Written Exam
Linear and Integer Programming
(DM545) [pdf format]

Department of Mathematics and Computer Science
University of Southern Denmark

Tuesday, June 10, 2014, 10:00–14:00, U9 and U27

The exam consists of answers to a number of tasks divided into subtasks, which are to be handed in electronically in Blackboard (http://e-learn.sdu.dk).

The content of the document “Exam Instructions” published on the public course web page is assumed to be known.
Remember to justify all your statements! You may refer to results from the books or the lecture slides listed at the course web page. In particular, it is possible to justify a statement by saying that it derives trivially from a result in the textbook (if this is true). You may use all methods or extensions that have been used in the assignment sheets, published during the course. However, it is not allowed to answer a subtask exclusively by reference to an exercise seen during the course. Reference to other books (outside the course material) or to internet links is not accepted as answer to a task.
The contribution to the final evaluation of each task, if carried out correctly, is given at the beginning of each task as a list of points for each subtask. The number of points does not necessarily reflect the difficulty of the subtask. The maximum score is 110.
The order in which the tasks are presented is a suggested order of execution of the exam.
You may write your answers in Danish or in English.

An HTML version of this document is available at:

http://www.imada.sdu.dk/~marco/DM545/Exam/w8wlOND.html

Task 1 Network Flows (points: 7)

A set of work centers performs operations of various type on a set of mechanical pieces. Each operation {1,2,3,4} can be performed on a subset of the work centers {A,B,C}. The requirement for each type of operation is expressed in minutes:

operation	center	minutes
1	A,B	50
2	A,C	20
3	A,B,C	10
4	B	70

In the next working shift the working centers A, B and C will be available for 30, 80 and 40 minutes, respectively. The problem consists in determining whether it is possible to finish all operations in the next shift. Formulate the problem in terms of network flows.

Task 2 Branch and bound (points: 5, 4, 4)

Consider the Integer Linear Programming problem P0: z=max{cx: Ax≤ b, x integer} solved by a Branch & Bound algorithm.

In Figure 1 it is represented a situation during the run of the algorithm (the symbol ∄ indicates an infeasible problem).

Figure 1:

Subtask 2.a

Give the tightest possible lower and upper bounds on the optimal value z.

Subtask 2.b

For which values of upper bound and lower bound at node P6 is it possible to prune the tree below that node?

Subtask 2.c

If any, for which values of upper bound and lower bound at node P6 is it possible to indicate the optimal solution and close all nodes of the tree?

Task 3 Simplex (points: 4, 5, 10, 5)

Consider the following LP problem:

(P) max	z=x₁	+	5x₂
s.t.	−x₁	+	3x₂	≤ 6
	4x₁	+	4x₂	≥ 5
	0	≤	x₁	≤ 2
			x₂	≥ 0

(Note: the following subtasks can be carried out independently; use fractional mode for numerical calculations; in the online version you find the problem in ASCII format).¹

maximize x1+5*x2
subject to -x1+3*x2<=6
4*x1 +4*x2 >=5
x1<=2, >=0
x2>=0

Subtask 3.a

The polyhedron representing the feasibility region is depicted in the figure. Indicate for each of the four points represented whether they are feasible and/or basic solutions. Justify your answer.

Subtask 3.b

Write the initial tableau or dictionary for the simplex method. Write the corresponding basic solution and its value. State whether the solution is feasible or not and whether it is optimal or not.

Subtask 3.c

Consider the following tableau:

|-----+----+----+----+------+----+----+------|
|     | x1 | x2 | x3 | x4   | x5 | -z | b    |
|-----+----+----+----+------+----+----+------|
| I   |  0 |  4 |  1 | -1/4 |  0 |  0 | 29/4 |
| II  |  1 |  1 |  0 | -1/4 |  0 |  0 | 5/4  |
| III |  0 | -1 |  0 | 1/4  |  1 |  0 | 3/4  |
| IV  |  0 |  4 |  0 | 1/4  |  0 |  1 | -5/4 |
|-----+----+----+----+------+----+----+------|

and the following three pivoting rules:

largest coefficient
largest increase
steepest edge.

Which entering and leaving variables would each of them indicate? In this specific case, which rule would be convenient to follow? Report the details of the computations for the first two rules and carry out graphically the application of the third rule using the plot in the figure above (tikz code to reproduce the figure available in the online version.)

\begin{center}
\begin{tikzpicturehevea}[domain=-0.1:2.2,xscale=1.5,yscale=1.5,
basis/.style={circle,draw=blue!50,fill=blue!20,thick,inner sep=0pt,minimum size=2mm},
opt/.style={circle,draw=red!50,fill=red!50,thick,inner sep=0pt,minimum size=2mm},
point/.style={rectangle,draw=black!50,fill=black!20,thick,inner sep=0pt,minimum size=4mm}]

\draw[very thin,color=gray] (-0.2,-1.2) grid (2.9,2.9);
\draw[color=red] plot[id=c0]  function{2 +0.33*x} node[right] {};

\draw[color=red] (2,-1.2) -- (2,3) node[right] {};

\draw[color=red] plot[id=c2, domain=-0.1:2.3]  function{1.2500 -x} node[right] {};

\fill[blue!30,opacity=0.5]
(2,2.666667) -- %
(0,2) -- %
(0,1.25) -- %
(1.25,0) -- %
(2,0);

\node (p1) at (1.1,1.5) [basis] {};
\node at (p1) [right] {($x_1,y_1$)};
\node (p2) at (2,1) [basis] {};
\node at (p2) [right] {($x_2,y_2$)};
\node (p3) at (0,2) [basis] {};
\node at (p3) [left] {($x_3,y_3$)};
\node (p4) at (2,-3/4) [basis] {};
\node at (p4) [right] {($x_4,y_4$)};

\draw[->,thick] (-0.2,0) -- (2.500000,0) node[right] {$x_1$};
\draw[->,thick] (0,-1.2) -- (0,3) node[above] {$x_2$};
\end{tikzpicturehevea}
\end{center

Subtask 3.d

For solving P₀ with the Gomory’s fractional cutting plane algorithm one needs initially to solve P. After a number of iterations of the simplex algorithm the tableau looks as follows:

|-----+----+----+------+----+------+---+-------|
|     | x1 | x2 | x3   | x4 | x5   | -z| b     |
|-----+----+----+------+----+------+---+-------|
| I   |  0 |  0 | 4/3  |  1 | 16/3 | 0 | 41/3  |
| II  |  0 |  1 | 1/3  |  0 | 1/3  | 0 | 8/3   |
| III |  1 |  0 | 0    |  0 | 1    | 0 | 2     |
| IV  |  0 |  0 | -5/3 |  0 | -8/3 | 1 | -46/3 |
|-----+----+----+------+----+------+---+-------|

Derive a Gomory cut and write it in the space of the original variables.

Show that the cut is a valid inequality for (P₀) and that it will make the current optimal solution of (P) infeasible.

Task 4 Revised Simplex and Sensitivity (points: 9, 6)

Consider the following problem

min	z=5y₁	+	4y₂
	4y₁	+	3y₂	≥ 4
	2y₁	+	y₂	≥ 3
	y₁	+	2y₂	≥ 1
	y₁	+	y₂	≥ 2
	y₁,y₂			≥ 0

Because this problem has more functional constraints than variables, we will solve it by applying the simplex method to its dual problem. Let x₁, x₂, x₃ and x₄ be the variables of the dual problem that are associated with the constraints of the primal and x₅ and x₆ be the slack variables of the dual problem. The final optimal tableau is the following:

|----+----+----+----+----+----+----+----+----|
|    | x1 | x2 | x3 | x4 | x5 | x6 | -z |  b |
|----+----+----+----+----+----+----+----+----|
| x2 |  1 |  1 | -1 |  0 |  1 | -1 |  0 |  1 |
| x4 |  2 |  0 |  3 |  1 | -1 |  2 |  0 |  3 |
|    | -3 |  0 | -2 |  0 | -1 | -1 |  1 | -9 |
|----+----+----+----+----+----+----+----+----|

Subtask 4.a

Write:

[i.] the value of the variables for the optimal solution of the primal problem
the value of the variables for the optimal solution of the dual problem
the value of the shadow prices of the dual problem. If we could increase by one unit the RHS term of the dual problem, which one should we choose in order to obtain the largest improvement of the optimal value of the dual problem.
the value of the shadow prices of the primal problem. If we could increase by one unit the RHS term of the primal problem, which one should we choose in order to obtain the largest worsening of the optimal value of z?

Subtask 4.b

Show how to derive the reduced costs of the final tableau above, hence for the dual problem, using only matrix computations, like in the revised simplex method. [Hint to be faster in matrix calculations you can use any program for linear algebra. In the online version of this document you find the R and python code for matrix calculation. In python, import numpy and linalg.solve. In R, the inverse of a matrix can be calculated by solve and matrix multiplications by %*%.]

}## Python code

from numpy import *
import scipy.linalg as sl

## Useful functions:
example=array([1,2,3,4]).reshape(2,2)
print example.T # transpose
print sl.inv(example) # inverse
print sl.solve(example,array([2,2])) # solve system of lin equations
#############################

## Your data ####
A_p=array([4, 3, 2, 1, 1, 2, 1, 1]).reshape(4,2)
b_p=array([4,3,1,2]).reshape(4,1)
c_p=array([5,4]).reshape(2,1)

## R code:

## Useful functions:
example=matrix(c(1,2,3,4]),ncol=2)
t(example) # transpose
solve(example) # inverse
solve(example,c(2,2)) # solve system of lin equations
#############################

