In an earlier blog about ‘Formulating Logical Constraints in MIP Models’ we have explored the various types of discrete entities for the formulation of Mixed Integer optimization problems (MIP) that are available through Mosel (namely decision variable types, Special Ordered Sets and indicator constraints).
The latest Xpress versions (Xpress Rel 8.10 and newer) provide several new modeling constructs in Mosel that allow for an easier formulation of MIP models without the need for explicit linear reformulations. These new genuinely nonlinear constructs are handled directly by the Xpress MIP solver. As a result, developers can work with concise model formulations that relate directly to the underlying business problem. Furthermore, the MIP solver can exploit the structure for efficient handling when solving the problem.
This blog is the last of a series of three contributions where we want to take a closer look at how to work with these so-called General constraints:
We are also going to present some formulation alternatives in the context of MIP problem formulations with Mosel.
Note that functionality for adding general constraints is available throughout the different APIs and user interfaces to Xpress. Most notably, you can use XPRSaddgencons()if you are a user of the C/C++ API or problem.addgencons if you are a user of the Python interface.
Logical constraints and Boolean variables
Since Mosel 2.0 the module mmxprsdefines the constraint type logctrfor indicator constraints and—in combination with advmod—for the representation of logical constraints ’and’ ,’or’, ’not’ , ’implies’ and ’xor’ (see the earlier blog in this series about ‘Formulating Logical Constraints in MIP Models’).
These constraints are transformed into indicators on the modeling level, so they result in a MIP model. Here are some examples of their use:
Mosel 5.2.2 (Xpress Rel 8.10) introduces a new type boolvarfor the formulation of logical constraints ’and’ ,’or’, ’not’. The resulting constraints are directly sent to the solver as constraints on binary variables, so they equally result in a MIP model.
boolvarand logctrcan be used for the formulation of SAT (constraint satisfaction) and MAXSAT (SAT with weighted sum objective) problems, for the formulation of the latter we need to retrieve the binary variables that are associated with the Boolean variables in order to state an algebraic expression:
Example: MIP formulations for logical constraints
The standard way of formulating logical constraints in MIP models that one usually encounters in Operations Research textbooks is to use reformulations that involve additional binary variables. However, there usually are several alternative formulation options via the different types of logical constraints. It should be noted here that it is often not possible to make any general recommendation on which formulation to use, the choice among such formulation options needs to be made by the model developer supported by tests with representative data instances for a specific problem.
The following code snippets formulate the problem of choosing among several investments projects where certain conditions apply to the permissible combinations of projects.
Please refer to the ‘MIP formulations Quick Reference’ guide for further detail on formulation alternatives for the formulation of MIP models with Xpress Mosel. If you are interested in keeping up to date with this type of content, make sure to subscribe to our Optimization blog for more information on this topic. In case you missed it, make sure to check out parts 1 and 2 of this series.
The latest Xpress versions (Xpress Rel 8.10 and newer) provide several new modeling constructs in Mosel that allow for an easier formulation of MIP models without the need for explicit linear reformulations. These new genuinely nonlinear constructs are handled directly by the Xpress MIP solver. As a result, developers can work with concise model formulations that relate directly to the underlying business problem. Furthermore, the MIP solver can exploit the structure for efficient handling when solving the problem.
This blog is the last of a series of three contributions where we want to take a closer look at how to work with these so-called General constraints:
- Minimum, maximum, and absolute value constraints
- Piecewise linear constraints
- Logical constraints: ‘and’ and ‘or’ over Boolean variables
We are also going to present some formulation alternatives in the context of MIP problem formulations with Mosel.
Note that functionality for adding general constraints is available throughout the different APIs and user interfaces to Xpress. Most notably, you can use XPRSaddgencons()if you are a user of the C/C++ API or problem.addgencons if you are a user of the Python interface.
Logical constraints and Boolean variables
Since Mosel 2.0 the module mmxprsdefines the constraint type logctrfor indicator constraints and—in combination with advmod—for the representation of logical constraints ’and’ ,’or’, ’not’ , ’implies’ and ’xor’ (see the earlier blog in this series about ‘Formulating Logical Constraints in MIP Models’).
These constraints are transformed into indicators on the modeling level, so they result in a MIP model. Here are some examples of their use:
Mosel 5.2.2 (Xpress Rel 8.10) introduces a new type boolvarfor the formulation of logical constraints ’and’ ,’or’, ’not’. The resulting constraints are directly sent to the solver as constraints on binary variables, so they equally result in a MIP model.
boolvarand logctrcan be used for the formulation of SAT (constraint satisfaction) and MAXSAT (SAT with weighted sum objective) problems, for the formulation of the latter we need to retrieve the binary variables that are associated with the Boolean variables in order to state an algebraic expression:
Example: MIP formulations for logical constraints
The standard way of formulating logical constraints in MIP models that one usually encounters in Operations Research textbooks is to use reformulations that involve additional binary variables. However, there usually are several alternative formulation options via the different types of logical constraints. It should be noted here that it is often not possible to make any general recommendation on which formulation to use, the choice among such formulation options needs to be made by the model developer supported by tests with representative data instances for a specific problem.
The following code snippets formulate the problem of choosing among several investments projects where certain conditions apply to the permissible combinations of projects.
- Formulation as binary variables.
- Formulation via indicators/logical constraints: largely the same as the previous version except for the formulation of constraint 6 where we now use an ‘xor’ constraint (that will be transformed into indicator constraints to obtain a MIP model).
- Formulation via Boolean variables: all constraints are transformed into logical relations with the exception of the last (C6b) that involves numerical coefficients and hence employs the binary variable counterpart of the Boolean variables.
- An alternative formulation via Boolean variables is the following shorthand notation: if constraints are not named it is sufficient to state the truth expression without the relational operator ‘=’ to indicate explicitly the truth value. The resulting optimization problem will be the same as the one resulting from the previous code example, this form simply provides a more concise way of stating the logical expressions.
Please refer to the ‘MIP formulations Quick Reference’ guide for further detail on formulation alternatives for the formulation of MIP models with Xpress Mosel. If you are interested in keeping up to date with this type of content, make sure to subscribe to our Optimization blog for more information on this topic. In case you missed it, make sure to check out parts 1 and 2 of this series.
Updated 5 years ago
Version 3.0