Linear relaxations
Constraint Programming and Mathematical Programming (here used for Linear and Mixed Integer Programming, LP/MIP) are two different approaches to solving optimization problems that have a number of complementary features. Some problems, or parts of problems, are better solved by CP, others by LP/MIP techniques. Based on this observation it is possible to devise various approaches for hybrid CP-MP problem solving. The FICO Xpress Optimization whitepaper 'Hybrid MIP/CP solving with Xpress Optimizer and Xpress Kalis' describes several decomposition schemes where coordination between MIP and CP models is done on the Mosel level. Xpress Kalis now provides a built-in linear programming relaxation functionality where communication and cooperation take place directly on the solver level, with optional configuration and user interaction from the Mosel CP model.
In the context of Xpress Kalis we use the term linear relaxation for sets of linear (in)equality constraints that are solved by an external LP/MIP solver. In the case of an automatic relaxation this will be a reformulation of (a subset of) the constraints in the CP problem. A user-defined 'linear relaxation', however, may also include additional information, in which case this name choice might be somewhat misleading.
Xpress Kalis can build automatically several linear (or mixed integer linear) relaxations of a CP problem and use Xpress Optimizer to solve them. Xpress Kalis uses a double modeling approach (as in [Hei98]) by exchanging automatically and in a bidirectional way, information such as objective bounds, infeasibility, optimal relaxed solutions and reduced costs between the CP solver and the linear relaxations solver(s) during the search for a solution.
- Linear relaxations can be generated fully automatically.
- Alternatively, relaxations can be configured by selecting sets of constraints to form subproblems and by defining their solving frequency.
- Relaxation problems can also be defined freely by the user; they may even include constraints that do not occur in the original CP problem.
These three ways of defining linear relaxations are presented in the following sections.