## Your data ####
(A.p <- matrix(c(4, 3, 2, 1, 1, 2, 1, 1), ncol=2, nrow=4, byrow=TRUE))
(b.p <- matrix(c(4,3,1,2),ncol=1))
(c.p <- matrix(c(5,4),ncol=1))

Task 5 Duality Theory (points: 7, 10)

Subtask 5.a

Using only the duality theory and without using the simplex method find out if

x₁^*=3, x₂^*=−1, x₃^*=0, x₄^*=2

is an optimal solution of the problem:

max	6x₁	+	x₂	−	x₃	−	x₄
s.t.	x₁	+	2x₂	+	x₃	+	x₄	≤ 5
	3x₁	+	x₂	−	x₃			≤ 8
			x₂	+	x₃	+	x₄	=1
	x₃,x₄							≥ 0

Subtask 5.b

Write the dual of the following problem:

(P) min

∑

j=1

c_jy_j

∑

j=1

a_ij x_ij =b_i

i=1,…,n

∑

i=1

x_ij≤ y_j

j=1,…,m

x_ij≤ 1

i=1,…,n; j=1,…,m

x_ij≥ 0

i=1,…,n; j=1,…,m

y_j∈ ℝ

j=1,…,m

Task 6 LP Formulation (points: 12, 5)

