Mathematical Programming basics

Topics covered in this section:

model "Chess 1"
 uses "mmxprs"                    ! Use Xpress Optimizer for solving

 declarations
  xs, xl: mpvar                   ! Decision variables
 end-declarations

 Time:= 3*xs + 2*xl <= 160        ! Constraint: limit on working hours
 Wood:= xs + 3*xl <= 200          ! Constraint: raw mat. availability

 xs is_integer; xl is_integer     ! Integrality constraints

 maximize(5*xs + 20*xl)           ! Objective: maximize total profit

 writeln("Solution: ", getobjval) ! Print objective function value

 writeln("small: ", getsol(xs))   ! Print solution for xs
 writeln("large: ", getsol(xl))   ! and xl

 write("Time: ", getact(Time))    ! Constraint activity
 writeln(" ", getslack(Time))     ! and slack

end-model

Decision variables

declarations
  x, b, d: mpvar
  ifmake: array(1..10, 1..20) of mpvar
  y, z: array(1..10) of mpvar
end-declarations

mpvar means mathematical programming variable or decision variable, sometimes also just called variable. Decision variables are unknowns: they have no value until the model is run, and the optimizer finds values for the decision variables.
Variables can take values between 0 and infinity by default, other bounds may be specified:

x <= 10
y(1) = 25.5
y(2) is_free
z(2,3) >= -50
z(2,3) <= 50

Integer programming types are defined as unary constraints on previously declared decision variables

b is_binary                      ! Single binary variable
forall(p in PRODS,l in LINES)
  ifmake(p,l) is_binary          ! An array of binaries
d is_integer                     ! An integer variable
d <= 25                          ! Upper bound on the variable
x is_partint 10                  ! Partial integer (integers up to 10, continuous beyond)
y(3) is_semcont 5                ! Semi-continuous (0 or greater or equal 5)

Constraints

Constraint are declared just like decision variables, in LP/MIP problems they have type linctr – linear constraint.

declarations
  MaxCap: linctr
  Inven: array(1..10) of linctr
end-declarations

The ``value'' of a constraint entity is a linear expression of decision variables, a constraint type (≤, ≥, =), and a constant term. It is set using an assignment statement:

MaxCap := 10*x + 20*y + 30*z <= 100
Ctr(3) := 4*x(1) - 3*x(2) >= 10
Inven(2) := stock(2) = stock(1) + buy(2) - sell(2)

Objective function

An objective function is just a constraint with no constraint type.

declarations
  MinCost: linctr
end-declarations

MinCost := 10*x(1) + 20*x(2) + 30*x(3) + 40*x(4)

Optimization

minimize(MinCost)

maximize(MaxProfit)

Viewing the matrix

After defining the problem the matrix can be output to a file, to examine off line.

Problem loaded into solver (default: MPS format, use for solver tuning):

loadprob(MinCost)
writeprob("explout.mps", "")  ! MPS format
writeprob("explout.lp", "l")  ! LP format

Problem held in Mosel core (default: LP format, constraint oriented file):

exportprob("explout", MinCost)          ! LP
exportprob(EP_MPS, "explout", MinCost)  ! MPS

Useful Optimizer control settings:

setparam('XPRS_VERBOSE', true)
setparam('XPRS_LOADNAMES', true)

Viewing the solution

Always check the solution status of the problem before accessing any solution values.

if getprobstat=XPRS_OPT then
  writeln('optimal!')
else
  writeln('not optimal!')
  exit(1)
end-if

Alternatively, testing all problem states:

case getprobstat of
  XPRS_OPT: writeln('optimal')
  XPRS_INF: writeln('infeasible')
  XPRS_UNB: writeln('unbounded')
  XPRS_UNF: writeln('unfinished')
else
  writeln('unexpected problem status!')
end-case

Accessing the solution values within the model:

writeln('Maximum revenue: $', getobjval)
writeln('x(1) = ', getsol(x(1)), '  x(2) = ', x(2).sol)

Solution values of constraints: activity value + slack value = RHS

 

MaxCap := 10*x + 20*y <= 30

Activity value:

getsol(10*x + 20*y)
getact(MaxCap)

Slack value:

getsol(30 - (10*x + 20*y))
getslack(MaxCap)

Xpress Workbench: assuming that the model runs successfully, the logging pane at the bottom of the workspace reports that the run is complete. If a model has been run through the debugger, you can browse solution values of decision variables and constraints in the Debugger tab on the right side of the workspace.