%  Final examination
%  Combinatorial Optimization, SUAMI, summer 2015
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=5.5truein \vsize=9truein
\pdfhorigin=1.5truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

% AMSFonts
\input amssym.tex

% rsfs script fonts
\font\tenscr=rsfs10    \font\sevenscr=rsfs7     \font\fivescr=rsfs5
\skewchar\tenscr='177  \skewchar\sevenscr='177  \skewchar\fivescr='177
\newfam\scrfam
\textfont\scrfam=\tenscr  \scriptfont\scrfam=\sevenscr
  \scriptscriptfont\scrfam=\fivescr
\def\scr{\fam\scrfam}

\font\titlefont=cmbx12  \font\smfont=cmr8  \font\transposefont=cmss8 at6pt

\edef\restoreinterlineskip{\noexpand\baselineskip=\the\baselineskip\relax\noexpand\lineskiplimit=\the\lineskiplimit\relax\noexpand\lineskip=\the\lineskip}

\long\def\boxed#1{\vbox{\offinterlineskip
	\hrule
	\hbox to \hsize{%
	\hss\vrule\hskip1em%
	\vbox{\advance\hsize by-2em \advance\hsize by-0.8pt
	\restoreinterlineskip
	\vskip1ex
	\noindent#1\par
	\vskip1ex
	}\hskip1em\vrule\hss}%
	\hrule}}

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\filbreak\medskip\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent{\bf Solution.}\enspace\ignorespaces}

\def\R{{\mathord{\Bbb R}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|}  \def\rabs{\mathclose|}  \def\abs#1{\labs#1\rabs}
\def\dom{\mathop{\rm dom}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Final examination}
\smallskip
\centerline{Tuesday, July~14, 2015}

\medskip

\noindent Please read all of the following before beginning this exam.

\medskip

\item{1.} This exam consists of six problems. Each of the problems is worth
20~points.

\medskip

\item{2.} You may use the textbook, your course notes, your completed problem
sets, the resources on the course Web page, and a calculator.

\medskip

\item{3.} Justify everything. The justification is often more important than
the answer itself. If you can't figure out the answer, describe your thought
process and what you have figured out; partial credit will be given. Clearly
state any assumptions you make.

\medskip

\item{4.} If you have questions during the exam, please ask.

\medskip\hbox to\hsize{\hskip1in\hrulefill\hskip1in}\bigskip

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the simplex tableau below, several variables are candidates to
become basic in the next basic feasible solution.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut$#$\enspace\cr
x_1&x_2&x_3&s_1&s_2&s_3&s_4&z&\omit&\hbox{\smfont RHS}\cr
\noalign{\vskip2pt}
-5&0&0&-2&0&0&-6&1&\omit\vrule&245\cr
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit\vrule height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit&\omit\vrule height2pt\cr
5&1&0&1&0&0&-3&0&\omit\vrule&40\cr
2&0&0&1/2&1&0&2&0&\omit\vrule&18\cr
1/2&0&0&-4/3&0&1&3&0&\omit\vrule&12\cr
1&0&1&2/3&0&0&1/2&0&\omit\vrule&24\cr}}$$
Which variable should be made basic in the next basic feasible solution if the
goal is

\smallskip

\item{(a)} for the new objective value to be~285? Why?

\smallskip

\item{(b)} for the next basic feasible solution to be degenerate? Why?

\smallskip

\item{(c)} to have $s_3=0$ in the next basic feasible solution? Why?

\smallskip

\item{(d)} to achieve the greatest increase in the objective value? Why?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider the following linear program.
$$\eqalign{
	{\rm minimize}\quad5y_1+3y_2+6y_3&\cr
	{\rm subject\ to}\quad\phantom1y_1\phantom{{}+0y_2}+\phantom1y_3&\ge60\cr
	y_1+2y_2+\phantom1y_3&\ge72\cr
	2y_1+\phantom1y_2+2y_3&\ge84\cr
	y_2-\phantom1y_3&\ge24\cr
	&\phantom{{}=00}\llap{$y_1\ge0$,\quad$y_2\ge0$,\quad$y_3\ge0$}.\cr
}$$
The optimal feasible solution to this linear program is $y_1=60$, $y_2=24$, and
$y_3=0$. Determine the dual linear program and its optimal solution. Use the
optimal dual solution to demonstrate that the claimed optimal solution to the
primal is indeed optimal.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Formulate a linear or integer program to answer the following
question.

