Mixed-Integer Programming vs. Constraint Programming for Shop Scheduling Problems: New Results and Outlook
Why this work is in the frame
A frame that forgets how it found something cannot be audited. These are the routes that admitted this work.
Bibliographic record
Abstract
Constraint programming (CP) has been recently in the spotlight after new CP-based procedures have been incorporated into state-of-the-art solvers, most notably the CP Optimizer from IBM. Classical CP solvers were only capable of guaranteeing the optimality of a solution, but they could not provide bounds for the integer feasible solutions found if interrupted prematurely due to, say, time limits. New versions, however, provide bounds and optimality guarantees, effectively making CP a viable alternative to more traditional mixed-integer programming (MIP) models and solvers. We capitalize on these developments and conduct a computational evaluation of MIP and CP models on 12 select scheduling problems. 1 We carefully chose these 12 problems to represent a wide variety of scheduling problems that occur in different service and manufacturing settings. We also consider basic and well-studied simplified problems. These scheduling settings range from pure sequencing (e.g., flow shop and open shop) or joint assignment-sequencing (e.g., distributed flow shop and hybrid flow shop) to pure assignment (i.e., parallel machine) scheduling problems. We present MIP and CP models for each variant of these problems and evaluate their performance over 17 relevant and standard benchmarks that we identified in the literature. The computational campaign encompasses almost 6,623 experiments and evaluates the MIP and CP models along five dimensions of problem characteristics, objective function, decision variables, input parameters, and quality of bounds. We establish the areas in which each one of these models performs well and recognize their conceivable reasons. The obtained results indicate that CP sets new limits concerning the maximum problem size that can be solved using off-the-shelf exact techniques. History: Accepted by Pascal Van Hentenryck, Area Editor for Computational Modeling: Methods & Analysis. 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.2023.1287 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2021.0326 ) at ( http://dx.doi.org/10.5281/zenodo.7541223 ).
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.001 | 0.001 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.000 | 0.000 |
| Science and technology studies | 0.000 | 0.000 |
| Scholarly communication | 0.001 | 0.000 |
| Open science | 0.000 | 0.000 |
| Research integrity | 0.000 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from it