Integer Programming entities in Mosel

We shall show how to make variables and sets of variables into global entities by using the following declarations.

 declarations
  IR = 1..8                       ! Index range
  WEIGHT: array(IR) of real       ! Weight table
  x: array(IR) of mpvar
 end-declarations

 WEIGHT:: [ 2, 5, 7, 10, 14, 18, 22, 30]

Xpress handles the following global entities:

Binary variables: decision variables that can take either the value 0 or the value 1 (do/ don't do variables).
We make a variable, say x(4), binary by
```
x(4) is_binary
```
Integer variables: decision variables that can take only integer values.
We make a variable, say x(7), integer by
```
x(7) is_integer
```
Partial integer variables: decision variables that can take integer values up to a specified limit and any value above that limit.
```
x(1) is_partint 5   ! Integer up to 5, then continuous
```
Semi-continuous variables: decision variables that can take either the value 0, or a value between some lower limit and upper limit. Semi-continuous variables help model situations where if a variable is to be used at all, it has to be used at some minimum level.
```
x(2) is_semcont 6   ! A 'hole' between 0 and 6, then continuous
```
Semi-continuous integer variables: decision variables that can take either the value 0, or an integer value between some lower limit and upper limit. Semi-continuous integer variables help model situations where if a variable is to be used at all, it has to be used at some minimum level, and has to be integer.
```
x(3) is_semint 7    ! A 'hole' between 0 and 7, then integer
```
Special Ordered Sets of type one (SOS1): an ordered set of non-negative variables at most one of which can take a non-zero value.
Special Ordered Sets of type two (SOS2): an ordered set of non-negative variables, of which at most two can be non-zero, and if two are non-zero these must be consecutive in their ordering. If the coefficients in the WEIGHT array determine the ordering of the variables, we might form a SOS1 or SOS2 set MYSOS by
```
MYSOS:= sum(i in IRng) WEIGHT(i)*x(i) is_sosX
```
where is_sosX is either is_sos1 for SOS1 sets, or is_sos2 for SOS2 sets.
Alternatively, if the set S holds the members of the set and the linear constraint L contains the set variables' coefficients used in ordering the variables (the so-called reference row entries), then we can do thus:
```
makesos1(S,L)
```
with the obvious change for SOS2 sets. This method must be used if the coefficient (here WEIGHT(i)) of an intended set member is zero. With is_sosX the variable will not appear in the set since it does not appear in the linear expression.
Another point to note about Special Ordered Sets is that the ordering coefficients must be distinct (or else they are not doing their job of supplying an order!).

The most commonly used entities are binary variables, which can be employed to model a whole range of logical conditions. General integers are more frequently found where the underlying decision variable really has to take on a whole number value for the optimal solution to make sense. For instance, we might be considering the number of airplanes to charter, where fractions of an airplane are not meaningful and the optimal answer will probably involve so few planes that rounding to the nearest integer may not be satisfactory.

Partial integers provide some computational advantages in problems where it is acceptable to round the LP solution to an integer if the optimal value of a decision variable is quite large, but unacceptable if it is small. Semi-continuous variables are useful where, if some variable is to be used, its value must be no less than some minimum amount. If the variable is a semi-continuous integer variable, then it has the added restriction that it must be integral too.

Special Ordered Sets of type 1 are often used in modeling choice problems, where we have to select at most one thing from a set of items. The choice may be from such sets as: the time period in which to start a job; one of a finite set of possible sizes for building a factory; which machine type to process a part on. Special Ordered Sets of type 2 are typically used to model non-linear functions of a variable. They are the natural extension of the concepts of Separable Programming, but when embedded in a Branch-and-Bound code (see below) enable truly global optima to be found, and not just local optima. (A local optimum is a point where all the nearest neighbors are worse than it, but where we have no guarantee that there is not a better point some way away. A global optimum is a point which we know to be the best. In the Himalayas the summit of K2 is a local maximum height, whereas the summit of Everest is the global maximum height).

Theoretically, models that can be built with any of the entities we have listed above can be modeled solely with binary variables. The reason why modern IP systems have some or all of the extra entities is that they often provide significant computational savings in computer time and storage when trying to solve the resulting model. Most books and courses on Integer Programming do not emphasize this point adequately. We have found that careful use of the non-binary global entities often yields very considerable reductions in solution times over ones that just use binary variables.

To illustrate the use of Mosel in modeling Integer Programming problems, two small examples follow. The first example is initially formulated using binary variables. This formulation is then modified to use Special Ordered Sets of type 1. For the second example we show a formulation via Special Ordered Sets of type 2 and also a simplified representation via 'piecewise linear' constructs.

For the interested reader, an excellent text on Integer Programming is Integer Programming by Laurence Wolsey, Wiley Interscience, 1998, ISBN 0-471-28366-5.

Contents

Index

Glossary

Search Results

Integer Programming entities in Mosel