A bartender serves usually alcoholic beverages behind the bar. A bartender can generally mix classic cocktails such as a Gin-and-Tonic, Caipirinha and Mojito. In order to achieve this task the bartender has to maintain the supplies and inventory for the bar.

End drinks for the customers are created by directly mixing the raw materials. Restricting our attention to the Gin-and-Tonic drink, the suggested ratios of gin and tonic are 1:1, 2:3, 1:2, and 1:3 (source Wikipedia). The historical data indicate nevertheless that the typical demand on a Saturday evening in the premise of our bartender is as follows:

Alcohol	quantity	price per deciliter
≥ 20%	≤ 12 l	30 dkk
≥ 16%	≤ 12 l	25 dkk
≥ 13%	≤ 12 l	21 dkk
≥ 10%	≤ 12 l	15 dkk

For example, the first row indicates that there are customers that are willing to intake 20% or more alcohol consuming all together up to 12 liters and willing to pay 30 krone per deciliter.

Our bartender for economical and logistic issues can buy up to 10 liters of gin that contain 40% alcohol and up to 20 liters of tonic that contain no alcohol.

The mixing process occurs in a way such that at the end the input products no longer exist in their original forms, but are mixed to form new mixed products with new property values, in this case, the percentage of alcohol content.

The objective is to maximize the total profit from the sell.

The problem is an example of blending problem that arises, beside bar keeping also in the oil refinery industry.

Subtask 6.a

Represent the situation as a network and model the problem as a linear programming problem.

Subtask 6.b

In order to be faster in serving his clients, our bartender decides to create and maintain intermediate drink containers. Depending on the structure of the network, this may anticipate part of the drink dilution process and delay another part until final drinks have to be blended to specification.

Now the raw materials are input of the pooling container only and customers receive their drinks directly from the pooling container or by mixing the drinks of the pooling containers. It is assumed that the flow of intermediate products into the pooling containers equals the flow required to blend the final products.

The bartender decides to experiment with the use of one only pooling container. The situation is represented in Figure 2.

Unfortunately, writing an LP model for this situation is known to be an NP hard problem. Can you nevertheless write a nonlinear model for this situation? Intuitively, when solved to optimality, will the total profit increase or decrease with respect to Subtask 6.a?

Figure 2: The situation in Subtask 6.b.

Task 7 IP Formulation (points: 10)

In two days the world cup in Brazil will finally start! Prandelli, the trainer of the Italian team, had to plan the content of the training sessions for his team. The schedule is two sessions per day, morning and afternoon, for a time horizon of n days; optimistically he planned for the whole duration of the competition, that is, one month. Prandelli has a data base of activities I to propose during the sessions. Associated to each activity i in I there are three numbers that quantify the training effect: technical effect a_i1, tactical effect a_i2 and physical effect a_i3. Moreover each activity has a duration t_i expressed in minutes.

Each activity can be proposed more than once throughout the sessions. The following constraints must be taken into account:

