Google CP-SAT Infeasible ILP for Large Problem Area

Question

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

Answer 1

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.

Answer 2

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.