[Previous chapter] [Next chapter]

Integer Programming

Though many systems can accurately be modeled as Linear Programs, there are situations where discontinuities are at the very core of the decision making problem. There seem to be three major areas where non-linear facilities are required

where entities must inherently be selected from a discrete set;

in modeling logical conditions; and

in finding the global optimum over functions.

Mosel lets you model these non-linearities using a range of discrete (global) entities and then the Xpress-MP Mixed Integer Programming (MIP) optimizer can be used to find the overall (global) optimum of the problem. Usually the underlying structure is that of a Linear Program, but optimization may be used successfully when the non-linearities are separable into functions of just a few variables.

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-MP 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, a small example follows. The first formulation uses binary variables. This formulation is then modified to use Special Ordered Sets.

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

A project planning model

A company has several projects that it must undertake in the next few months. Each project lasts for a given time (its duration) and uses up one resource as soon as it starts. The resource profile is the amount of the resource that is used in the months following the start of the project. For instance, project 1 uses up 3 units of resource in the month it starts, 4 units in its second month, and 2 units in its last month.

The problem is to decide when to start each project, subject to not using more of any resource in a given month than is available. The benefit from the project only starts to accrue when the project has been completed, and then it accrues at BEN_p per month for project p, up to the end of the time horizon. Below, we give a mathematical formulation of the above project planning problem, and then display the Mosel model form.

Model formulation

Let PROJ denote the set of projects and MONTHS={1,...,NM} the set of months to plan for. The data are:

DUR_p the duration of project p

RESUSE_pt the resource usage of project p in its t^th month

RESMAX_m the resource available in month m

BEN_p the benefit per month when project finishes

We introduce the binary decision variables start_pm that are 1 if project p starts in month m, and 0 otherwise.

The objective function is obtained by noting that the benefit coming from a project only starts to accrue when the project has finished. If it starts in month m then it finishes in month m+DUR_p-1. So, in total, we get the benefit of BEN_p for NM-(m + DUR_p-1) = NM - m - DUR_p+1 months. We must consider all the possible projects, and all the starting months that let the project finish before the end of the planning period. For the project to complete it must start no later than month NM-DUR_p. Thus the profit is:

_{p PROJ}

^NM-DUR_p

_{m = 1}

(BEN_p · (NM-m-DUR_p+1)) · start_pm

Each project must be done once, so it must start in one of the months 1 to NM-DUR_p:

p PROJ:

_{m MONTHS}

start_pm = 1

We next need to consider the implications of the limited resource availability each month. Note that if a project p starts in month m it is in its (k-m+1)^th month in month k, and so will be using RESUSE_p,k-m+1 units of the resource. Adding this up for all projects and all starting months up to and including the particular month k under consideration gives:

k MONTHS:

_{p PROJ}

^k

_{m = 1}

RESUSE_p,k+1-m · start_pm RESMAX_k

Finally we have to specify that the start_pm are binary (0 or 1) variables:

p PROJ, m MONTHS: start_pm {0,1}

Note that the start month of a project p is given by:

^NM-DUR_p

_{m = 1}

m · start_pm

since if an start_pm is 1 the summation picks up the corresponding m.

Implementation

The model as specified to Mosel is as follows (file pplan.mos):
model Pplan 
 uses "mmxprs"

 declarations
  PROJ = 1..3                      ! Set of projects
  NM = 6                           ! Time horizon (months)
  MONTHS = 1..NM                   ! Set of time periods (months) to plan for
 
  DUR: array(PROJ) of integer      ! Duration of project p
  RESUSE: array(PROJ,MONTHS) of integer 
                                   ! Res. usage of proj. p in its t'th month
  RESMAX: array(MONTHS) of integer ! Resource available in month m
  BEN: array(PROJ) of real         ! Benefit per month once project finished
 
  start: array(PROJ,MONTHS) of mpvar  ! 1 if proj p starts in month t, else 0
 end-declarations

 DUR   :: [3, 3, 4]
 RESMAX:: [5, 6, 7, 7, 6, 6]
 BEN   :: [10.2, 12.3, 11.2]
 RESUSE:: (1,1..3)[3, 4, 2]
 RESUSE:: (2,1..3)[4, 1, 5]
 RESUSE:: (3,1..4)[3, 2, 1, 2]     ! Other RESUSE entries are 0 by default

