---

Lesson 3
Binary constraints, Linearization

---

I. Modelling with binary constraints

We are running a company with 16 workstations and 4000 workers. Each worker has to be assigned to a workstation. Each workstation has to have insurance, and the insurer categorizes workstations into the following groups:

Number of workers	Insurance type	Yearly insurance fee (USD)
1-19	Regular office	250
20-49	A-type workplace	600
50-99	B-type workplace	1250
100-249	C-type workplace	3150
250-499	Large scale work operation	6250
500+	Industrial scale work operation	12500

We can assign any number of workers to each workstation, from a minimum of 1, up to a maximum of 1000. What is the optimal number of workers in each workstation that minimizes our total insurance cost?

Download the Lesson3_Insurance.mos Mosel model from here

I./1. Excercise 1

a) Read through the model constraints, then run the program! It crashes. Why?
b) Comment out the part that crashes, and uncomment the solution. How does it work? Magic! Math!
c) Are there any other solutions besides swapping each workstation?

II. Linearization

Linearization Theorem 1

$$x,y \in \mathbb{R}^+_0 \text{ or } x,y \in \mathbb{Z}^+_0 \text{ decision variables},\ b \in \{0,1\} \text{ binary decision variable}$$ $$y=x \cdot b \Leftrightarrow \begin{cases}y \le Mb \\ y \le x \\ x+Mb-M \le y \\ (y \ge 0) \ (\text{default in Mosel})\end{cases}$$ $$\text{for some } M \ge \sup(x)$$

Linearization Theorem 2

$$x,y \in \mathbb{R} \text{ or } x,y \in \mathbb{Z} \text{ decision variables},\ b \in \{0,1\} \text{ binary decision variable}$$ $$y=x \cdot b \Leftrightarrow \begin{cases}y \le Mb \\ y \ge -Mb \\ x+Mb-M \le y \\ x-Mb+M \ge y\end{cases}$$ $$\text{for some } M \ge \sup|x|$$

Linearization Theorem 3

$$a,b,c \in \{0,1\} \text{ binary decision variables}$$ $$c=a \cdot b \Leftrightarrow \begin{cases}c \le a \\ c \le b \\ a+b \le 1+c\end{cases}$$

Linearization Theorem 4

$$b_1,\dots,b_n;b \in \{0,1\} \text{ binary decision variables}$$ $$b=b_1 \cdot . . . \cdot b_n \Leftrightarrow \begin{cases}b \le b_1 \\ \vdots \\ b \le b_n \\ b_1 + \dots + b_n \le n-1+b\end{cases}$$

III. Modelling with binary constraints Part 2

We have 7 backpacks and 30 items. Each backpack has a carrying capacity (in kg). Each item has a weight (in kg) and a value (in USD). We would like to carry as much value as possible. (Up to here, this is called a Backpack Problem or a Knapsack Problem.)

However if any backpack weight exceeds 32 kg, then we also need to tie a rope to it for safe carrying. Each rope costs 4 USD, which we subtract from the objective function.

Download the Lesson3_Backpacks.mos Mosel model from here

III./1. Excercise 2

a) Read through the model constraints, then run the program! It crashes. Why?
b) Comment out the part that crashes, and rewrite it using Theorem 3 (or 4)!
c) How does the solution change if we set ropeValue to 0?
d) Change ropeValue back to 4 and change ropeMin to 24. How many backpacks will be stuffed to exactly 24 kg?

IV. Parameter shifting and graphing

Download the Lesson3_Insurance2.mos Mosel model from here

We are re-running the Insurance example, this time with different starting parameters. Namely what if we had fewer or more workers at the company? How much insurance would we have to pay? XPress allows us to store a basis solution and re-run the optimization with slightly different constraints, then graph the overall results according to how the input parameters changed.

IV./1. Excercise 3

a) Read through the model, and find the lines marked with "new".
b) Change the model such that every time we increase the number of workers we have by 500 in workerAmt, also increase the maximum number of workers allowed at each workstation by 50!
c) Change the insuranceCosts array to [250,500,750,1000,10000,12000]! Have the results changed significantly? If so, explain why!