More advanced features

Topics covered in this chapter:

Other constraint types

In addition to inequality constraints (which include equations and ranged rows), there are a number of other constraints that Xpress supports:

• Special ordered set constraints restrict the number of variables that can be non-zero.
• Indicator constraints conditionally enable or disable inequality constraints, based on the values of binary variables.
• Piecewise linear constraints set one variable to the result of evaluating a piecewise linear function for another variable.
• General constraints model things like absolute value, maximum or minimum of variables and values, and logical and/or between binary variables.

Creation of these constraints is described in detail below.

Special ordered set (SOS) constraints

Special ordered set (SOS) constraints specify how many and which variables in a set of variables can be non-zero. For an SOS constraint of type 1 only one variable in the set can be non-zero. For an SOS constraint of type 2 at most two variables in the set can be non-zero and non-zero variables must be adjacent.

The ordering of variables within a set is given by weights assigned to variables: variables are ordered by increasing weight values and two different variables cannot have the same weight. In many cases the order in which variables are passed to functions is already the intended one. In that case the weight argument to the functions can be nullptr. The function will then assume weights 1, 2, ...

Note that weights are not only used for ordering. Instead the actual weight values may be used by the solver algorithm when taking branching or other decisions in the solution process. Refer to the solver documentation for more details.

One way to create SOS constraints is by using the static sos(), sos1(), or sos2() function of the SOSConstraint class:

// Create an SOS1 for { x, y, z } with default weights.
using namespace xpress;
using namespace xpress::objects;
prob.addConstraint(SOS::sos(SetType.SOS1,
                            std::vector<Variable>{ x, y, z },
                            nullptr,
                            "SOS constraint"));
// Create the same SOS1
prob.addConstraint(SOS::sos1(std::vector<Variable>{ x, y, z },
                             nullptr,
                             "SOS constraint"));
// Create an SOS2 for { x, y, z } with default weights.
prob.addConstraint(SOS::sos2(std::vector<Variable>{ x, y, z },
                             nullptr,
                             "SOS constraint"));

Indicator constraints

In Xpress, indicator constraints are not represented as explicit constraints. Instead they are defined by combining an inequality r with a binary variable b. Once these two are combined, the solver will enforce a condition that if b is set then r is satisfied. If b is not set then r may be violated.

Note that the condition on variable b may be complemented. In that case r is only enforced if b is not set.

In order to set indicator variables for certain inequality constraints, use function XpressProblem::setIndicatorVariable():

Variable b = ...;
Inequality r1 = ...;
Inequality r2 = ...;
prob.setIndicatorVariable(b, true, r1);
prob.setIndicatorVariable(b, false, r2);

The above code will enforce r1 if variable b is set (has value 1) and enforce r2 if b is not set (has value 0).

The XpressProblem class also has a setIndicatorVariables function with which multiple indicators can be set with a single function call.

Another way to set indicator variables for inequalities is by using the ifThen and ifNotThen function of the Variable class. These functions create an indicator constraint with the given variable as indicator variable:

prob.addConstraint(b.ifThen(r1)); // enforce r1 if b is set
prob.addConstraint(b.ifNotThen(r2)); // enforce r2 if b is not set

Piecewise linear constraints

A piecewise linear constraint is a constraint of the form

resultant = PWL(breakpoints)(argument)

Here resultant and argument are variables and PWL(breakpoints) is a piecewise linear function specified by the given breakpoints. See the documentation of function XPRSaddpwlcons for a detailed explanation of how breakpoints are specified.