! Objective: Maximize Benefit
! If project p starts in month t, it finishes in month t+DUR(p)-1 and 
! contributes a benefit of BEN(p) for the remaining NM-(t+DUR(p)-1) months:
 MaxBen:= 
  sum(p in PROJ, m in 1..NM-DUR(p)) (BEN(p)*(NM-m-DUR(p)+1)) * start(p,m)

! Each project starts once and only once:  
 forall(p in PROJ) One(p):= sum(m in MONTHS) start(p,m) = 1

! Resource availability:
! A project starting in month m is in its k-m+1'st month in month k: 
 forall(k in MONTHS) ResMax(k):=
  sum(p in PROJ, m in 1..k) RESUSE(p,k+1-m)*start(p,m) <= RESMAX(k)

! Make all the start variables binary
 forall(p in PROJ, m in MONTHS) start(p,m) is_binary

 maximize(MaxBen)                   ! Solve the MIP-problem

 writeln("Solution value is: ", getobjval)
 forall(p in PROJ) writeln( p, " starts in month ", 
                            getsol(sum(m in 1..NM-DUR(p)) m*start(p,m)) )
end-model
Note that in the solution printout we apply the getsol function not to a single variable but to a linear expression.

The project planning model using Special Ordered Sets

The example can be modified to use Special Ordered Sets of type 1 (SOS1). The start_pm variables for a given p form a set of variables which are ordered by m, the month. The ordering is induced by the coefficients of the start_pm in the specification of the SOS. For example, start_p1's coefficient, 1, is less than start_p2's, 2, which in turn is less than start_p3's coefficient, and so on The fact that the start_pm variables for a given p form a set of variables is specified to Mosel as follows:
(! Define SOS-1 sets that ensure that at most one start(p,m) is non-zero
   for each project p. Use month index to order the variables !)

 forall(p in PROJ) XSet(p):= sum(m in MONTHS) m*start(p,m) is_sos1
The is_sos1 specification tells Mosel that Xset(p) is a Special Ordered Set of type 1. The linear expression specifies both the set members and the coefficients that order the set members. It says that all the start_pm variables for m in the MONTHS index range are members of an SOS1 with reference row entries m.

The specification of the start_pm as binary variables must now be removed. The binary nature of the start_pm is implied by the SOS1 property, since if the start_pm must add up to 1 and only one of them can differ from zero, then just one is 1 and the others are 0.

If the two formulations are equivalent why were Special Ordered Sets invented, and why are they useful? The answer lies in the way the reference row gives the search procedure in Integer Programming (IP) good clues as to where the best solution lies. Quite frequently the Linear Programming (LP) problem that is solved as a first approximation to an Integer Program gives an answer where start_p1 is fractional, say with a value of 0.5, and start_p,NM takes on the same fractional value. The IP will say:

`my job is to get variables to 0 or 1. Most of the variables are already there so I will try moving xp1 or xpT. Since the set members must add up to 1.0, one of them will go to 1, and one to 0. So I think that we start the project either in the first month or in the last month.'

A much better guess is to see that the start_pm are ordered and the LP solution is telling us it looks as if the best month to start is somewhere midway between the first and the last month. When sets are present, the IP can branch on sets of variables. It might well separate the months into those before the middle of the period, and those later. It can then try forcing all the early start_pm to 0, and restricting the choice of the one start_pm that can be 1 to the later start_pm. It has this option because it now has the information to `know' what is an early and what is a late start_pm, whereas these variables were unordered in the binary formulation.

The power of the set formulation can only really be judged by its effectiveness in solving large, difficult problems. When it is incorporated into a good IP system such as Xpress-MP it is often found to be an order of magnitude better than the equivalent binary formulation for large problems.

[Next] [Index]

If you have any comments or suggestions about these pages, please send mail to docs@dashoptimization.com.

DUR_p	the duration of project p
RESUSE_pt	the resource usage of project p in its t^th month
RESMAX_m	the resource available in month m
BEN_p	the benefit per month when project finishes