[i.] Each activity can be scheduled only once per day.
Each session lasts 2 hours, that is, 120 minutes.
There is a pre-determined limit on the physical effort b_3s for each session s. This value varies through the sessions. For example, sessions in the days just before and just after a match will contain less physical effort.
Considering the technical and tactical aspects as the main strengths of his team, Prandelli wants to ensure that each session has at least a desired amount of effort in those attributes. Let b_1s and b_2s define these requirements for each session.
Some activities are incompatible, that is, they cannot be scheduled in the same day. Let A be a set of pairs of incompatible activities. In each day and for each pair of activities (i,j) ∈ A, if activity i is selected then activity j cannot be prescribed in the same day and viceversa.
Some activities that are physically particularly demanding can be scheduled only with at least 3 days distance. Let H ⊆ S² be the set that identifies these activities.
For the tactical activities, that is, those with a non zero tactical attribute, that is, a_i2>0, the effect must be non-decreasing during the month of training. [Hint: define P to be the set of pairs of activities such that (i,j) ∈ P if and only if 0<a_i2<a_j2. Thus, if (i,j) ∈ P then i must be scheduled before j. Further, define a variable to contain for an activity i the last session in which it is scheduled...]

The objective is to maximize the number of activities proposed.

Formulate the problem as an integer linear problem.

[Hint: Let S be the set of session indexed by s. For variables you need at least the variable x_is to indicate if activity i is scheduled in session s. You might need more variables to make the IP formulation.]

Task 8 Preprocessing and TUM (points: 7)

Using preprocessing rules only, eliminate as many rows and columns as possible from the following set partitioning problem until you are left with a totally unimodular matrix or it is possible to determine the optimal solution. Remember to justify your claims by showing how a certain result from the course applies. For example, it is not enough to claim that a matrix is TUM but you have to show why.

min

⎡
⎣

⎤
⎦

∈ {0,1}¹²

with A given by:

⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣

1	1			1				1
	1				1		1				1
	1		1	1		1			1	1	1
1		1	1
					1
	1			1		1		1		1
1			1
				1					1		1

⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦

|---++---+---+---+---+----+---+----+---+---+----+----+----|
|   || 1 | 2 | 3 | 4 |  5 | 6 |  7 | 8 | 9 | 10 | 11 | 12 |
|   || 5 | 4 | 5 | 4 | 11 | 6 | 10 | 2 | 5 |  3 |  9 | 5  |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 1 || 1 | 1 |   |   |  1 |   |    |   | 1 |    |    |    |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 2 ||   | 1 |   |   |    | 1 |    | 1 |   |    |    |  1 |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 3 ||   | 1 |   | 1 |  1 |   |  1 |   |   |  1 |  1 |  1 |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 4 || 1 |   | 1 | 1 |    |   |    |   |   |    |    |    |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 5 ||   |   |   |   |    | 1 |    |   |   |    |    |    |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 6 ||   | 1 |   |   |  1 |   |  1 |   | 1 |    |  1 |    |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 7 || 1 |   |   | 1 |    |   |    |   |   |    |    |    |
|---++---+---+---+---+----+---+----+---+---+----+----+----|
| 8 ||   |   |   |   |  1 |   |    |   |   |  1 |    |  1 |
|---++---+---+---+---+----+---+----+---+---+----+----+----|

|---+---+---+---+---+----+---+----+---+---+----+----+----|
|   | 1 | 2 | 3 | 4 |  5 | 6 |  7 | 8 | 9 | 10 | 11 | 12 |
|   | 5 | 4 | 5 | 4 | 11 | 6 | 10 | 2 | 5 |  3 |  9 | 5  |
|---+---+---+---+---+----+---+----+---+---+----+----+----|
| 1 | 1 | 1 |   |   |  1 |   |    |   | 1 |    |    |    |
| 2 |   | 1 |   |   |    | 1 |    | 1 |   |    |    |  1 |
| 3 |   | 1 |   | 1 |  1 |   |  1 |   |   |  1 |  1 |  1 |
| 4 | 1 |   | 1 | 1 |    |   |    |   |   |    |    |    |
| 5 |   |   |   |   |    | 1 |    |   |   |    |    |    |
| 6 |   | 1 |   |   |  1 |   |  1 |   | 1 |    |  1 |    |
| 7 | 1 |   |   | 1 |    |   |    |   |   |    |    |    |
| 8 |   |   |   |   |  1 |   |    |   |   |  1 |    |  1 |
|---+---+---+---+---+----+---+----+---+---+----+----+----|

1: Update 26.06.2014: In the figure a point (x_i,y_i) should be intended as (x₁ⁱ,x₂ⁱ).
2: Update 26.06.2014: H ⊆ I

Written Exam Linear and Integer Programming (DM545) [pdf format]

Department of Mathematics and Computer Science University of Southern Denmark