Piecewise linear constraints can be created using the pwlOf member function of class Variable (assuming that resultant and argument are instances of Variable:

std::vector<double> breakX = ...;
std::vector<double> breakY = ...;
prob.addConstraint(resultant.pwlOf(argument, breakX, breakY));
std::vector<Breakpoint> breaks = ...;
prob.addConstraint(resultant.pwlOf(argument, breaks));

General constraints

A general constraint is a constraint of the form

resultant = function(y1, y2, ..., v1, v2, ...)

where resultant is a variable, function is a function like "min", "max", "abs", "or", "and", yi are variables and vi are constant values.

General constraints can be created by invoking an appropriate member function on the resultant variable:

Variable x, y1, y2, y3;
prob.addConstraint(x.absOf(y));          // add x = |y|
prob.addConstraint(x.orOf(y1, y2));      // add x = y1 or y2
prob.addConstraint(x.andOf(y1, y2, y3)); // add x = y1 and y2 and y3
prob.addConstraint(x.maxOf(y1, y2, 4));  // add x = max(y1, y2, 4.0)
prob.addConstraint(x.minOf(y1, 2));      // add x = min(y1, 2.0)

Performance considerations

While building small to medium-sized problems, there is usually no need to consider which way is the fastest to create the problem. The speed of different strategies does not matter.

When building models with hundreds of thousands or even millions of elements, it is important to know that some methods are faster than others:

Building linear expressions

The most efficient way to build a linear expression is by creating an instance of LinExpression and then add the terms to this instance. In order to be as fast as possible, use the LinTermList class rather than the LinTermMap class (note that there are some caveats about this class, see above and in the reference documentation).

Building quadratic expressions

As with linear expressions, the most efficient way to build a quadratic expression is using QuadExpression ( QuadTermList).

Bulk operators are faster than single operations

Consider this loop:

for (int i = 0; i < n; ++i) prob.addConstraint(...);

This adds constraints one by one to the model. A more efficient way to do this is to add all constraints in one shot:

prob.addConstraints(n, [](auto i) { return ...; });

This adds exactly the same constraints in the same order but reduces interaction with the low-level code.

Accessing the matrix

Class XpressProblem is a subclass of XPRSprob. The latter provides a direct matrix-based interface to the solver. Any function in XPRSprob directly maps to a function call in the C implementation of the solver. Since XpressProblem is a subclass of XPRSprob, all these functions are also available when modeling with objects. In order to interact with a function in XPRSprob, you need the indices of the objects. These can be obtained using the getIndex() function of classes like Variable, Inequality, SOS, PWL, GeneralConstraint.

Data containers

This section contains advanced implementation details that can be ignored in most cases.

In many real world applications building of models requires some data that is organized in containers. The Xpress C++ API distinguishes mainly two types of data containers

C style arrays

C style arrays are types like int[] or int * that just point to some memory area. These arrays are just raw memory buffers. Arrays of this type are passed into the Xpress C++ API using the xpress::Array class. This class is only used for passing this kind of array. Instances of xpress::Array can be constructed from raw pointers, std::vector and std::array. So all of the following will work (because getSolution takes an Array<double> argument):

double *dataC = ...;
prob.getSolution(dataC, nullptr, 0, 2);
std::vector<double> dataV(3);
prob.getSolution(dataV, nullptr, 0, 2);
std::array<double,3> dataA;
prob.getSolution(dataA, nullptr, 0, 2);

The use of Array is typically only required when interacting with Xpress using indices.

STL (like) containers

The standard template library provides containers like std::vector, std::map, etc. The Xpress C++ API accepts any such containers. More precisely, it accepts any types that specialize std::begin() and std::end(). There are three different kind of such containers (the nomenclature resembles the Java nomenclature):

1. Collections are containers that also have a size. The size is given by a size() member function. Collections can be iterated an arbitrary number of times. In function prototypes, collections are indicated by template parameters that start with "Coll", i.e., Coll0, Coll1, etc. In addition, std::enable_if is used to make sure the argument has a size() function.
2. Iterables are like collections but are not required to have a size() functions. In function prototypes, iterables are indicated by template parameters that start with "Iter", i.e., Iter0, Iter1, etc. Note that any collection is also an iterable.
3. Streams are like iterables but can be iterated at most once (i.e. iteration is destructive). In function prototypes, streams are indicated by template parameters that start with "Strm", i.e., Strm0, Strm1, etc. Note that any collection or iterable is also a stream.