BIP for Sudoku naturally integral?

Question

I was reading through the following notes regarding solving a 9x9 Sudoku via a binary integer program

https://vanderbei.princeton.edu/tex/talks/INFORMS_19/Sudoku.pdf

The formulation is straightforward but on slide 10 the author claims that if the problem has a unique integer solution then that implies the linear relaxation has the same solution and therefore the binary constraints on the variables is unnecessary.

It's really not clear to me why this would be so. Wouldn't this contradict the fact that Sudoku is known to be NP-complete?

Edit:

The following Sudoku has a unique solution. You can verify that by solving it by logical deduction alone.

4  7     |     3     |  6  2   
9  3     |  2     6  |  7  4   
6  2  8  |  5  7  4  |  1  9  3
-------------------------------
2  1  3  |  8  4  5  |  9  7  6
   4  9  |  3  6  7  |     1  2
7     6  |        2  |  3     4
-------------------------------
1  6  7  |  4     3  |  2     9
3     4  |  7  2     |     6  1
      2  |  6     1  |  4  3  7

I adapted the PuLP sudoku example code and the LP relaxation solves with the unique integral solution. However, I introduced auxiliary variable and constraints and changed objective function to make non integral solutions more attractive, and it found a solution where 42 of the variables had a value of 1/2.

So this counts as a counter-example that a unique BIP solution gives rise to a unique LP solution.

No, its the other way around. It means that in this specific case, the sudoku is no longer NP-hard. — Kuifje, Oct 06 '22 at 10:06
@Kuifje Are you sure it is referring to this specific case? The last sentence on the slide is "Hence, it is always possible to solve sudoku problems as linear optimization problems" - that seems like a very general statement. — Ram, Oct 06 '22 at 10:14
I have found Provan (2009) where they say that if the solution of the Sudoku can be found via pigeon-hole rules (i.e. enough non-empty cells are given), then the relaxation solution is integer (Theorem 2). In general, it is NP-complete by reduction to graph colouring or set covering. The claim on unique integer solutions in this talk sounds wrong (otherwise all MIPs with unique integer solutions would be easy peasy). — David Torres, Oct 11 '22 at 11:15

Hexaly · Accepted Answer · 2022-10-10T17:20:56.210

2

The creators of the Sudoku puzzles ensure players that there is a unique solution to the puzzle. Hence, the system of integer linear equalities over Boolean variables described in Vanderbei's slides has one and only one solution. This is what Vanderbei calls the "unique integer solution" in slide 10.

EDIT: THE FOLLOWING ARGUMENT IS FALSE BECAUSE THE RANK OF THE MATRIX IS NOT (NECESSARILY) FULL. SORRY FOR THIS WRONG PATH. SEE THE DISCUSSION IN THE COMMENT. Now, consider a relaxation of this system of equalities over the reals. This is what Vanderbei calls "linear relaxation" in slide 10. The unique integer solution discussed above remains a solution to this relaxed system. A system of linear equalities over the reals has no solution, one solution, or an infinite number of solutions (for a proof of this claim, or at least an intuition, please check a linear algebra course on the web). Consequently, the linear relaxation has one solution which is the integer one.

In the case where the initial assertion becomes false - "the creators of the Sudoku puzzles ensure players that there is a unique solution to the puzzle" - then the property above does not hold anymore.

Then, to answer your question, the best is to cite David Eppstein, a renowned computational complexity theorist, who blogged a lot about the complexity of the Sudoku puzzle in the past:

"In the meantime, when one says Sudoku is NP-complete, one should keep in mind that this refers only to an unusual type of Sudoku puzzle in which there might be multiple solutions."

To conclude, may we recall that any KxK Sodoku puzzle with K a fixed parameter in input, that is, with K a constant, is solvable in constant time.

edited Oct 10 '22 at 17:20

answered Oct 06 '22 at 17:55

Hexaly

2,976
1
11
17

2

Thanks @LocalSolver. I'm still missing whatever is needed to make the conclusion that "Consequently, the linear relaxation has one solution". Why could it not be the case that we have one integer solution and infinite number of non-integer solutions to the linear relaxation? The simple BIP with two variables and a single constraint 2x_1 + x_2 = 2 has a single integer solution (1,0) but the linear relaxation has an infinite amount of solutions right? – Ram Oct 06 '22 at 22:30
In the case you mention here, your system has 2 variables but 1 equality. Then it can have an infinity of solutions over the reals. More generally, if your system has N variables and M equalities with M < N, then you will have an infinite number of solutions. If the system has N variables and M equalities with M >= N and no linearly dependent equalities, which is the case here (check the AMPL output: 198 variables, 212 constraints on page 9), then there is one or no solution. – Hexaly Oct 07 '22 at 20:40
I probably misunderstand this argument. If M>=N then the rank can at most be N. So there must be linear dependent constraints, right? Of course, LP solvers typically work with N+M variables. – Erwin Kalvelagen Oct 08 '22 at 16:51
You're right @ErwinKalvelagen. The argument is fallacious. Intuitively, I feel the rank to be full because, according to the principle of the game, one can reduce the matrix using simple propagation techniques. Sorry for this. But our exchange leads to interesting thoughts and experiments. Below are the ones. – Hexaly Oct 09 '22 at 21:05
Consider the original system, without applying any reduction techniques using the integrity of variables. The system is underdetermined, thus there is an infinity of real solutions. Now, consider the corresponding LP in normal form. Seems that when the Sodoku puzzle has only one solution, there is only one basic feasible solution to this LP, which is thus the integral one. Consequently, the simplex finds it. Here is a related paper: https://ieeexplore.ieee.org/document/5247059 Open question: it is true? If not, would be nice to see some basic feasible solutions that aren't integral.

Hexaly

Oct 09 '22 at 21:50

Modern MILP solvers apply sophisticated constraint propagation techniques before the computation of the root node LP. By using a modern MILP solver, you will observe that it eliminates almost all - if not all - the columns and rows of the system before the computation of the LP relaxation. So we need to be precise when we talk about the "linear relaxation". The LP after any good constraint propagation is trivially integral.

– Hexaly Oct 09 '22 at 22:20

BIP for Sudoku naturally integral?

1 Answers1