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