This blog is part 2 of our series on Mosel Guidelines for working with general constraints. In case you missed it, make sure to check out part 1.
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 and are hence easier to understand and maintain. Furthermore, the MIP solver can exploit the structure for efficient handling when solving the problem.
This blog is the second in 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.
This blog discusses the formulation of piecewise linear constraints with Xpress Mosel. Note that functionality for adding piecewise linear constraints is available throughout the different APIs and user interfaces to Xpress. Most notably, you can use XPRSaddpwlconsif you are a user of the C/C++ API or problem.addpwlconsif you are a user of the Python interface.
Piecewise Linear Constraints:
A piecewise linear expression is a collection of linear segments. We can distinguish several cases:
1. A monotonously increasing continuous piecewise linear function (the typical case of cost or price functions, also known as incremental price breaks)
2. A piecewise linear function that is not continuous (all item price breaks)
3. A continuous piecewise linear function of arbitrary shape (the typical case where a piecewise linear function is used to approximate a nonlinear function)
Incremental price breaks
When buying a certain number of items, we get discounts incrementally.
Example:
Formulation options for this case include: Special Ordered Set of type 2 (SOS2), binary variables, or piecewise linear expressions (see also the discussion in ‘MIP formulations quick reference’ and example files pricebrinc*.mos).
Formulation via SOS2:
For the Mosel implementation of the cost expression, we have the choice between 3 different forms that result in the same piecewise linear constraints
Note that for all forms of pwlin the curve continues beyond the first and last breakpoint, prolongating the first and last segments to infinity.
All items discount
When buying a certain number of items, we get discounts on all items. The price bands with costs per unit are determined by the total quantity bought.
Example:
Formulation options include Special Ordered Sets of type 1 (SOS1), binary variables, or a piecewise linear expression (see also the discussion in ‘MIP formulations quick reference’ and example files pricebrai*.mos)
Using the same declarations as in the previous example, the Mosel formulation as piecewise linear expression can take 2 equivalent forms that result internally in the same constraint formulation:
Specification as a list of piecewise linear segmentswith associated intervals:
Specification as a list of points:
The solver representation is a continuous line: at ’jumps’ any intermediate value might occur:
Approximating univariate non-linear functions
We can model non-linear functions in the same way as incremental price breaks by approximating the non-linear function with a piecewise linear function.
Example:
Formulation options for this case include the use of an SOS2 or a piecewise linear expression (see example files approx*.mos).
For the formulation as piecewise linear expression with Mosel we need to use the most generic form namely the
The world is nonlinear
We have seen that piecewise linear expressions can be used to represent approximations of nonlinear functions in a single variable. If the data points are not fixed upfront, determining a suitable set of break points for the piecewise linear approximation is a (nonlinear) optimization problem on its own (expfita.mos), but often satisfactory approximations can be obtained by working with sufficiently fine-grained predetermined grid points (catenary.mos, minsurf.mos).
What if the function that we wish to approximate has more than a single variable as its argument? For two-dimensional cases it may still be practical to work with SOS-based formulations (see the example Non-linear function in two variables), however anything "more nonlinear" may call for a direct representation using nonlinear expressions and hence a solver that can cope with other constraint types. The Mosel language allows its users to write nonlinear constraints in quite a natural extension to what you are used to from working with linear constraints. You need to load the solver module 'mmxnlp' that will automatically select the solver among the available Xpress solvers that is best suited for the type of nonlinearities that are contained in your problem (defaulting to the LP or MIP optimizer if the problem is found to be linear).
A caveat nevertheless: nonlinear solution methods work differently from LP and MIP techniques, for example, the general nonlinear solvers of the Xpress suite are local solvers, that is, the generated solution may only be locally optimal. Also, nonlinear solvers may not be able to solve quite as large problem sizes as what you are used to from MIP or LP solvers.
For more detail on this topic, please refer to the ‘MIP formulations Quick Reference’. Don’t forget to subscribe to our Optimization Blog to be notified about Part 3 of this series on logical constraints: ‘and’ and ‘or’ over Boolean variables.
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 and are hence easier to understand and maintain. Furthermore, the MIP solver can exploit the structure for efficient handling when solving the problem.
This blog is the second in 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.
This blog discusses the formulation of piecewise linear constraints with Xpress Mosel. Note that functionality for adding piecewise linear constraints is available throughout the different APIs and user interfaces to Xpress. Most notably, you can use XPRSaddpwlconsif you are a user of the C/C++ API or problem.addpwlconsif you are a user of the Python interface.
Piecewise Linear Constraints:
A piecewise linear expression is a collection of linear segments. We can distinguish several cases:
1. A monotonously increasing continuous piecewise linear function (the typical case of cost or price functions, also known as incremental price breaks)
2. A piecewise linear function that is not continuous (all item price breaks)
3. A continuous piecewise linear function of arbitrary shape (the typical case where a piecewise linear function is used to approximate a nonlinear function)
Incremental price breaks
When buying a certain number of items, we get discounts incrementally.
Example:
Formulation options for this case include: Special Ordered Set of type 2 (SOS2), binary variables, or piecewise linear expressions (see also the discussion in ‘MIP formulations quick reference’ and example files pricebrinc*.mos).
Formulation via SOS2:
- we associate real valued decision variables wiwith the quantity break points Bi
- the implementation with Mosel employs the ‘makesos2’ subroutine (the alternative formulation via ‘is_sos2’ cannot be used here due to the 0-valued coefficient of w0):
Formulation as piecewise linear expression:
- No additional decision variables are required in this case, however, the constraints resulting from the ‘pwlin’ modeling construct in Mosel – just like those resulting from ‘fmin’, ’fmax’, and ‘abs’ discussed in the preceding blog in this series – are of type ‘nlctr’: they require the module mmxnlp but will result in MIP models given that they only involve linear expressions.
For the Mosel implementation of the cost expression, we have the choice between 3 different forms that result in the same piecewise linear constraints
- specification as a list of slopeswith associated intervals: (with Mosel only points of slope changes are specified, the start value is 0):
- specification as a list of piecewise linear segments (pws)with associated intervals:
- specification as a list of points:
Note that for all forms of pwlin the curve continues beyond the first and last breakpoint, prolongating the first and last segments to infinity.
All items discount
When buying a certain number of items, we get discounts on all items. The price bands with costs per unit are determined by the total quantity bought.
Example:
Formulation options include Special Ordered Sets of type 1 (SOS1), binary variables, or a piecewise linear expression (see also the discussion in ‘MIP formulations quick reference’ and example files pricebrai*.mos)
Using the same declarations as in the previous example, the Mosel formulation as piecewise linear expression can take 2 equivalent forms that result internally in the same constraint formulation:
Specification as a list of piecewise linear segmentswith associated intervals:
Specification as a list of points:
The solver representation is a continuous line: at ’jumps’ any intermediate value might occur:
Approximating univariate non-linear functions
We can model non-linear functions in the same way as incremental price breaks by approximating the non-linear function with a piecewise linear function.
Example:
Formulation options for this case include the use of an SOS2 or a piecewise linear expression (see example files approx*.mos).
For the formulation as piecewise linear expression with Mosel we need to use the most generic form namely the
- specification as a list of points:
The world is nonlinear
We have seen that piecewise linear expressions can be used to represent approximations of nonlinear functions in a single variable. If the data points are not fixed upfront, determining a suitable set of break points for the piecewise linear approximation is a (nonlinear) optimization problem on its own (expfita.mos), but often satisfactory approximations can be obtained by working with sufficiently fine-grained predetermined grid points (catenary.mos, minsurf.mos).
What if the function that we wish to approximate has more than a single variable as its argument? For two-dimensional cases it may still be practical to work with SOS-based formulations (see the example Non-linear function in two variables), however anything "more nonlinear" may call for a direct representation using nonlinear expressions and hence a solver that can cope with other constraint types. The Mosel language allows its users to write nonlinear constraints in quite a natural extension to what you are used to from working with linear constraints. You need to load the solver module 'mmxnlp' that will automatically select the solver among the available Xpress solvers that is best suited for the type of nonlinearities that are contained in your problem (defaulting to the LP or MIP optimizer if the problem is found to be linear).
A caveat nevertheless: nonlinear solution methods work differently from LP and MIP techniques, for example, the general nonlinear solvers of the Xpress suite are local solvers, that is, the generated solution may only be locally optimal. Also, nonlinear solvers may not be able to solve quite as large problem sizes as what you are used to from MIP or LP solvers.
For more detail on this topic, please refer to the ‘MIP formulations Quick Reference’. Don’t forget to subscribe to our Optimization Blog to be notified about Part 3 of this series on logical constraints: ‘and’ and ‘or’ over Boolean variables.
Updated 5 years ago
Version 3.0