Note from the Editor

We continue to announce the winners of INFORMS Journal on Computing (IJOC) Test of Time Paper Award to cover the backlog of awards since the journal’s inception. The energetic and able committee chaired by John Chinneck with members Bill Cook, Bruce Golden, Pascal Van Hentenryck, and David Woodruff, has selected the awardee covering the period 1997 through 2001. What follows is the citation from the award committee and then a reflective interview with the authors about this paper.

I want to thank the committee for its superb efforts and I am very pleased to share this recognition of the impactful heritage of our journal.

All my best,

The Test of Time Award for papers published in the INFORMS Journal on Computing in the years 1997–2001 is awarded to

Algorithms for Hybrid MILP/CP Models for a Class of Optimization Problems

 Vipul Jain and Ignacio E. Grossmann

 INFORMS Journal on Computing 13(4):258–276, 2001

 https://pubsonline.informs.org/doi/abs/10.1287/ijoc.13.4.258.9733

Test of Time Award Citation 1997–2001

This paper is an early and compelling application of logical Benders decomposition, where the master problem is solved by a mixed-integer program and the subproblems by constraint programming. The authors consider a scheduling problem on a pool of heterogenous machines, where the master problem allocates the jobs to the machines, the subproblems schedule the machines, and a logical Benders decomposition connects them.

In addition to its contributions to the considered application, the paper was instrumental in stimulating significant and substantial research in logical Benders decomposition, branch and check, and branch and price and check, with applications in many domains including routing and scheduling.

Retrospection from the Authors Vipul Jain and Ignacio E. Grossmann

Many thanks to the editor-in-chief, Alice Smith, and the selection committee for selecting our paper for this prestigious recognition. We were both very excited to learn about the selection of our paper for the Test of Time Award 1997–2001.

We would like to first acknowledge two major researchers who motivated this paper: Professor John Hooker and Professor Pascal Van Hentenryck. Professor Hooker pioneered the integration of optimization techniques with symbolic logic and constraint programming, going back to his 1988 paper A quantitative approach to logical inference (Hooker 1988), subsequent papers (Hooker and Osorio 1999, Hooker et al. 1999, Ottosson et al. 2002), and the seminal book Logic-Based Methods for Optimization: Combining Optimization and Constraint Satisfaction (Hooker 2000) that established this field as a new exciting research area. Professor Pascal Van Hentenryck (Michel and Van Hentenryck 2005, Van Hentenryck and Milano 2011) pioneered constraint logic programming (Dincbas et al. 1988) and made his work available through the software Optimization Programming Language (OPL) (Van Hentenryck 1999), which we used in our work. It is interesting to note that Professor John Hooker was at the time the area editor for Logic, Optimization and Constraint Programming in INFORMS Journal on Computing and handled our paper.¹

We are chemical engineers by training but have been active in the application of optimization models and algorithms for the design, planning, and scheduling of process and energy systems (Grossmann 2002, 2021; Grossmann et al. 2008). The INFORMS Journal of Computing paper was motivated by the computational challenges we encountered in the modeling and optimization of scheduling manufacturing operations through mixed-integer linear programming (MILP). These challenges were largely due to weak linear programming (LP) relaxations that were due to precedence constraints that involved big-M constraints. At the same time, constraint programming (CP) started to emerge as a modeling technique that allowed the efficient solution of sequencing problems for scheduling.

In fact, some of the presentations during the INFORMS Annual Meeting in the spring of 1998 in Montreal motivated us to try CP to solve scheduling problems using ILOG’s OPL framework (Van Hentenryck and Lustig 1999), which was actually somewhat outside of our focus at that point in time. During that conference, there was a lot of discussion on how the CP engine in ILOG could be very effective in solving some challenging sequencing problems. It made us wonder why the MILP method cannot solve some of the same problems as efficiently. This made us think whether we could add some preprocessing in MILP methods to improve the computational effectiveness. During that process, we realized that MILP and CP offer complementary strengths to solve problems that are otherwise are intractable if solved using either of the two methods by themselves. We would attribute our ability to test ideas presented in this paper to ILOG’s OPL, which became available at that time. Before that time, there was no other tool that was available to solve MILP and CP using a single platform. ILOG at that time generously allowed us to experiment with their new software platform.

The class of problems we considered had the characteristic that only a subset of the binary variables had nonzero objective function coefficients if modeled as an MILP. We next formulated a hybrid MILP/CP model that involved a relaxed MILP, a reduced set of CP constraints, and the equivalence relations between the MILP and the CP variables. To solve this hybrid model, we developed an MILP/CP-based decomposition and solved it using an LP/CP based branch-and-bound algorithm that relied on the relaxed MILP and feasibility CP problems. The motivation in developing these hybrid methods was to combine the strength of MILP for proving optimality by using the LP relaxations and the power of CP for finding feasible solutions for hard discrete optimization problems using specialized propagation algorithms. We established a rigorous convergence proof for this type of method. The computational efficiency of the proposed algorithms strongly depends on the nature of the relaxed MILP problem, the feasibility CP problem, and the integer cuts used in the algorithm.

As an application example, we considered a scheduling problem whose aim was to find a least-cost schedule to process a set of orders using dissimilar parallel machines subject to release and due date constraints. We showed that this problem can be modeled as an MILP, CP, or combined MILP/CP model. The CP model was more succinct in terms of representation compared with the MILP model because there were high level constructs for modeling scheduling problems. Conversely, the combined MILP-CP OPL model was larger in size then the CP model but was smaller compared with the MILP model due to equivalence relations that had to be added. To implement our algorithm, we relied on newly available features in OPL, which integrated both MILP and CP solvers in one platform. It is worth remembering that ILOG bought CPLEX in 1997, and this commercial development led to software integration allowing CPLEX and ILOG’s CP solver to become accessible via one single platform, namely OPL. Without OPL, we are not sure we would have been able to test our ideas so readily. We were fortunate to have benefited tremendously from these developments and vibrant discussions during the INFORMS conference about our work. We used CPLEX for the MILP subproblem and the ILOG constraint solver for the CP subproblem. The combined model could solve most of the problems significantly faster relative to the MILP and CLP models. The computational results indicated that, for the larger instances of the example scheduling problem, the computational times were two to three orders of magnitude faster compared with MILP, CLP, or the combined MILP-CLP OPL method. Needless to say, we were very happy with these impressive results.

The research paper at the time of publication caught the imagination of many different researchers, and we had many fruitful follow-up discussions. However, this award truly made us realize the impact this research paper has had, and we are truly grateful for this recognition.