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.

Speed versus expressiveness

The API allows writing constraints in very expressive ways. However, the most expressive way is not always the fastest way. If the time to create your model becomes a bottleneck then you can find some potential improvements here.

Duplicate terms

The Optimizer's C library and API do not allow the same variable to appear multiple times in the same row. If this happens then the Optimizer will raise an error. The C++ API allows this since this can easily happen when creating expressions in object oriented form. Consequently, the API must merge duplicate entries before submitting rows to the Optimizer's low level C API. This merging can take time.

If you know that in your code you will never produce duplicate terms then you can use functions setCreateLists(true) of class LinExpression and setAutoCompress(false) of class LinTermList (and similarly for QuadExpression and QuadExpression) to tell the API about this. With this linear/quadratic expressions are represented by lists by default. Any non-zero added to such an expression is just appended to the list. When the expression is finally converted to a linear constraint, the list is not scanned for duplicates but non-zeros are committed from the list to the C library as-is. This avoids any overhead for sorting indices and merging duplicates.

Function sum() versus explicit expression building

The sum() function allows for writing easy to read code when creating sums. It requires creation of a good number of small objects, especially if you use lambdas. This can slow things down and creating an explicit expression may be faster in some cases.

Consider this example code:

sum(I, [&](auto i) { return a[i] * x[i]; });

The same expression can be created explicitly:

LinExpression expr = LinExpression::create();
for (int i : I) expr.addTerm(a[i], x[i]);

Using explicit expressions can be faster than building them up with the sum function.

Size of temporary buffers

When building up sums and when submitting data to the Optimizer's low level API, the C++ API uses temporary buffers to collect and/or transform data. These buffers start out small and will grow as needed. If you build large sums and/or large constraints then this may result in a lot of buffer reallocations.

These reallocations can be reduced/avoided if you can tell the API how long your buffers and constraints are going to be.

In order to configure the expected size of constraints, use functions

• setNonzeroThreshold() in class XPRSProblem.RowCreator
• setInitialNonzeros() in class XPRSProblem.ConstraintCreator
• setInitialInequalities() in class XPRSProblem.ConstraintCreator

In order to create expressions with a non-default initial buffer size use the overloads for LinExpression::create() and QuadExpression::create() that allow a capacity argument. For example,

LinExpression::create(0.0, 100);

will prepare the expression to allow addition of 100 terms without reallocation of internal buffers.

Note that creating expressions with an initial capacity is only meaningful for expressions that are implemented by lists. For expressions that are implemented as maps, the initial capacity argument is ignored.