Success Stories in Integrated Optimization

What Is This List About?
It is a collection of references to papers about optimization problems that are better solved by a combination of optimization techniques, rather than using any particular technique in isolation.

Why Create This List?
People often ask me what makes a problem more suitable for a hybrid/integrated approach. Although I think this question still does not have a good general answer, there are many examples illustrating the power of integration. As our experience grows and we collect a larger body of empirical evidence, we will improve our understanding of the underlying problem characteristics that favor an integrated approach. This is one of the ultimate goals of my research.

What Kinds Of Papers Appear In This List?
I am trying to group together papers that address problems for which integrated approaches deliver significant improvements in terms of development effort, solution time, resource requirements (e.g. memory), and so on.

Why Is XYZ's Paper Not In This List?
I am trying to keep this list updated, and as complete as possible, to the best of my knowledge and time availability. I know that many relevant papers are not listed below. If you know a paper that should be included here, please let me know and I will be happy to add it to the list.

Credits: The first version of this list was based on a table compiled by John N. Hooker in 2005.

Papers are divided into categories, depending on the type of integration, and are listed chronologically and sorted alphabetically by first author's last name within a year.

---

Loose Integration of CP and MILP

• Author(s): Hajian et al. (1996)
  Problem: British Airways fleet assignment. CP solver provides starting feasible solution to MILP.
  Improvement: Twice as fast as MILP; 4 times faster than CP.
  
  

CP + MILP-style Relaxations

• Author(s): Focacci, Lodi and Milano (1999)
  Problem: Lesson timetabling. Reduced-cost variable fixing using an assignment problem relaxation.
  Improvement: 2 to 50 times faster than CP.
  
  
• Author(s): Hooker and Osorio (1999)
  Problem: Boat party scheduling and flow shop scheduling. Logic processing plus linear relaxation.
  Improvement: Solved 10-boat instance in 5 minutes that MILP could not solve in 12 hours. Solved flow shop instances 4 times faster than MILP.
  
  
• Author(s): Refalo (1999)
  Problem: Piecewise linear costs.
  Improvement: 2 to 200 times faster than MILP. Solved two instances that MILP could not solve.
  
  
• Author(s): Bollapragada, Ghattas and Hooker (2001)
  Problem: Nonlinear structural design. Logic processing plus convex relaxation.
  Improvement: Up to 600 times faster than MILP. Solved 2 problems in less than 6 minutes that MILP could not solve in 20 hours.
  
  
• Author(s): Sellmann and Fahle (2001)
  Problem: Automatic digital recording. CP plus Lagrangean relaxation.
  Improvement: 1 to 10 times faster than MILP, which was faster than CP.
  
  
• Author(s): Thorsteinsson and Ottosson (2001)
  Problem: Product configuration.
  Improvement: 30 to 40 times faster than MILP, which was faster than CP.
  
  
• Author(s): Beck and Refalo (2003)
  Problem: Scheduling with earliness and tardiness costs.
  Improvement: Solved 67 out of 90 instances, while CP solved only 12.
  
  
• Author(s): Van Hoeve (2003)
  Problem: Stable set problems. CP plus semi-definite programming relaxation.
  Improvement: Significantly better suboptimal solutions than CP in a fraction of the time.
  
  

CP-based Branch-and-Price

• Author(s): Easton, Nemhauser and Trick (2002)
  Problem: Traveling tournament scheduling (baseball).
  Improvement: First to solve 8-team instance to optimality.
  
  
• Author(s): Yunes, Moura and de Souza (2005)
  Problem: Urban transit crew scheduling.
  Improvement: Solved problems with up to 210 trips, while traditional branch-and-price could accommodate only 120 trips.
  
  

Integration of CP and MILP in Benders Decomposition

• Author(s): Jain and Grossmann (2001)
  Problem: Min-cost planning and disjunctive scheduling. MILP master problem and CP subproblem.
  Improvement: 20 to 1000 times faster than CP and MILP.
  
  
• Author(s): Thorsteinsson (2001)
  Problem: Same as Jain and Grossmann (2001) problems. Branch-and-check.
  Improvement: An additional factor of 10 over Jain and Grossmann (2001).
  
  
• Author(s): Benoist, Gaudin and Rottembourg (2002)
  Problem: Call center scheduling. CP master, LP subproblem.
  Improvement: Solved twice as many instances as traditional Benders.
  
  
