Written Exam |
The exam consists of answers to a number of tasks divided into subtasks, which are to be handed in electronically in http://e-learn.sdu.dk (Blackboard).
A small firm that produces two types of mattresses, Single and Double, has two workers for the final treatment of the mattresses before being ready for sell. In one hour the two workers can process the following number of mattresses:
The market demands at least 30 Single and 20 Double mattresses per day. The cost of one hour of working time is 90 Dkk for worker A and 80 Dkk for worker B. The management of the firm wants to determine the number of hours per day that each worker has to be engaged in order to meet the demand at the minimum cost. Workers can only be engaged for multiples of hours and not for fractions of hours.
Formulate the problem as an integer linear programming problem. (Ignore that workers can have a maximum number of working hours per day.)
Write the linear programming relaxation (P1) of the original problem formulation (P) given at the previous subtask.
Explain the relation between the optimal solution of (P1) and the optimal solution of (P).
Derive the dual (D1) of (P1) using the Lagrange multipliers approach. Show all steps of the derivation and write the final problem (D1).
After two iterations of the appropriate form of the simplex method we obtain the two following tableaux:
Tableau #4 |-----+-----+------+------+----+----+------| | | x_A | x_B | s1 | s2 | -z | b | |-----+-----+------+------+----+----+------| | I | 1 | 2/3 | -1/3 | 0 | 0 | 10 | | II | 0 | -4/3 | -1/3 | 1 | 0 | -10 | | III | 0 | 20 | 30 | 0 | 1 | -900 | |-----+-----+------+------+----+----+------|
Tableau #5 |-----+-----+-----+------+------+----+-------| | | x_A | x_B | s1 | s2 | -z | b | |-----+-----+-----+------+------+----+-------| | I | 1 | 0 | -1/2 | 1/2 | 0 | 5 | | II | 0 | 1 | 1/4 | -3/4 | 0 | 15/2 | | III | 0 | 0 | 25 | 15 | 1 | -1050 | |-----+-----+-----+------+------+----+-------|
Explain in detail which operations have been done to reach the two tableaux. In particular, indicate the pivot of the two iterations, the entering and leaving variables and the elementary row operations to go from one tableau to the other. (Use the names given in the first column of the tableaux to identify rows.)
Determine the optimal solution of (P1) and the value of the corresponding objective function. (Report the values for all four variables of the standard form in the optimal solution and remember to explain why the solution you are reporting is feasible and optimal.)
Determine the value of the dual variables.
The optimal integer solution is found by adding a Gomory cut.
Consider the network N=(V,A,l≡ 0,u,b,c) of Figure 1 and let x* be the flow there represented.
\tikzset{ node/.style={circle,draw,fill=none,thick,minimum size=20pt,inner sep=0pt}, nondirectional/.style={very thick,black}, unidirectional/.style={nondirectional,shorten >=2pt,-stealth}, bidirectional/.style={unidirectional,bend right=10}, weight/.style={sloped,font=\small} } \begin{tikzpicture}[scale=8] \node [node] (a) at (-0.956460, -0.365955) {$a$}; \node at (a) [below=9pt] {$0$}; \node [node] (b) at (-0.462372, -0.368572) {$b$}; \node at (b) [below=9pt] {$1$}; \node [node] (c) at (-0.709751, -0.002069) {$c$}; \node at (c) [below=9pt] {$-6$}; \node [node] (d) at (-0.370297, 0.015660) {$d$}; \node at (d) [above=9pt] {$-4$}; \node [node] (e) at (-1.100000, 0.070901) {$e$}; \node at (e) [above=9pt] {$2$}; \node [node] (f) at (-0.657976, 0.290306) {$f$}; \node at (f) [above=9pt] {$7$}; \path [unidirectional] (a) edge node[weight,above=0pt,pos=0.5] {$0/3/4,1$} (c); \path [unidirectional] (b) edge node[weight,above=0pt,pos=0.5] {$0/1/4,2$} (a); \path [unidirectional] (c) edge node[weight,above=0pt,pos=0.5] {$0/1/2,3$} (d); \path [unidirectional] (c) edge node[weight,above=0pt,pos=0.5] {$0/0/2,2$} (e); \path [unidirectional] (d) edge node[weight,above=0pt,pos=0.5] {$0/0/3,1$} (b); \path [unidirectional] (e) edge node[weight,below=0pt,pos=0.5] {$0/2/2,4$} (a); % to use for bidirectional arcs % \path [bidirectional] (e) edge node[weight,below=0pt,pos=0.5] {$3/ /4,4$} (a); % \path [bidirectional] (a) edge node[weight,below=0pt,pos=0.5] {$3/ /4,4$} (e); \path [unidirectional] (e) edge node[weight,above=0pt,pos=0.5] {$0/0/3,3$} (f); \path [unidirectional] (f) edge node[weight,above=0pt,pos=0.5] {$0/4/5,2$} (c); \path [unidirectional] (f) edge node[weight,above=0pt,pos=0.5] {$0/3/3,2$} (d); \end{tikzpicture
Argue that the flow x* is feasible and give its cost.
Draw the residual network N(x*) explaining briefly how you find the capacity on the arcs of N(x*) (it suffices to show a couple of examples).
Argue that x* is a minimum cost cycle for N.
Suppose now that the lower bound to the flow in the arc ef is set to 1 while all the rest remains unchanged, thus yielding the network N′=(V,A,l′,u,b,c). Find a new feasible flow and explain how you found it.
Find an optimal cost flow x′ for N′.
Decompose x′ into path and cycle flows and explain how you found each single component in the decomposition.
The Danish Research Council has to decide which research projects to finance. The total budget for the projects is 20 million Dkk. The table below shows the evaluation from 0 (worst) to 2 (best) that the projects received by the external reviewers and the amount of money required.
1 2 3 4 5 Evaluation score 1 1.8 1.4 0.6 1.4 Investment (in million of DKK) 6 12 10 4 8
Projects 2 and 3 have the same coordinator and the Council decided to grant only one of the two.
The Council wants to select the combination of projects that will maximize the total relevance of the projects, that is, the sum of the evaluation score while remaining within the budget.
Formulate the problem of deciding on which project the Council has to invest as an integer linear programming problem P.
We want the IP instance solved using the branch-and-bound
algorithm. What is the optimal solution x* to the LP relaxation
P′? [Hint: use glpsol to find out. You find a skeleton with
the input data in the online version of this document.]
| }set P; param score{P}; param crone{P}; param B; # # Your model here # solve; display something; data; set P := 1 2 3 4 5; param : score crone := 1 1 6 2 1.8 12 3 1.4 10 4 0.6 4 5 1.4 8; param B := 20; end; # in case you need data transposed: # 1 1.8 1.4 0.6 1.4 # 6 12 10 4 8 |
The rounding heuristic applied to the solution x* gives a feasible solution x′. Which one? With the knowledge collected until this stage which of the three following statements is correct:
(Remember to justify your answer.)
The two subproblems generated by the branch-and-bound algorithm after finding x* correspond to choosing or not choosing a particular project. Which one?
Suppose the branch-and-bound algorithm considers first the subproblem corresponding to not choosing this project. Let’s call this subproblem and its corresponding node in the search tree SP1. What is the optimal solution to its LP relaxation?
Next, the branch-and-bound algorithm considers the subproblem corresponding to choosing the project, i.e., subproblem SP2. Find the optimal solution to its LP relaxation. Which are the active nodes (i.e., open subproblems) at this point?
How does the branch and bound end?
Some video camera must be allocated to watch the corridors of a museum. The graphs in Figure 2 represent the two floors of the museum, in which arcs correspond to corridors and vertices to the crossing points between corridors. A camera, allocated on a vertex, is able to watch all and only the arcs incident to the vertex. The problem in each floor consists in determining the minimal number of cameras and their position in order to watch all the corridors.
\tikzstyle{vertex}=[circle,draw,fill=none,thick,minimum size=12pt,inner sep=0pt,font=\scriptsize] \tikzstyle{selected vertex} = [vertex, fill=red!24] \tikzstyle{edge} = [draw,thick,-] \tikzstyle{arc} = [draw,thick,->,shorten >=1pt,>=stealth'] \tikzstyle{arcl} = [draw,thick,->,shorten >=1pt,>=stealth',bend left=25] \tikzstyle{arcr} = [draw,thick,->,shorten >=1pt,>=stealth'] \tikzstyle{weight} = [font=\small] \tikzstyle{selected edge} = [draw,line width=5pt,-,red!50] \tikzstyle{ignored edge} = [draw,line width=5pt,-,black!20] \begin{tikzpicture}[scale=0.9, auto,swap] % First we draw the vertices \foreach \pos/\name/\bv in {{(0,0)/8/ }, {(2,0)/9/ }, {(4,0)/10/ }, {(6,0)/11/ }, {(0,1)/4/ }, {(2,1)/5/ }, {(4,1)/6/ }, {(6,1)/7/ }, {(2,2)/1/ }, {(4,2)/2/ }, {(6,2)/3/ }}{ \node[vertex] (\name) at \pos {$\name$}; \node at \pos [below=9pt] {\bv}; } % Connect vertices with edges and draw weights - Forward arcs \foreach \source/\dest/\weight in { 8/9/{ }, 9/10/{ }, 10/11/{ }, 11/7/{ }, 7/6/{ }, 6/5/{ }, 5/4/{ }, 4/8/{ }, 5/1/{ }, 6/2/{ }, 5/9/{ }, 2/3/{ }, 7/3/{ } }{ \path[edge] (\source) -- node[weight] {$\weight$} (\dest); } \end{tikzpicture} % \hspace{2cm} \begin{tikzpicture}[scale=0.9, auto,swap] % First we draw the vertices \foreach \pos/\name/\bv in {{(0,0)/8/ }, {(2,0)/9/ }, {(6,0)/10/ }, {(0,1)/4/ }, {(2,1)/5/ }, {(4,1)/6/ }, {(6,1)/7/ }, {(2,2)/1/ }, {(4,2)/2/ }, {(6,2)/3/ }}{ \node[vertex] (\name) at \pos {$\name$}; \node at \pos [below=9pt] {\bv}; } % Connect vertices with edges and draw weights - Forward arcs \foreach \source/\dest/\weight in { 8/9/{ }, 9/10/{ }, 10/7/{ }, 7/6/{ }, 6/5/{ }, 5/4/{ }, 4/8/{ }, 5/1/{ }, 6/2/{ }, 5/9/{ }, 2/3/{ }, 7/3/{ } }{ \path[edge] (\source) -- node[weight] {$\weight$} (\dest); } \end{tikzpicture
Figure 2: Two graphs representing the two floors of the museum of Task 4. On the left the first floor, on the right the second floor. [You find online the code of these graphs exhibiting the list of edges.]
Formulate the problem
in terms of integer linear programming.
What can you say about the possibility to solve the problems on the two floors using only linear programming? (Remember to justify your answers.)
While your are holding this exam, the staff at IMADA will take a final decision about the creation of a new study area for students in the Mathematical Library. If the decision is positive some journals currently stored in the library will have to be moved in secondary facilities such as the basement or at the central Library. Each secondary storage facility has limited capacity and a particular access cost for retrieving information. Through appropriate data collection, made available by the diligent work of Tove, we can determine the usage rates for the information needs of the users. Let bj denote the capacity storage of facility j and vj denote the access cost per unit item from this facility. In addition, let ai denote the number of items of a particular class i requiring storage and let ui denote the expected rate (per unit of time) that we will need to retrieve books from this class. Our goal is to help Tove in deciding where to store the journals in a way that will minimize the expected retrieval cost.
Show how to formulate the problem of determining an optimal policy as a network flow problem;
Describe briefly an algorithm and explain the computational cost of its operations (only stating the total computational complexity without explanation is not enough).
Consider the following LP problem [you find online its data in text format]:
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||
and call x5,x6 the two slack variables to bring the problem in standard form.
Using only matrix computations, like in the revised simplex method,
calculate the value of the variables corresponding to a solution x*
with xB*=(x2, x3) basic variables and xN*=(x1,x4,x5,x6) non
basic variables. [Hint to be faster in inverting the matrix AB you
can use any program for linear algebra. For example, in R, the inverse
of a matrix can be calculated by solve and matrix
multiplications by %*%.]
Show that the solution found at the previous subtask is optimal but that it is not unique. Consequently, express all optimal solutions.
Which minimal change in the data of the problem, maintaining all data integer, would make x* become the unique optimal solution.
Suppose we wish to consider a change in the right-hand side term of the second constraint, adding a value є ∈ ℝ.