---

Lesson 1
The basics of Linear Programming, XPRESS & Mosel

---

I. Setting up XPRESS

I./1. XPRESS Software Downloads

Windows 64-bit
Linux Intel 64-bit (RHEL7+ & Ubuntu)
Linux ARM 64-bit
macOS Intel 64-bit
macOS ARM 64-bit

I./2. Remote run softwares

WinSCP download site
PuTTY download site

I./3. Running an XPRESS Mosel (.mos) file remotely

The above downloads provide the free version of XPRESS, which restricts the number of variables and constraints we can use in an LP model. If you run into this problem, you can run your file remotely through the university server:

1. Connect to the university server with WinSCP: leibniz.math.bme.hu
2. Copy the .mos file to your university account file system.
3. Connect to leibniz.math.bme.hu again with PuTTY.
4. Use the following commands to run your mosel file:

    source /usr/local/bin/xpvars.sh
    mosel xyz.mos

(where xyz.mos is the name of your file)

Another option is to run your Mosel file through the free NEOS server. (However it is slow, as multiple people may be using the service at once; and security issues may arise):

1. Upload your file to the NEOS website for Mosel.
2. Fill out your details. The solution will be sent to the e-mail address provided.

II. Linear Programming models

II./1. Standard Linear Programming model: $$\text{(LP)} \begin{cases}\text{max}\ c^T x \\ Ax \le b \\ A \in \mathbb{R}^{m \times n};\ x, c \in \mathbb{R}^n;\ b \in \mathbb{R}^m \\ x \text{ is unknown}\end{cases} $$ Solver: mmxprs

II./2. Integer Programming model: $$\text{(IP)} \begin{cases}\text{max}\ c^T x \\ Ax \le b \\ A \in \mathbb{R}^{m \times n};\ x \in \mathbb{Z}^n;\ c \in \mathbb{R}^n;\ b \in \mathbb{R}^m \\ x \text{ is unknown}\end{cases} $$ Solver: mmxprs

II./3. Mixed Integer Linear Programming model: $$\text{(MILP)} \begin{cases}\text{max}\ c^T x + d^T y \\ A\begin{bmatrix}x \\ y\end{bmatrix} \le b \\ A \in \mathbb{R}^{m \times (n_1 + n_2)};\ x \in \mathbb{R}^{n_1};\ y \in \mathbb{Z}^{n_2};\ c \in \mathbb{R}^{n_1};\ d \in \mathbb{R}^{n_2};\ b \in \mathbb{R}^m \\ x,\ y \text{ are unknown}\end{cases} $$ Solver: mmxprs

II./4. Binary Integer Programming / Zero-One Integer Programming model: $$\text{(BIP)} \begin{cases}\text{max}\ c^T x + d^T y \\ A\begin{bmatrix}x \\ y\end{bmatrix} \le b \\ A \in \mathbb{R}^{m \times (n_1 + n_2)};\ x \in \mathbb{R}^{n_1};\ y \in \{0,1\}^{n_2};\ c \in \mathbb{R}^{n_1};\ d \in \mathbb{R}^{n_2};\ b \in \mathbb{R}^m \\ x,\ y \text{ are unknown}\end{cases} $$ Solver: mmxprs

II./5. (Convex) Quadratic Programming model: $$\text{(QP)} \begin{cases}\text{max}\ \frac{1}{2}x^TQx + c^T x \\ Ax \le b \\ A \in \mathbb{R}^{m \times n};\ x,c \in \mathbb{R}^n;\ Q \in \mathbb{R}^{n \times n} \text{ symmetric};\ b \in \mathbb{R}^m \\ x \text{ is unknown}\end{cases} $$ Solvers: mmquad, mmnl

II./6. Nonlinear Programming model: $$\text{(NLP)} \begin{cases}\text{max}\ f(x) \\ \forall i \in \{1,\dots,m\}\ g_i(x) \le 0 \\ \forall j \in \{1,\dots,p\}\ h_j(x) = 0 \\ x \in X \subseteq \mathbb{R}^n, f, g_i, h_j: X \to \mathbb{R}\\ x \text{ is unknown}\end{cases}$$ Solvers: mmnl, mmxnlp

II./7. Constraint Programming model: $$\text{(CP)} \begin{cases} X = \{x_1,\dots,x_n\} \text{ set of decision variables} \\ D=\{D_1,\dots,D_n\} \text{ set of domains},\ \forall i \in {1,\dots,n},\ x_i \in D_i \\ C = \{C_1,\dots,C_m\} \text{ set of constraints},\ \forall i \in \{1,\dots,n\},\ C_i = (X_i,R_i) \\ X_i = \{x_{i_1},\dots,x_{i_k}\}, R \subseteq D_{i_1} \times \dots \times D_{i_k} \text{ allowed relations between elements of } X \\ X \text{ is unknown}\end{cases}$$ Solver: kalis

III. Basics of XPRESS

III./1. Softwares

XPRESS Workbench: newer software, easier for beginners, features: autocompletion, keyboard shortcuts, autosave, unlimited Ctrl+Z, etc.
XPRESS IVE: older software, for developers, profiling tools, matrix view, branch & bound visualizer, etc.

