4 ms·
> There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's walle
by polivier 3y ago
> There are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :)
While this is generally true, there are some exceptions. I recently compared the performance of CP-SAT vs CPLEX for a problem (linear constraints and objective). For large instances where proving optimality in a reasonable time was out of the question, CP-SAT had much faster convergence to near-optimal solutions than CPLEX when the time limit was small enough (~30s to a few minutes). This is with the CPLEX solver tuned towards improving the upper bound as much as possible (it was a minimization problem).
- whatever1 3y agoIf feasibility is your goal then cp/sat solvers/heuristics should be your tool of choice. I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go
- sterlind 3y agocan't you just use the strong duality theorem to reframe an integral optimization problem as a system of integer inequalities? I thought you usually don't do that because the satisfaction problem is harder in practice.
- whatever1 3y agoNo unfortunately strong duality does not hold for integer problems. But your intuition is right, this is roughly how IP optimizers work. They relax the problem to a continuous one (aka convert the {0,1} to [0,1]), solve this super easy linear problem and try to find integral solutions close this linear optimum. If not, start branching on the integers and solve smaller and smaller linear problems until you prove optimality.
- polivier 3y agoI think that you've misunderstood what I said. For large instances of this specific problem (and when the time limit is too short to allow either CP-SAT or CPLEX to prove optimality) the best integer feasible solution found by CP-SAT is generally of better quality (w.r.t. the objective value) than the best integer feasible solution found by CPLEX. Furthermore, in some cases, CP-SAT can offer a certificate of optimality faster than CPLEX.
- 7thaccount 3y agoHmmm...for this problem, have you tried Hexaly? Just curious.
- polivier 3y agoNo I haven't, but in our case CP-SAT works very well and license-wise it's free.
- fhk 3y agoYes, highly recommended. There is abit of a gap in modeling approaches to classic MILP but the team are very proactive to make it work. Also very permissive license with unlimited deployment and cores!
- whatever1 3y agoWell these are generic solvers, meaning that they are tuned to perform on a variety of problems well, so you can easily find cases where you get unexpectedly low performance. My advice is if you are on the clock, just use whatever works best out of the box. Now if you plan to solve this problem thousands of times daily, then I would invest in writing custom callbacks in CPLEX to inject feasible solutions during the search since its heuristics are suffering in your problem case.