Do you know any sources on on how set equivalence theory is related to integer programming? Because I don't see the immediate connection and I could not find anything on the internet, but maybe I used the wrong terms.
I don't know any reference for this - it's something I worked out after hearing about Phistomefel's Theorem from a friend. The idea goes like this:
The standard Linear Programming relaxation of the constraint "the nine variables x_1, ..., x_9 are a permutation of 1, ..., 9" is defined in the following way. First we make real variables p_ij which we think of as representing the "probability" that x_i is equal to j. Each p_ij has to be between 0 and 1, of course, and they have to satisfy the following system of linear equations:
- for each i, the sum over j of p_ij is equal to 1 (since every x_i has to have some value), and
- for each j, the sum over i of p_ij is equal to 1 (since every value from 1, ..., 9 has to show up in the list of x_is somewhere).
The fact that this system of equations, together with the inequalities 0 <= p_ij <= 1, corresponds exactly to the "convex hull" of the constraint that the x_i are a permutation of 1, ..., 9 is a fairly famous early result from the theory of the Linear Programming relaxation of the bipartite matching problem.
To describe the full Linear Programming relaxation of Sudoku, instead of just having 9 variables x_i you have 81 variables x_ab, which leads to 729 real "probability" variables p_abj between 0 and 1, and for each row, column, and square of the Sudoku these probabilities have to satisfy the equations listed above (applied to the relevant variables). That gives you a system of 324 (slightly redundant) linear equations in 729 unknown real variables p_abj, each of which is constrained to be between 0 and 1 - a piece of cake for a computer.
For a human, you don't want to write down that entire system of equations - you want to use just a few of them to quickly figure out some piece of the puzzle. The technique of set equivalence theory does just this: instead of focusing on all of the probabilities p_abj, you just use the fact that the sum of the probabilities p_ab1 along every row/column is 1, and add/subtract the equations you get from some rows and columns to notice that the sum of the p_ab1s for the (ab)s corresponding to the corners is equal to the sum of the p_ab1s for the (ab)s corresponding to the ring around the center. Then you do the same for the 2s, and so on.
cevi|3 years ago
The standard Linear Programming relaxation of the constraint "the nine variables x_1, ..., x_9 are a permutation of 1, ..., 9" is defined in the following way. First we make real variables p_ij which we think of as representing the "probability" that x_i is equal to j. Each p_ij has to be between 0 and 1, of course, and they have to satisfy the following system of linear equations:
- for each i, the sum over j of p_ij is equal to 1 (since every x_i has to have some value), and
- for each j, the sum over i of p_ij is equal to 1 (since every value from 1, ..., 9 has to show up in the list of x_is somewhere).
The fact that this system of equations, together with the inequalities 0 <= p_ij <= 1, corresponds exactly to the "convex hull" of the constraint that the x_i are a permutation of 1, ..., 9 is a fairly famous early result from the theory of the Linear Programming relaxation of the bipartite matching problem.
To describe the full Linear Programming relaxation of Sudoku, instead of just having 9 variables x_i you have 81 variables x_ab, which leads to 729 real "probability" variables p_abj between 0 and 1, and for each row, column, and square of the Sudoku these probabilities have to satisfy the equations listed above (applied to the relevant variables). That gives you a system of 324 (slightly redundant) linear equations in 729 unknown real variables p_abj, each of which is constrained to be between 0 and 1 - a piece of cake for a computer.
For a human, you don't want to write down that entire system of equations - you want to use just a few of them to quickly figure out some piece of the puzzle. The technique of set equivalence theory does just this: instead of focusing on all of the probabilities p_abj, you just use the fact that the sum of the probabilities p_ab1 along every row/column is 1, and add/subtract the equations you get from some rows and columns to notice that the sum of the p_ab1s for the (ab)s corresponding to the corners is equal to the sum of the p_ab1s for the (ab)s corresponding to the ring around the center. Then you do the same for the 2s, and so on.