search

d-krupke / cpsat-primer

The CP-SAT Primer: Using and Understanding Google OR-Tools' CP-SAT Solver
https://d-krupke.github.io/cpsat-primer/
Creative Commons Attribution 4.0 International
292 stars 27 forks source link

Some questions #4

Closed rlacjfjin closed 8 months ago

rlacjfjin commented 1 year ago

Hi, Thanks for sharing such good project. I have some questions:

  1. You say: ⚠️ If you use intersecting linear constraints, you may get problems because the intersection point needs to be integral. There is no such thing as a feasibility tolerance as in Mixed Integer Programming-solvers. it means cp-sat solver can't solve a general linear programming? Sorry I can't understand what the problems in intersecting linear constraints.
  2. About Circuit/Tour-Constraints, I think this is specialize for sub-tour problem, but when I want to add AddCircuit(), would the number of arcs grow exponentially? I didn't use this method, so I'm confusing this part, is there any refference examples ?
  3. I think the Array operations part is not clear explain, is there any more source to study?

Looking forward to your reply, thank you. Zhe.

d-krupke commented 1 year ago

Hey Zhe,

I am happy it is already useful, before it is completed (I am only writing it on the side, aiming to finish it in around another year).

  1. If you have the constraints $x=y$ and $x-1=-y$, the only feasible solution will be the intersection of the two implied lines at $x=0.5, y=0.5$. This is fine with linear programming, but not with CP-SAT. CP-SAT would tell you that there is no solution available. So, if one tries to simulate continuous variables (that are commonly necessary), you have to make sure not to have such constraints (that are common in some areas). However, CP-SAT should still have a similar performance if you don't have these problems as an LP-solver is part of its portfolio (though, it is probably not as good as Gurobi).
  2. I don't fully understand. Sub-tours don't need special constraints as you can just enforce that every vertex has to be entered and left. Could you elaborate your question, please? (Haven't used this constraints, neither. Gurobi is usually better for tour constraints.)
  3. You can check out the documentation https://google.github.io/or-tools/python/ortools/sat/python/cp_model.html I will look into the text next time I find the time and try to make it easier.

Best, Dominik

PS: If you have any idea on how to write things better/easier, feel free to submit a pull request or just write your idea here in the comments.