• Author(s): Timpe (2002)
  Problem: Polypropylene batch scheduling at BASF. MILP master, CP subproblem.
  Improvement: Solved previously insoluble problem in 10 minutes.
  
  
• Author(s): Hooker (2004)
  Problem: Min-cost and min-makespan planning and cumulative scheduling. MILP master, CP subproblem.
  Improvement: 100 to 1000 times faster than CP and MILP.
  
  
• Author(s): Hooker (2005)
  Problem: Min-tardiness planning and cumulative scheduling. MILP master, CP subproblem.
  Improvement: 10 to over 1000 times faster than CP and MILP when minimizing number of late jobs; roughly 10 times faster when minimizing total tardiness; much better solutions when suboptimal.
  
  
• Author(s): Rasmussen and Trick (2005)
  Problem: Sports scheduling to minimize number of consecutive home or away games.
  Improvement: Speedup of several orders of magnitude compared to previous state of the art.
  
  

References

• C. Beck and P. Refalo. A hybrid approach to scheduling with earliness and tardiness costs. Annals of Operations Research, 118:49-71, 2003.
  
  
• T. Benoist, E. Gaudin and B. Rottembourg. Constraint programming contribution to benders decomposition: A case study. Proceedings of the Eigth International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science 2470, 603-617, 2002.
  
  
• S. Bollapragada, O. Ghattas and J. N. Hooker. Optimal design of truss structures by mixed logical linear programming. Operations Research 49(1):42-51, 2001.
  
  
• K. Easton, G. Nemhauser and M. Trick. Solving the traveling tournament problem: A combined integer programming and constraint programming approach. Proceedings of the Fourth International Conference on the Practice and Theory of Automated Timetabling (PATAT), 2002.
  
  
• F. Focacci, A. Lodi and M. Milano. Cost-based domain filtering. Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science 1713, 189-203, 1999.
  
  
• M. T. Hajian, H. El-Sakkout, M. Wallace, J. M. Lever and E. B. Richards. Toward a closer integration of finite domain propagation and simplex-based algorithms. Proceedings of the Fourth International Symposium on Artificial Intelligence and Mathematics, 1996.
  
  
• J. N. Hooker. A hybrid method for planning and scheduling. Proceedings of the Tenth International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science 3258, 305-316, 2004.
  
  
• J. N. Hooker. A hybrid method for planning and scheduling. To appear in Constraints, 2005.
  
  
• J. N. Hooker and M. A. Osorio. Mixed logical/linear programming. Discrete Applied Mathematics 96-97(1-3):395-442, 1999.
  
  
• V. Jain and I. E. Grossmann. Algorithms for hybrid MILP/CP models for a class of optimization problems. INFORMS Journal on Computing 13(4):258-276, 2001.
  
  
• R. Rasmussen and M. Trick. A benders approach for the minimum break scheduling problem. Presented at the INFORMS National Meeting in San Francisco, California, 2005.
  
  
• P. Refalo. Tight cooperation and its application in piecewise linear optimization. Proceedings of the Fifth International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science 1713, 375-389, 1999.
  
  
• M. Sellmann and T. Fahle. Constraint programming based lagrangean relaxation for a multimedia application. Proceedings of the Third International Workshop on Integration of AI and OR techniques in Constraint Programming for Combinatorial Optimization Problems (CP-AI-OR), 2001.
  
  
• E. S. Thorsteinsson. Branch-and-Check: A hybrid framework for integrating mixed integer programming and constraint logic programming. Proceedings of the Seventh International Conference on Principles and Practice of Constraint Programming. Lecture Notes in Computer Science 2239, 16-30, 2001.
  
  
• E. S. Thorsteinsson and G. Ottosson. Linear relaxations and reduced-cost based propagation of continuous variable subscripts. Annals of Operations Research 115:15-29, 2001.
  
  
• C. Timpe. Solving planning and scheduling problems with combined integer and constraint programming. OR Spectrum 24:431-448, 2002.
  
  
• W. J. Van Hoeve. A hybrid constraint programming and semidefinite programming approach for the stable set problem. Proceedings of the Ninth International Conference on Principles and Practice of Constraint Programming (CP). Lecture Notes in Computer Science 2833, 407-421, 2003.
  
  
• T. H. Yunes, A. V. Moura and C. C. de Souza. Hybrid column generation approaches for urban transit crew management problems. Transportation Science 39(2):273-288, 2005.