% Final examination % Combinatorial Optimization, SUAMI, summer 2015 % Brian Kell \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