We are going to be using XPRESS Workbench.

III./2. Documentation

Mosel quick reference guide: <install path>/xpressmp/docs/mosel/moselquickref.pdf
Formulization reference guide: <install path>/xpressmp/docs/mosel/mipformref.pdf
Detailed Mosel reference guide: <install path>/xpressmp/docs/mosel/mosel_lang/mosel_lang.pdf
Kalis reference guide: <install path>/xpressmp/docs/solver/kalis/kalis_ug/kalisug.pdf

IV. An example Mosel model

Download the Lesson1_Carpenter.mos Mosel model from here

IV./1. Excercise 1

a) Run the model.
b) How many chairs and tables were made?
c) How much time was left at the end?
d) How much wood was left at the end?
e) Experiment different parameters and rerun the model!
f) Change chairProfit from 80 to 200! What do you expect to happen?
g) If the optimal solution makes some (non-zero amount of) chairs and some (non-zero amount of) tables, then why is "Amount of wood left" and "Amount of time left" always 0?

IV./2. Excercise 2

Change back chairProfit from 200 to 80, then add the following lines right after the declarations block to turn the LP model into an IP model:

---

chairs is_integer
tables is_integer

---

a) How does the solution change?
b) How does the Total profit change?
c) Why is the statement in 1/g not necessarily true now?

Note: You can use the following commands as well:

is_binary: Set range of variable to {0,1}.
is_continuous (default): Set range of variable to [0,∞[
is_free: Set range of variable to ]-∞,+∞[

V. The Mosel language

V./1. Data types

string: "value", "has " + string(n) + " variables"
real: 3.2, -67.283, real("5.9")
integer: 0, 1, 2, ...
boolean: true, false
mpvar: decision variable ("mathematical programming variable")
linctr: linear constraint
nlctr: nonlinear constraint

These require the mmsystem module:

time: hours:minutes:seconds,milliseconds
date: year-month-day
datetime: year-month-dayThours:minutes:seconds,milliseconds

All of the above 3 work with SYS_NOW, e.g. time(SYS_NOW)

V./2. Comments

!: in-line comment
(! ... !): multi-line comment

V./3. If statements

if debug then
 writeln(cost)
end-if

if cost=3 then
 writeln("perfect")
elif cost >= 5 then
 writeln("too much")
elif cost <> 0 then
 writeln("cost isn't 0")
else
 writeln("close to optimal")
end-if

case c of
 1,2: writeln("c is too small")
 3 : writeln("c is optimal")
 4..6: do
  writeln("c is greater than the optimum")
  writeln("consult the management team")
 end-do
else
 writeln("this is unexpected!")
end-case

V./4. Lists, arrays

Sets

Sets have unique elements.

declarations
 COUNTRIES: set of string
end-declarations

COUNTRIES := {"USA","Hungary","Turkey","Botswana","Uruguay"}

Set union:

COUNTRIES += {"Samoa","Tajikistan"}

Set subtract:

COUNTRIES -= {"Botswana"}

Set intersection:

COUNTRIES * {"Turkey","Mexico","Samoa"}

Set size:

COUNTRIES.size

Lists

declarations
 ages: list of integer
end-declarations

ages := [37,80,13,57,37,22]

List truncation:

ages -= [37,22]

List concatenation:

ages += [29,55]

Element of list:

ages(2)

Index starts at 1.
List size:

ages.size

Ranges

declarations
 month_index: range
end-declarations

month_index := 1..12

Lists of lists

declarations
 S: set of list of integer
end-declarations

S := {[3,4,5],[9,0,2],[7,7,1]}

Arrays

parameters
 machines=1..10
 workers=1..25
end-parameters

declarations
 A: array(machines) of boolean
 B: array(machines,workers) of real
 C: array(machines,workers,machines) of integer
 D: dynamic array(machines,workers,machines) of integer
 E: array(range,list of string) of integer
end-declarations

E:: (2..4, ["A","B","C"]) [3,14,15,92,65,35,89,79,32]

Then A will be a 10 element vector,
B will be a 10x25 matrix,
C will be a 10x25x10 matrix,
D will be a 10x25x10 matrix which is "sparsely stored" - all elements will be stored in a pair with their index (like a python dictionary), and elements not defined won't be stored.
Finally, E will be $$E = \begin{bmatrix}3 & 14 & 15 \\ 92 & 65 & 35 \\ 89 & 79 & 32\end{bmatrix}$$ with row indices 2, 3, 4; and column indices "A", "B", "C".

V./5. Equality and inequality signs

= Equality constraint, equality in an if condition or parameter set operator.
:= Assignment operator. Assigning value to a variable, or assigning a name to a constraint.
: Decaring a variable in the declarations block without assigning a value to it.
:: Inline initialization of an array.
<= Less than or equal
>= Greater than or equal
< Less than
> Greater than
<> Not equal
a += 5 Equivalent to a = a + 5
a -= 5 Equivalent to a = a - 5
a *= 5 Equivalent to a = a * 5
a /= 5 Equivalent to a = a / 5