Minimum, Maximum, and Absolute Value Constraints for the Formulation of MIP Problems

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 forms part 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. In this first blog we will review Minimum, maximum, and absolute value constraints. 

Minimum, Maximum, and Absolute Value Constraints: 

Here are some examples of how to work with the new constraint types in Mosel: 



Note that the constraints resulting from the modeling constructs ‘fmin’, ‘fmax’, ‘abs’, and also ‘pwlin’ for the formulation of MIP problems are of type ‘nlctr’: they require the module mmxnlp but will result in MIP models if they only involve linear expressions.

Absolute value: MIP Formulation Alternatives 

Taking the example v = |x1 – x2| we now have the following formulation alternatives with Mosel: 

• Formulation via binary variables: (besides an additional binary variable, this formulation requires the bounds on the variables x1 and x2.)  

• Formulation via indicator constraints: (this formulation also uses an additional binary variable but does not require the specification of bounds on x1 and x2.)  

• Formulation via logical constraints: (Mosel automatically transforms this formulation into a formulation via indicator constraints before problem is input to the solver. It automatically adds any required additional variables.)

• Formulation as general constraint: (most concise formulation, directly loading an ‘absolute value’ constraint to the solver.) 

Using general constraints, the number of constraints reduces from 6 to a single line and removes the explicit auxiliary binary variable d.

Maximum value: MIP Formulation Alternatives 

Similarly to what we have seen for absolute values, here are some formulation alternatives for maximum values for the example case u = max(x1, x2, x3)

• Formulation via binary variables: (one binary variable per variable in the constraint is added and we need to know the lower and upper bounds on the variables in the maximum constraint) 

• Formulation via indicator constraints: (one indicator constraint with its binary indicator variable is added per variable in the maximum constraint.) 

• Formulation via logical constraints: (the automatic reformulation of the ‘or’ relations will result in a larger number of indicator constraints than the direct use of indicators.)  

• Formulation as general constraint: (most concise formulation, ‘maximum’ constraint is handled directly by the solver.)

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 youare a user of the Python interface. 

This blog discusses several formulation alternatives for the formulation of MIP models: 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.  

Please refer to the ‘MIP formulations Quick Reference’ guide for further detail.

To learn more Piecewise linear constraints in Part 2 of this series, make sure to subscribe to our Optimization blog to be notified about new content.