8
$\begingroup$

I'm using the OR-Tools CP-SAT solver to fill a table with integers, with various constraints, as illustrated by the x in the following figure.

|   | A | B | C | D | E |
| 1 | x | x | x | x | x |
| 2 | x | x | x | x | x |
| 3 | x | x | x | x | x |
| 4 | x | x | x | x | x |
| 5 | x | x | x | x | x |

Sadly, the solving time become prohibiting when the dimensions of the table increase. I know that if a given problem has no solution with, for instance, 5 columns (A-E), it won't have a solution with any number of additional columns (A-Z). Therefore, theoretically, I should be able to know quickly if a problem with 26 columns is infeasible by checking beforehand if the same problem with 5 columns, or 6 columns, or 7 columns, … is infeasible.

How could I make the solver aware of this fact? I have tried to loop over the number of columns and breaking at the first failure, but it comes with two problems:

  • the solver can't use the knowledge gained in the previous iteration of the loop;
  • the solver fails quickly if the problem is infeasible, but takes a long time to succeed; if a 26-column problem is feasible until the 25th column, then I've lost a long time in finding 25 useless partial solutions.

Is is impossible, or have I overlooked a way to do that? Is there any way to use a decision strategy, for instance?

Improve this question
$\endgroup$
6
  • $\begingroup$ Please let me know if: 1) You have any idea for a better title on this question. I'm not satisfied with the current one, but I can't find a way to summarize my problem in only a few words. 2) You think it's more suited to SO (where it's being from "migrated" from). 3) There are more suited tags (I'm new here and not really aware of the various tags). $\endgroup$
    – Blackhole
    Commented Aug 22, 2019 at 18:53
  • $\begingroup$ With solution hinting, you can guide your search towards the solution of the previous iteration. Not sure decision strategy will help. Have you tried parallelism ? $\endgroup$
    – Laurent Perron
    Commented Aug 22, 2019 at 20:17
  • $\begingroup$ @LaurentPerron I've already tried solution hinting, to no avail. Should I try to use some decision strategy to ask the solver to modify the variables associated with the new column first, or would it be in vain? Parallelism sounds like a good idea, I'll try. $\endgroup$
    – Blackhole
    Commented Aug 22, 2019 at 22:18
  • $\begingroup$ I never use decision strategies myself :-) $\endgroup$
    – Laurent Perron
    Commented Aug 23, 2019 at 5:43
  • $\begingroup$ So, what is the goal there ? Fail quickly, or improve the time to find a solution? To fail quickly, you can reduce you problem with any subset of the table and check it. To improve performance of finding a solution, this is a much harder problem I struggle with everyday. $\endgroup$
    – Laurent Perron
    Commented Aug 23, 2019 at 15:41

1 Answer 1

Reset to default
3
$\begingroup$

Manually create groups, if you know which groups make more sense than others then you don't need to define every possible permutation. If you are less certain you can use a script to enumerate the combinations.

If you actually need (eventually) all 26 columns for a successful solution (fewer than 26 is always a failure, regardless of early success) then the MIP solver is faster; you would be staring at blank progress for a while, but for less time than false hopes.

You can also use time limits during the day, while you check for an answer, and remove them overnight (or all weekend, if at work) to pursue hopeful paths when more time is available.

Instead of showing the first solution of a smaller set show all solutions, then combine each permutation of the smaller solution sets into bigger sets; eventually producing a group of 26 that work together.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I do not understand why you conclude that the MIP solver is faster. With a large table constraint, there is no way a MIP solver can be faster. $\endgroup$
    – Laurent Perron
    Commented Aug 23, 2019 at 5:44
  • $\begingroup$ @LaurentPerron When you click on that link you can see that it is what they claim. $\endgroup$
    – Rob
    Commented Aug 23, 2019 at 5:46
  • $\begingroup$ I wrote that doc. Please trust me on this case. Plus, it talks about the original CP solver. The CP-SAT solver is closer to a MIP solver than you think. $\endgroup$
    – Laurent Perron
    Commented Aug 23, 2019 at 14:19
  • 5
    $\begingroup$ Interesting. Why the aggressive tone? Why measure my contribution to the number of upvotes ? I believe OR-Tools is already a decent contribution. BTW, I am actually on vacation, and answering to S.O. on my free time, to support the community of a free product? OR-Tools is not my job $\endgroup$
    – Laurent Perron
    Commented Aug 23, 2019 at 15:35
  • $\begingroup$ Thanks for your answer, Rob. As explained by @LaurentPerron, I'm not sure switching to a MIP solver is worth it (my problem really isn't convex at all). Your idea with groups sound interesting, but I'm not sure to understand it correctly. What should I do with it? $\endgroup$
    – Blackhole
    Commented Aug 23, 2019 at 16:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.