I recently ran across a paper comparing Constraint Programming (CP) and Mixed-Integer Programming (MIP) for scheduling operating theatres (if you don’t have access, here is what appears to be an earlier version).
I went googling for some other comparisons. Here’s what I found:
- Comparing Solution Methods for the Machine Reassignment Problem (2012): “The results suggest that our CP-based LNS can scale to large instances and is superior in memory use and the quality of solutions that can be found in limited time.”
- CP and MIP Methods for Ship Scheduling with Time-Varying Draft (2012): “We found that the CP model with a good choice of search strategy was significantly faster and was able to solve larger problems than the MIP model.”
- Comparing Mixed & Integer Programming vs. Constraint Programming by solving Job-Shop Scheduling Problems (2015): “In this work, each model is individually analyzed and then compared considering: i) Optimization success performance, ii) Computational processing time, iii) Greatest Resource Utilization and, iv) Minimum Work-in-process Inventory. Results demonstrated that CP-2 presented best results on criteria i and ii, but MIP was superior on criteria iii and iv and those findings are discussed at the final section of this work.”
- A comparison of an CP and MIP approach for scheduling jobs in production areas with time constraints and uncertainties (2018): “The test results show that the CP model outperforms the MIP and quickly finds much earlier usable schedules for large problem sizes.”
- A Comparison of Constraint Programming and Mixed‐Integer Programming for Automated Test‐Form Generation (2018): “Both examples show that CP works well with feasible solutions and running times likely to be better than that for MIP‐based applications.”
- An Update on the Comparison of MIP, CP and Hybrid Approaches for Mixed Resource Allocation and Scheduling (2018): “We consider a well known resource allocation and scheduling problem for which different approaches like mixed-integer programming (MIP), constraint programming (CP), constraint integer programming (CIP), logic-based Benders decompositions (LBBD) and SAT-modulo theories (SMT) have been proposed and experimentally compared in the last decade. Thanks to the recent improvements in CP Optimizer, a commercial CP solver for solving generic scheduling problems, we show that a standalone tiny CP model can out-perform all previous approaches and close all the 335 instances of the benchmark.”
Perhaps Google knows I have a CP bias. 🙂 Or perhaps someone can point to alternative results in the Comments.
Gene Freuder 
Hi Gene,
Very interesting collection of papers. Off the top of my head, here are a few more on a similar line (but I’m also CP biased):
* Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches (2016):
“We also provide the reasons why CP would be soon welcomed by the practitioners. Firstly, CP’s natural formulation is closer to the problem description than the restricted linear programming formulation. Secondly, a concise CP code provides a flexibility and scalability to practitioners. Thirdly, unlike meta-heuristics which are tailor-made requiring a fine tuning of parameters to reach at the best performance, CP is off-the-rack. Namely, practitioners provide a high level description of the problem only. All settings of search algorithms and detailed tunings are automatically done by CP engine. Finally, CP outperforms MIP in the scheduling problems as we demonstrate in this study.”
* A Constraint Programming model for food processing industry: a case for an ice cream processing facility (2019):
“This paper presents a Constraint Programming (CP) scheduling model for an ice cream processing facility. […] Its performance was compared to a Mixed Integer Linear Programming (MILP) model from the literature for optimality, speed, and competence using the partial capacity of the production facility of the case study. Furthermore, the model was tested using different product demand sizes for the full capacity of the facility. The results demonstrate both the effectiveness, flexibility, and speed of the CP models, especially for large-scale models.”
* Resource-constrained multi-project scheduling with activity and time flexibility (2020):
“Project scheduling in manufacturing environments often requires flexibility in terms of the selection and the exact length of alternative production activities. Moreover, the simultaneous scheduling of multiple lots is mandatory in many production planning applications. To meet these requirements, a new resource-constrained project scheduling problem (RCPSP) is introduced where both decisions (activity flexibility and time flexibility) are integrated. Besides the minimization of makespan, two new alternative objectives are presented: maximization of balanced length of selected activities (time balance) and maximization of balanced resource utilization (resource balance). New mixed integer and constraint programming (CP) models are proposed for the developed integrated flexible project scheduling problem. Benchmark instances on an already existing flexible RCPSP and the newly developed problem are solved to optimality. The real-world applicability of the suggested CP models is shown by additionally solving a large industry case.”
* Mathematical programming approach to productivity improvement in wind turbine-blade manufacturing through a case study (2020):
“Wind energy has attracted remarkable attention in recent years as one of the most important renewable energy sources. However, wind energy production is still a costly process and one of the reasons is production processes which are usually not optimized. The purpose of this paper is to improve the efficiency of spar cap production process as an important phase of a wind turbine blade production in a manufacturing system. For this purpose, the present paper introduces a new optimization problem for optimal assignment of fiberglass rolls along the spar cap. In order to solve the roll allocation problem (RAP) optimally, two alternative mathematical programming models based on mixed-integer programming (MIP) and constraint programming (CP) are developed. Subsequently, two cases form a real manufacturing setting are presented and solved by using both MIP and CP models. Although proposed models are capable to solve problems optimally, it is observed that CP outperforms MIP. Solving RAP optimally reduces walking time/distance of workers considerably and provides significant improvements in comparison with current manufacturing practices. Besides, the total operation time will also decrease correlatively, and this will lead to an increase in productivity of turbine blade production in the studied system.”
* Scheduling of Operations in Quantum Compiler (2020):
“When scheduling quantum operations, a shorter overall execution time of the resulting schedule yields a better throughput and higher fidelity output. In this paper, we demon- strate that quantum operation scheduling can be interpreted as a special type of job-shop problem. On this basis, we provide its formulation as Constraint Programming while taking into account commutation between quantum operations. We show that this formulation improves the overall execution time of the resulting schedules in practice through experiments with a real quantum compiler and quantum circuits from two common benchmark sets.”
“… We also examined the MIP solver (with the same 10-sec time limit) to find solutions of the Ext-DAG; however, all of the solutions were slightly worse or equal to those by the CP solver.”
* Balancing stochastic type-II assembly lines: chance-constrained mixed integer and constraint programming models (2020)
“In the literature, line balancing is mostly investigated in deterministic environments. But production systems inevitably contain stochastic situations. In this study, the stochastic type-II assembly line balancing problem (ALBP) is considered. Firstly, a chance-constrained nonlinear mixed integer programming (MIP) formulation is developed from the well-known deterministic form. Then, a new linearized stochastic model is proposed by using some transformation approaches to reduce model complexity, and the model is solved. Finally, constraint programming (CP) models for deterministic ALBPs, nonlinear chance-constrained stochastic ALBPs and linearized chance-constrained stochastic ALBPs are developed, respectively. Problems from the literature are utilized to test the effectiveness of the proposed models and the results are compared with a bidirectional heuristic algorithm. The numerical results show that the CP models are more effective and successful for solving the stochastic ALBP. Some managerial implications are also suggested for industrial environments that consistently face ALBPs.”
great set of references and here is another one:
Flexible job shop scheduling problem with parallel batch processing machines: MIP and CP approaches, 2016 – ” Computational results find three key lessons: the proposed MIP model significantly reduces computational time compared to the original model from the literature, the valid inequalities further reduce a computational time, and CP incomparably outperforms all three MIP models.”
https://www.sciencedirect.com/science/article/abs/pii/S036083521630417X