The conclusion is that the strength of CP-SAT depends on its successful integration of search, inference, and OR-based relaxation on top of a satisfiability solver.
Abstract
A simple but general semantics for timed Petri nets is presented in this paper. Based on this semantics, an optimization formulation is introduced and implemented in a recently developed optimization solver, where a satisfiability (SAT) solver is integrated with constraint programming (CP). The solver, called CP-SAT, is a part of Google’s OR-Tools. The optimization formulation includes both concurrent and alternative sequences of operations, involving shared as well as alternative resources. The proposed optimization strategy is compared with the SAT/SMT-based solver Z3Opt and Gurobi’s mixed integer linear programming (MILP) solver. The conclusion is that the computation time for CP-SAT is much shorter than for Z3Opt, while MILP is able to handle deep problems, including long sequences with many transitions, with similar computational performance as CP-SAT. On the other hand, CP-SAT is much faster than MILP for wide problems, including many parallel sequences. An evaluation of an industrial-sized flexible manufacturing system, which involves uncontrollable events, also demonstrates how efficient and easy to implement the proposed strategy is compared to existing results. In addition, it is also demonstrated how basic functionality in SAT and constraint programming are related and integrated in CP-SAT. The conclusion is that the strength of CP-SAT depends on its successful integration of search, inference, and OR-based relaxation on top of a satisfiability solver.
The goal is to translate high-level constraint satisfaction and optimization problems into any lower-level formalism, including CP, SMT QF-LIA, ILP, PB and (Max)SAT, and to present a modular framework for transforming the high-level modeling language to CP/SMT/ILP/PB and (Max)SAT solvers.
Tias Guns, Ignace Bleukx, H. Bierlee et al.· 0 citations
Solving Boolean polynomial systems, or equivalently, SAT-solving, based on the XNF and the XLIN proof system outperforms classical methods not only theoretically, but based on the new conflict-driven XNF clause learning methods developed here, it is possible to implement an XNF solver with good practical efficiency.
Julian Danner, Martin Kreuzer· Journal of Artificial Intell...· 0 citations
Here it is explained how and why the WhyUnsat approach is now also directly applicable, at no implementation cost, to IPASIR-UP-based constraint programming by Lazy Clause Generation (LCG) as well as to SAT Modulo Theories (SMT).
R. Nieuwenhuis, Albert Oliveras, Enric Rodríguez-carbonell· 0 citations
Personnel scheduling problems (PSPs) often involve multiple working rules that are difficult to integrate into mixed-integer programs (MIPs). Recent works have proposed to overcome this limitation by representing the set of valid schedules as words of a formal language. A set of linear constraints can be derived from this language to obtain an efficient MIP formulation. A significant drawback of this methodology is the absence of a generic or automated approach for incorporating some classical working rules into a formal language. In this paper, we propose a generic modeling approach to address this gap and represent a wide variety of working rules in PSPs with regular languages. More precisely, we formalize four standard rules and show how to obtain a deterministic finite automaton (DFA) representation for each of them. Then, we introduce four specific operations on DFA and present their practical computation. The standard rules, combined with the operations on DFA, allow us to integrate most of the classic working rules found in the PSP literature. In addition to allowing efficient formulations for many PSPs, this framework also offers an easy way to automatize the modeling of such problems. We finally discuss the practical use of this formalism and illustrate its performance with numerical experiments on a nurse scheduling problem (NSP).
History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis.
Funding: This work was supported by Agence Nationale de la Recherche [Grant ANR-21-CE22-0002]. This research also used resources of the GLiCID Computing Facility (Ligerien Group for Intensive Distributed Computing, Pays de la Loire, France).
Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2024.1003 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2024.1003 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .
Guillaume Ghienne, O. Bellenguez, Guillaume Massonnet et al.· INFORMS journal on computing· 0 citations
A new proof system for MaxSAT is described, the Comparator Calculus, which models the inferential strategies used in core-guided MaxSAT solvers and two new MaxSAT algorithms are introduced: a core-guided one (CSimple) and one non-core-guided (CSat), which uses heuristics to construct new soft formulas and calls a SAT solver on a single soft formula.
Ilario Bonacina, J. Levy, Ion Mikel Liberal· International Conference on...· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
