1
$\begingroup$

I'm trying to formulate an LP that is in essence a variant of the sudoku problem, and I've repurposed the code from https://coin-or.github.io/pulp/CaseStudies/a_sudoku_problem.html.

The differences are now that instead of a Boxes constraint in the original sudoku formulation, I now want each possible pair-wise sequences across a row to appear at least once (ie, the sequence 1-2 should appear once, 2-1 should appear once, etc).

In this specific scenario it is equivalent to having no duplicated pairwise sequences, but I intend to generalize this code for values/rows/columns that aren't equal.

To that end I've attempted two ways of formulating it:

  1. Making a new binary variable for the link between two cells, denoted [v1][v2][r][l], where l can take values from 1-8 (8 links in total between 9 cells).
# All rows, columns and values within a Sudoku take values from 1 to 9
VALS = ROWS = COLS = range(1, 10)
LINKS = range(1, 9) #8 links between cells in a given row
links = LpVariable.dicts("Links", (VALS, VALS, ROWS, LINKS), cat = "Binary")

Just like choices[v][r][c] is denoted as:

  • 1 if the cell at (r,c) has value v
  • 0 otherwise

links[v1][v2][r][l] is denoted as:

  • 1 if cell at [r][l] has value v1 and cell at [r][l + 1] has value v2
  • 0 otherwise

After setting the typical constraints on links (each individual link sums to 1 across all [v1][v2]), I then set the constraint as such:

for v1 in VALS:
    for v2 in VALS:
        if v1 != v2:
            prob += lpSum([links[v1][v2][r][l] for r in ROWS for l in LINKS]) >= 1 
            #Each link of v1 - v2 should appear at least once across all rows/links

The problem is now that I'm dealing with significantly more binary variables with this formulation - the original sudoku LP deals with 729 binary variables and here I deal with 5000-ish at the minimum and I'm not sure if this is efficient (or even feasible if I expand the range of rows/columns/values).

  1. Having a multiplicative boolean variable

Since each individual link is a binary variable that's 1 if both cell choices are 1, link[v1][v2][r][c] can be expressed as choices[v1][r][c] * choices[v2][r][c+1], and as such it should be possible to formulate a constraint as:

for v1 in VALS:
    for v2 in VALS:
        if v1 != v2:
            prob += lpSum(choices[v1][r][l] * choices[v2][r][l+1] for r in ROWS for c in LINKS) >= 1

but from what I understand of PuLP, constraints cannot involve multiplication since that makes them not linear. Linearizing it like in 1) would resolve it but run into the issues of way too many variables and constraints for a feasible run time if the problem is expanded in any way.

Are there better ways to formulate this constraint such that it doesn't require the creation of a 4d array to specify/solve for each individual link, and doesn't require multiplication in its constraints?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

You can define a binary link $z_{v,v'}$ and use the following linear constraints

$ z_{v,v'} \le \sum_{r,l}x_{r,l}^v$

$ z_{v,v'} \le \sum_{r,l}x_{r,l+1}^{v'}$

$\sum_{r,l}(x_{r,l+1}^v+x_{r,l}^{v'}) \le z_{v,v'}+1$

$z_{v,v'} \ge 1 \quad \forall v, v'$

where $x_{r,l}^{v}$ is your choice binary variable.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks. Correct me if I'm wrong but these are basically variables to force z to follow x(r,l) and x(r,l+1), basically necessary constraints to manage 1). In this case is there a way to approach using a link but without explicitly telling the solver to solve for the links AND the choices? Or does creating additional binary variables necessitate giving them to the solver to solve, since the runtime of 1) and the excessive variables + constraints was my issue with the approach $\endgroup$ Commented Jul 17, 2023 at 2:08
  • $\begingroup$ @Riezz to linearize a nonlinear relations like a product you need another variable $z$. You can the use this constraint $z_{v,v'} \ge 1 \ \forall v, v'$. But for the link variable $z$ there's no need to add dimensions with $r,l$, a 2D binary variable $z_{v,v'}$ won't put too much of complexity for the solver. Try it & let me know how it goes. $\endgroup$ Commented Jul 17, 2023 at 4:03
  • $\begingroup$ @Riezz you can directly use $\sum_{r,l} (x_{r,l}^v + x_{r,l+1}^{v'} - 1) \ge 1 $ provided that $x_{r,l}^v + x_{r,l+1}^{v'} \le 1$. Otherwise you'd have $0+0-1 $ situation $\endgroup$ Commented Jul 17, 2023 at 4:17
  • $\begingroup$ I'm having some trouble understanding the 3rd constraint $\sum_{r,l}(x_{r,l+1}^v+x_{r,l}^{v'}) \le z_{v,v'}+1$. Using v = 1, v' = 9 as an example: $z_{1,9}$ refers to if a link (1, 9) exists (or the count of (1, 9) links?), the first two constraints force it to less than or equal to the number of 1 on the left of the link and the number of 9 on the right of the link. The last constraint forces $z_{1,9}$ to be more or equal to 1 for all 1, 9 which is the original question. The 3rd constraint seems to be for the sum of 1s in left links and 9s in right link to be less than $z_{1,9}$? $\endgroup$ Commented Jul 17, 2023 at 6:20
  • $\begingroup$ But if 1 (1,9) link exists (and if 1 and 9 appear once in each column), $\sum_{r,l}(x_{r,l+1}^v+x_{r,l}^{v'})$ would be 16 regardless of how many links there actually are? It would be solved of course with $(x_{r,l+1}^v*x_{r,l}^{v'})$ but I'm not sure how this 3rd constraint works as is. $\endgroup$ Commented Jul 17, 2023 at 6:24
0
$\begingroup$

I would try having a 'link' variable for each row and ordered pair of values. Then force if to 0 if the reverse order appears anywhere in the row. If this is not general enough for you, I think your first option might be fast enough depending on your choice of solver.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you. Regarding the choice of solver, I'm using whatever is default for PuLP. Are there more suitable solvers for such questions? I've realized recently that or-tools is another option albeit solving it via constraint programming instead of ILP so if there are other options/solvers available that would be helpful to know. $\endgroup$ Commented Jul 17, 2023 at 2:09

Your Answer

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

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.