Introduction

Topics covered in this section:

This quick reference guide presents a collection of MIP model formulations for Xpress Optimizer, including standard linearization techniques involving binary variables, the use of more specific modeling objects such as SOS and partial integer variables, and reformulations of logic constraints through indicator constraints.

Integer Programming entities supported in Xpress

• Binary variables (BV) – decision variables that must take either the value 0 or the value 1, sometimes called 0/1 variables;
• Integer variables (UI) – decision variables that must take on integer values. Some upper limit must be specified;
• Partial integer variables (PI) – decision variables that must take integer values below a specified limit but can take any value above that limit;
• Semi-continuous variables (SC) – decision variables that must take on either the value 0, or any value in a range whose lower an upper limits are specified. SCs help model situations where, if a variable is to be used at all, it has to be at some minimum level;
• Semi-continuous integer variables (SI) – decision variables that must take either the value 0, or any integer value in a range whose lower and upper limits are specified;
• Special ordered sets of type one (SOS1) – an ordered set of variables of which at most one can take a nonzero value;
• Special ordered sets of type two (SOS2) – an ordered set of variables of which at most two can be nonzero, and if two are nonzero, they must be consecutive in their ordering.

Remarks

• The solution values of binary and integer variables are real valued, not integer valued.
• At an optimal MIP solution, the actual values of the binary and integer variables will be integer – to within a certain tolerance.

Integer Programming entities in Mosel

Definition: integer programming types are defined as unary constraints on previously declared decision variables of type mpvar; name the constraints if you want to be able to access/modify them.

declarations
  d: mpvar
  ifmake: array(PRODS,LINES) of mpvar
  x: mpvar
 end-declarations

 d is_binary                      ! Single binary variable
 forall(p in PRODS, l in LINES)
  ifmake(p,l) is_binary           ! An array of binaries

 ACtr:= x is_integer              ! An integer variable
 x >= MINVAL                      ! Lower bound on the variable
 x <= MAXVAL                      ! Upper bound on the variable
 ! MINVAL,MAXVAL: values between -MAX_REAL and MAX_REAL
 ...
 ACtr:= x is_partint 10           ! Change type to partial integer
 ...
 ACtr:= 0                         ! Delete constraint
! Equivalently:
 ACtr:= x is_continuous           ! Change type to continuous

Solving: with Xpress Optimizer (Mosel module mmxprs) any problem containing integer programming entities is automatically solved as a MIP problem, to solve just the LP relaxation use option XPRS_LPSTOP (if following up with MIP search) or XPRS_LIN (ignore all MIP information) for maximize / minimize.

Accessing the solution: for obtaining solution values of decision variables and linear expressions use getsol (alternative syntax: .sol); the MIP problem status is returned by the function getparam("XPRS_MIPSTATUS")

 case getparam("XPRS_MIPSTATUS") of
  XPRS_MIP_NOT_LOADED,
    XPRS_MIP_LP_NOT_OPTIMAL: writeln("Solving not started")
  XPRS_MIP_LP_OPTIMAL:       writeln("Root LP solved")
  XPRS_MIP_UNBOUNDED:        writeln("LP unbounded")
  XPRS_MIP_NO_SOL_FOUND,
    XPRS_MIP_INFEAS:         writeln("MIP search started, no solution")
  XPRS_MIP_SOLUTION,
    XPRS_MIP_OPTIMAL:        writeln("MIP solution: ", , getobjval)
 end-case

 writeln("x: ", getsol(x))
 writeln("d: ", d.sol)

Integer Programming entities in BCL

The BCL code extracts in this document are formulated for the BCL C++ interface. The other BCL interfaces (C, Java, C#) work similarly, please refer to the Xpress BCL documentation for further detail.

Definition: Integer Programming types are specified when creating decision variables (type XPRBvar); types may be changed with setType.

 XPRBprob prob("test");
 XPRBvar d, ifmake[NP][NL], x;
 int p,l;

 d = prob.newVar("d", XPRB_BV);         // Single binary variable

 for (p = 0; p < NP; p++)               // An array of binaries
  for (l = 0; l < NL; l++)
   ifmake[p][l] = prob.newVar("ifmake", XPRB_BV);

 x = prob.newVar("x", XPRB_UI, MINVAL, MAXVAL);  // An integer variable
 // MINVAL,MAXVAL: reals between -XPRB_INFINITY and XPRB_INFINITY
 ...
 x.setType(XPRB_PI);                    // Change type to partial integer
 x.setLim(10);
 ...
 x.setType(XPRB_PL);                    // Change type to continuous

Solving: use mipOptimize, possibly preceded by setSense (the default optimization direction is minimization), to solve a problem as a MIP problem. To solve just the LP relaxation use option "l" (if following up with MIP search) or lpOptimize (ignore all MIP information).

 prob.setSense(XPRB_MINIM);
 prob.mipOptimize("");

Accessing the solution: for obtaining solution values of decision variables and linear expressions use getSol; the MIP problem status is returned by getMIPstatus.

 int mipstatus = prob.getMIPStat();
 switch (mipstatus) {
  case XPRB_MIP_NOT_LOADED:
  case XPRB_MIP_LP_NOT_OPTIMAL:
    cout << "Solving not started" << endl;
    break;
  case XPRB_MIP_LP_OPTIMAL:
    cout << "Root LP solved" << endl;
    break;
  case XPRB_MIP_UNBOUNDED:
    cout << "LP unbounded" << endl;
    break;
  case XPRB_MIP_NO_SOL_FOUND:
  case XPRB_MIP_INFEAS:
    cout << "MIP search started, no solution" << endl;
    break;
  case XPRB_MIP_SOLUTION:
  case XPRB_MIP_OPTIMAL:
    cout << "MIP solution: " << prob.getObjVal() << endl;
    break;
 }
 cout << x.getName() << ": " << x.getSol() << endl;