{\medskip\narrower

\noindent A company manufactures three product lines. Each production run of
line~$i$ involves a fixed cost~$F_i$ and a per-unit cost~$p_i$, so that the
cost of $x_i$~units of line~$i$ is $F_i+p_ix_i$. These costs, together with the
per-unit revenue, are given in the table below.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
Product&&Fixed&Per-unit&Per-unit\cr
line&&cost&cost&revenue\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
1&&\$1500&\$45&\$240\cr
2&&\phantom{\$0}900&\phantom\$38&\phantom\$190\cr
3&&\phantom\$1000&\phantom\$40&\phantom\$210\cr}}$$
There are two key production processes, A~and~B. The time requirements for
each product line on each process, and the hours available, are given in the
table below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#&\enspace\hfil\strut#\hfil\enspace&\enspace\hfil\strut#\hfil\enspace\cr
&&\multispan3\enspace\hfil\strut Product line\hfil\enspace&&Hours\cr
Process&&1&2&3&&available\cr
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt&\omit&\omit&\omit&height2pt\cr
A&&0.25&0.20&0.30&&300\cr
B&&0.40&0.50&0.20&&400\cr}}$$
The company will upgrade exactly one of the two processes. The upgrade to
Process~A will raise the number of effective hours by~20\%; that to Process~B
will raise the number of effective hours by~10\%.

Which process should the company upgrade, and how much of each product line
should be manufactured in order to maximize the difference between revenue and
cost?

\medskip}

\noindent[Note: You do not need to {\it solve\/} your linear or integer
program---just formulate it.]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the following network, capacities of arcs are shown as circled
numbers, and flows along arcs are shown in blue. Is the given $s$--$t$ flow
optimal? If so, prove that it is optimal. If not, find (methodically) a better
flow.
$$\fig{final-flow-1.mps}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Constraint programming is an important area of combinatorial
optimization that we did not discuss in this course. An instance of a
constraint programming problem (in particular, a constraint satisfaction
problem) consists of a finite set~$X$ of variables; a finite set~$\dom(x)$ for
each variable~$x\in X$, called the {\it domain\/} of~$x$; and a set of
{\it constraints}, each of which specifies, directly or indirectly, a set of
allowable combinations of values for a subset of the variables. The objective
is to find an assignment of values to all of the variables such that for every
variable~$x\in X$ the value assigned to~$x$ is an element of~$\dom(x)$ and such
that all constraints are satisfied, or to determine that no such satisfying
assignment exists.

One type of constraint is the {\it alldiff\/} constraint, which specifies that
the values of a subset of the variables must all be different. For example, the
constraint ${\it alldiff\/}(x_1,x_3,x_4,x_8)$ means that the values assigned to
the variables $x_1$,~$x_3$, $x_4$, and~$x_8$ must all be different; no two of
those variables may be assigned the same value.

Suppose you are given an {\it alldiff\/} constraint and the domains of the
variables in the constraint. Carefully describe an efficient algorithm to
determine whether the {\it alldiff\/} constraint is satisfiable (alone,
independently of any other constraints that happen to be in the constraint
satisfaction problem). Justify that your algorithm is correct. You may use any
of the algorithms we discussed in the course as subroutines in your algorithm.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In the {\smfont SET PACKING} problem, an instance is a
collection~$\scr C$ of finite sets and a positive integer~$k$, and the question
is whether $\scr C$ contains $k$~disjoint sets. Prove that {\smfont SET
PACKING} is NP-hard.

\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\footline={\hfil}

$$\fig{final-flow-2.mps}$$
\vfill
$$\fig{final-flow-2.mps}$$
\vfill
$$\fig{final-flow-2.mps}$$
\vfill\eject
$$\fig{final-flow-2.mps}$$
\vfill
$$\fig{final-flow-2.mps}$$
\vfill
$$\fig{final-flow-2.mps}$$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bye
