1
$\begingroup$

I am trying to generate a shortest path between source and sink in a square grid of cells. I am using the Google CP-SAT solver as I believe it is recommended for problems with integer/boolean decision variables. In my case I have a square matrix P of NUM_CELLS*NUM_CELLS entries where P[i][j] represents a transition from cell i to j.

I have noticed that the problem becomes infeasible for NUM_CELLS greater than, around 256. Is there an error in my ILP implementation, or is the problem size just too big?

You may view my attempt here: https://gist.github.com/raghavthakar/eafb590a3d1dc8c1c7f3d62098cb47b2

[EDIT]: Here is the error I received:

CpSolverResponse summary:
status: INFEASIBLE
objective: NA
best_bound: NA
booleans: 159201
conflicts: 0
branches: 37708
propagations: 7681149
integer_propagations: 7718860
restarts: 37708
lp_iterations: 9
walltime: 44.9287
usertime: 44.9287
deterministic_time: 3.85921
gap_integral: 0

Traceback (most recent call last):
  File "/home/raghav/move_box/src/scripts/cp-sat_test.py", line 106, in <module>
    if solver.BooleanValue(P[i][j]):
  File "/home/raghav/.local/lib/python3.6/site-packages/ortools/sat/python/cp_model.py", line 2165, in BooleanValue
    return EvaluateBooleanExpression(literal, self.__solution)
  File "/home/raghav/.local/lib/python3.6/site-packages/ortools/sat/python/cp_model.py", line 2057, in EvaluateBooleanExpression
    return bool(solution.solution[index])
IndexError: list index (0) out of range
Improve this question
$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

With 256, I get the optimal solution quite fast. With > 256, I get the following error:

python3.9  infeasible_grid_sat.py
Traceback (most recent call last):
  File "infeasible_grid_sat.py", line 29, in <module>
    W[i][i+1] = 1
IndexError: list assignment index out of range

with 324 (18^2), I get an optimal solution easily.

So it seems there is a problem with array boundaries.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you.The error I got was completely different. I have edited the question to provide that as well. $\endgroup$
    – Raghav Thakar
    Jun 8, 2022 at 1:55
  • $\begingroup$ You cannot query a solution if the problem is infeasible. $\endgroup$
    – Laurent Perron
    Jun 8, 2022 at 6:14
  • $\begingroup$ yes, that is true! I'm yet to find out why it is becoming infeasible, but the search is still on. $\endgroup$
    – Raghav Thakar
    Jun 8, 2022 at 14:23
1
$\begingroup$

So the issue here is that I have overconstrained the model. I am constraining the relationship between out_degree and in_degree while simultaneously constraining the actual value of out_degree or in_degree too.

Instead, once the relationship between out_degree and in_degree has been developed, simply constrain out_degree <= 1.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.