TL;DR
This paper argues that to truly harness the power of combining Constraint Programming (CP) and Linear Programming (LP) for combinatorial optimization, we need a new way of modeling problems. They propose a declarative framework where constraints themselves dictate how CP and LP can work together, leading to more efficient and elegant solutions.
What Problem Does This Paper Address?
Combinatorial optimization problems, like scheduling or resource allocation, are notoriously hard to solve. Two powerful techniques, Constraint Programming (CP) and Integer Programming (IP, a form of LP), are often used separately. CP excels at handling discrete, logical relationships and pruning search spaces, while IP is great at finding global "big picture" solutions through relaxations. The challenge is that integrating them has largely meant shoehorning one into the other's framework, which limits their combined potential. This paper aims to bridge this gap by proposing a unified modeling approach that allows CP and LP to interact more naturally and effectively.
Methods
The core of the paper is the proposal of a Mixed Logical/Linear Programming (MLLP) framework. This framework uses conditional constraints of the form h(y) -> Ax >= b, where h(y) is a discrete constraint (handled by CP) and Ax >= b is a linear inequality (handled by LP). This means that linear inequalities are only "posted" or added to the LP solver when their corresponding discrete conditions are met.
Key aspects of their approach include:
- Declarative Modeling: The focus is on how the structure of the constraints guides the integration, rather than forcing a specific solver to dominate.
- Two Constraint Stores: MLLP maintains separate stores for discrete (CP) and continuous (LP) constraints.
- Conditional Inference Agents: Special "nonprimitive" constraints (like
ElementandNogood) act as bridges, accessing information from both stores and performing inference across them. For instance, an infeasible LP solution can generate "nogoods" (logical constraints) that are added to the CP store. - Variable Subscripts: The framework naturally handles situations where indices in constraints depend on discrete variables, simplifying models.
Datasets
Not discussed in the paper. The paper uses a "simple multiple-machine scheduling problem" as a running example to illustrate their modeling framework and solution approach.
Key Insights and Ideas
- Modeling is Key: The authors strongly advocate that the biggest hurdle to effective CP-LP integration isn't the solvers themselves, but the traditional modeling languages. A new, unified modeling language is crucial.
- Conditional Constraints as the Bridge: The
h(y) -> Ax >= bstructure is a powerful way to link discrete reasoning (CP) with continuous optimization (LP). It allows LP relaxations to be built incrementally as the discrete search progresses. - CP and LP as Complementary Inference: CP prunes discrete domains, which in turn activates or deactivates linear constraints. Conversely, LP solutions (or infeasibilities) can generate new discrete constraints (nogoods) that further prune the search space.
- Simplifying Complex Models: The MLLP framework can lead to more succinct models by avoiding the need for complex, doubly-subscripted variables often required in pure IP formulations for problems with discrete choices.
Key Results
The paper doesn't present extensive empirical results with quantitative speedups on benchmark problems. Instead, it focuses on:
- Illustrating the Modeling Power: They demonstrate how their MLLP framework can elegantly model a scheduling problem, showing how it dispenses with some of the complex variables needed in traditional IP.
- Conceptual Framework: The primary contribution is the conceptual framework for integrating CP and LP through conditional constraints and a dual-constraint-store architecture.
- Algorithmic Sketch: They outline how an MLLP problem would be solved by branching on discrete variables, using CP for inference, and incrementally building and solving LP relaxations.
Limitations and Future Work
The authors acknowledge several areas for future work:
- Systematic Implementation: Developing a systematic implementation of variable subscripts and index sets.
- Leveraging LP Solutions: Fully exploiting the LP solution at each node, beyond just feasibility.
- Branching on Continuous Variables: Extending the framework to handle branching on continuous variables and propagating continuous constraints, not just discrete ones.
- Efficiency of Nonprimitive Constraints: Further research into the efficiency and implementation of the proposed nonprimitive constraints (like
ElementandNogood).
Summary updated