% Problem set 7: solutions
% 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
\font\titlefont=cmbx12 \font\smfont=cmr8 \font\transposefont=cmss8 at6pt
\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
\medbreak\noindent{\llap{\bf\the\pno.\enspace}}\ignorespaces}
\def\solution{\medskip\noindent\llap{$\triangleright$\bf\phantom.\enspace}{\bf Solution.}\enspace\ignorespaces}
% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
\parfillskip=0pt \finalhyphendemerits=0 \par}}
\def\subqed{{\unskip\nobreak\hfil\penalty50
\hskip1em\hbox{}\nobreak\hfil\raise2pt\hbox{\vrule height4pt width4pt depth0pt}
\parfillskip=0pt \finalhyphendemerits=0 \par}}
\newdimen\pivotwidth \newdimen\pivotdepth
\def\pivot#1{%
\setbox0=\hbox{\vphantom/$#1$}
\pivotdepth=\dp0
\setbox0=\hbox{\vbox{\vskip1pt\hbox{\hskip2pt\box0\hskip2pt}\vskip1pt}}%
\pivotwidth=\wd0 \advance\pivotwidth by0.8pt
\lower\pivotdepth\hbox{\vbox{%
\vskip-1.4pt
\hrule width\pivotwidth height0.4pt depth0.0pt
\hbox{%
\vrule height\ht0 depth\dp0 width0.4pt
\copy0
\vrule height\ht0 depth\dp0 width0.4pt
}%
\hrule width\pivotwidth height0.4pt depth0.0pt
\vskip-1.4pt
}\hskip-2.4pt}%
}
\def\frac#1#2{{\textstyle{{#1}\over{#2}}}}
\def\R{{\mathord{\Bbb R}}} \def\Q{{\mathord{\Bbb Q}}}
\def\Z{{\mathord{\Bbb Z}}} \def\N{{\mathord{\Bbb N}}}
\def\transpose{{\raise0.5pt\hbox{\transposefont T}}}
\def\labs{\mathopen|} \def\rabs{\mathclose|} \def\abs#1{\labs#1\rabs}
\def\implies{\Longrightarrow}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~7: solutions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Formulate and solve an integer program for the following scenario.
{\medskip\narrower
\noindent A trader of unusual objects is traveling with a caravan that begins
in city~A, proceeds through cities B,~C, and~D, in order, and ends in city~E.
The trader knows of some items in each city that can be purchased and later
sold in other cities. The following table lists these items, their weights,
their current locations, and the profit that can be gained by selling each item
in later cities along the caravan route.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\enspace\hfil\strut#\hfil\enspace
&\enspace\hfil\strut#\hfil\enspace&\vrule#&&\enspace\hfil\strut#\hfil\enspace\cr
&&&&\multispan4\enspace\hfil\strut Profit if sold in\hfil\enspace\cr
Item&Weight&In city&&B&C&D&E\cr
\omit&\omit&\omit&height2pt\cr
\noalign{\hrule}
\omit&\omit&\omit&height2pt\cr
1&43&A&&\$200&\$300&---&\$450\cr
2&26&A&&\$150&---&\$250&\$375\cr
3&14&B&&&\phantom0\$85&\$130&---\cr
4&19&B&&&\$110&---&\$120\cr
5&35&C&&&&\$225&\$340\cr
6&23&D&&&&&\$260\cr}}$$
The trader's camel can carry a maximum weight of~60. What items should the
trader purchase, and where should the items be sold, in order to maximize
profit by the end of the caravan route?
\par}
{
\def\\#1#2{x_{\rm#1#2}}
\solution For $1\le i\le6$ and $j\in\{\rm B,C,D,E\}$, let $x_{ij}\in\{0,1\}$
denote whether item~$i$ is to be sold in city~$j$. Our objective is to
maximize profit:
$$\eqalign{
{\rm maximize}\quad\phantom{{}+{}}200\\1B+300\\1C\phantom{{}+000\\1D}+450\\1E\cr
{}+150\\2B\phantom{{}+000\\2C}+250\\2D+375\\2E\cr
{}+\phantom085\\3C+130\\3D\phantom{{}+000\\3E}\cr
{}+110\\4C\phantom{{}+000\\4D}+120\\4E\cr
{}+225\\5D+340\\5E\cr
{}+260\\6E&.\cr
}$$
The constraints must ensure that each item is sold at most once:
$$\eqalign{
\\1B+\\1C\phantom{{}+\\1D}+\\1E&\le1\cr
\\2B\phantom{{}+\\2C}+\\2D+\\2E&\le1\cr
\\3C+\\3D\phantom{{}+\\3E}&\le1\cr
\\4C\phantom{{}+\\4D}+\\4E&\le1\cr
\\5D+\\5E&\le1.\cr
}$$
Furthermore, we cannot exceed the camel's capacity on any leg of the journey:
$$\eqalignno{
43(\\1B+\\1C+\\1E)+26(\\2B+\\2D+\\2E)&\le60&\rm[A\to B]\cr
43(\\1C+\\1E)+26(\\2D+\\2E)+14(\\3C+\\3D)+19(\\4C+\\4E)&\le60&\rm[B\to C]\cr
43\\1E+26(\\2D+\\2E)+14\\3D+19\\4E+35(\\5D+\\5E)&\le60&\rm[C\to D]\cr
43\\1E+26\\2E+19\\4E+35\\5E+23\\6E&\le60.\qquad&\rm[D\to E]\cr
}$$
The variable domains are $x_{ij}\in\{0,1\}$ for all $1\le i\le6$ and all
$j\in\{\rm B,C,D,E\}$.
} % end \def\\
\goodbreak
{
\def\\#1#2{{\it x#1#2}}
\noindent The following Maple worksheet solves this integer program.
{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
\hangafter=0 \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
\qquad\it QPSolve]\hfill\cr
}$$
> profit:=(x1b,x1c,x1e,x2b,x2d,x2e,x3c,x3d,x4c,x4e,x5d,x5e,x6e)->\hfil\break
\strut\qquad200*x1b+300*x1c+450*x1e+150*x2b+250*x2d+375*x2e+85*x3c+130*x3d\hfil\break
\strut\qquad+110*x4c+120*x4e+225*x5d+340*x5e+260*x6e;
$$\displaylines{
{\it profit}:=(\\1b,\\1c,\\1e,\\2b,\\2d,\\2e,\\3c,\\3d,\\4c,\\4e,\\5d,\\5e,\\6e)\to200\,\\1b\hfill\cr
\qquad{}+300\,\\1c+450\,\\1e+150\,\\2b+250\,\\2d+375\,\\2e+85\,\\3c+130\,\\3d\hfill\cr
\qquad{}+110\,\\4c+120\,\\4e+225\,\\5d+340\,\\5e+260\,\\6e\hfill\cr
}$$
> sellonce:=[x1b+x1c+x1e<=1,x2b+x2d+x2e<=1,x3c+x3d<=1,x4c+x4e<=1,\hfil\break
\strut\qquad x5d+x5e<=1];
$$\displaylines{
{\it sellonce}:=[\\1b+\\1c+\\1e\le1,\\2b+\\2d+\\2e\le1,\\3c+\\3d\le1,\\4c+\\4e\le1,\hfill\cr
\qquad\\5d+\\5e\le1]\hfill\cr
}$$
> capacity:=[43*(x1b+x1c+x1e)+26*(x2b+x2d+x2e)<=60,\hfil\break
\strut\qquad43*(x1c+x1e)+26*(x2d+x2e)+14*(x3c+x3d)+19*(x4c+x4e)<=60,\hfil\break
\strut\qquad43*x1e+26*(x2d+x2e)+14*x3d+19*x4e+35*(x5d+x5e)<=60,\hfil\break
\strut\qquad43*x1e+26*x2e+19*x4e+35*x5e+23*x6e<=60];
$$\displaylines{
{\it capacity}:=[43\,\\1b+43\,\\1c+43\,\\1e+26\,\\2b+26\,\\2d+26\,\\2e\le60,\hfill\cr
\qquad43\,\\1c+43\,\\1e+26\,\\2d+26\,\\2e+14\,\\3c+14\,\\3d+19\,\\4c+19\,\\4e\le60,\hfill\cr
\qquad43\,\\1e+26\,\\2d+26\,\\2e+14\,\\3d+19\,\\4e+35\,\\5d+35\,\\5e\le60,\hfill\cr
\qquad43\,\\1e+26\,\\2e+19\,\\4e+35\,\\5e+23\,\\6e\le60]\hfill\cr
}$$
> LPSolve(profit(x1b,x1c,x1e,x2b,x2d,x2e,x3c,x3d,x4c,x4e,x5d,x5e,\hfil\break
\strut\qquad x6e),[op(sellonce),op(capacity)],'maximize',assume=binary);
$$\displaylines{
\bigl[1040,[\\1b=1,\\1c=0,\\1e=0,\\2b=0,\\2d=0,\\2e=0,\\3c=0,\\3d=1,\hfill\cr
\qquad\\4c=1,\\4e=0,\\5d=0,\\5e=1,\\6e=1]\bigr]\hfill\cr
}$$
}
\noindent So the optimal strategy for the trader is to buy item~1 in city~A;
sell item~1 and buy items 3~and~4 in city~B; sell item~4 and buy item~5 in
city~C; sell item~3 and buy item~6 in city~D; and sell items 5~and~6 in city~E.
This will yield a total profit of \$1040. \qed
} % end \def\\
\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem A {\it propositional formula\/} with the Boolean operators
$\land$,~$\lor$, and~$\lnot$, meaning {\smfont AND},~{\smfont OR},
and {\smfont NOT}, respectively, can be defined inductively as follows:
\smallskip
\item{(i)} A literal (i.e., a variable or its negation) is a propositional
formula.
\smallskip
\item{(ii)} If $P$~and~$Q$ are propositional formulas, then the conjunction
$(P)\land(Q)$ is a propositional formula.
\smallskip
\item{(iii)} If $P$~and~$Q$ are propositional formulas, then the disjunction
$(P)\lor(Q)$ is a propositional formula.
\smallskip
\item{(iv)} If $P$ is a propositional formula, then the negation~$\lnot(P)$ is
a propositional formula.
\smallskip
\noindent Recall that a propositional formula is in {\it conjunctive normal
form\/} (CNF) if it is a conjunction of disjunctions of literals. For
example, the propositional formula
$$(x_1\lor\bar x_2)\land(\bar x_2\lor\bar x_3)\land(x_1\lor x_2\lor\bar x_3)
\land(\bar x_1\lor x_3)$$
is in conjunctive normal form.
\smallskip
\item{(a)} Prove that any propositional formula with the Boolean operators
$\land$,~$\lor$, and~$\lnot$ can be rewritten as an equivalent formula, on the
same set of variables, in conjunctive normal form. ({\it Equivalent\/} means
that the two formulas have the same set of satisfying variable assignments.)
\smallskip
\item{(b)} Suppose we introduce the Boolean operators $\oplus$~and~$\to$,
having the meanings ``exclusive~{\smfont OR}'' and ``implies,'' respectively.
Show that any propositional formula with the Boolean operators $\land$,~$\lor$,
$\lnot$, $\oplus$, and~$\to$ can be rewritten as an equivalent formula in
conjunctive normal form.
{
\def\true{\hbox{\smfont TRUE}} \def\false{\hbox{\smfont FALSE}}
\solution Here is one approach. Suppose the variables in the given
propositional formula~$F$ are $x_1$,~\dots,~$x_n$. Construct a truth table
for~$F$, with one row for each of the $2^n$~possible assignments of truth
values to the $n$~variables.
For each assignment of truth values to the variables that makes $F$
{\it false}, write a conjunction in which each variable appears positively if
it is assigned the value \true\ and negatively if it is assigned the value
\false. For example, for $n=3$, if the assignment $x_1=\true$, $x_2=\false$,
$x_3=\true$ causes $F$ to be false, then form the conjunction
$x_1\land\bar x_2\land x_3$.
Next, negate each of these conjunctions, and then form the conjunction of the
negations. The resulting formula disallows exactly those variable assignments
that do not satisfy~$F$. For instance, if the only two non-satisfying variable
assignments are $x_1=\true$, $x_2=\false$, $x_3=\true$ and $x_1=\false$,
$x_2=\false$, $x_3=\false$ then the resulting formula is
$$\lnot(x_1\land\bar x_2\land x_3)\land\lnot(\bar x_1\land\bar x_2\land\bar x_3).$$
Now apply De~Morgan's law to each of the negations:
$$(\bar x_1\lor x_2\lor\bar x_3)\land(x_1\lor x_2\lor x_3).$$
The resulting formula~$F'$ is in conjunctive normal form and is equivalent
to~$F$, because an assignment of truth values to the variables satisfies~$F'$
if and only~if it does {\it not\/} cause~$F$ to be false.
Nothing in this construction depends on what Boolean operators appear in the
formula~$F$, so it works for both parts (a)~and~(b). \qed
\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Formulate and solve an integer program to determine truth values for
the Boolean variables $x_1$,~$x_2$, $x_3$, $x_4$, and~$x_5$ so that the
propositional formula
$$\displaylines{
\quad(x_1\oplus x_2)\land(x_3\lor x_4\lor x_5)
\land\lnot[x_3\land(x_4\lor x_5)]\land(\bar x_4\lor\bar x_5)\hfill\quad\cr
\quad\hfill{}\land(x_1\lor x_4\lor x_5)\land(\bar x_1\lor x_3\lor x_5)
\land(x_2\lor x_4\lor x_5)\land(\bar x_2\lor x_3\lor x_5)\quad\cr
}$$
is satisfied, or determine that the formula is unsatisfiable.
\solution First we convert the formula to conjunctive normal form. The
subformula $x_1\oplus x_2$ is equivalent to
$(x_1\lor x_2)\land(\bar x_1\lor\bar x_2)$, and the subformula
$\lnot[x_3\land(x_4\lor x_5)]$ is equivalent to
$$\lnot[(x_3\land x_4)\lor(x_3\land x_5)]
\equiv[\lnot(x_3\land x_4)]\land[\lnot(x_3\land x_5)]
\equiv(\bar x_3\lor\bar x_4)\land(\bar x_3\lor\bar x_5)$$
by the distributive law and De~Morgan's laws. So the given formula is
equivalent to
$$\displaylines{
\quad(x_1\lor x_2)\land(\bar x_1\lor\bar x_2)\land(x_3\lor x_4\lor x_5)
\land(\bar x_3\lor\bar x_4)\land(\bar x_3\lor\bar x_5)
\land(\bar x_4\lor\bar x_5)\hfill\quad\cr
\quad\hfill{}\land(x_1\lor x_4\lor x_5)\land(\bar x_1\lor x_3\lor x_5)
\land(x_2\lor x_4\lor x_5)\land(\bar x_2\lor x_3\lor x_5).\quad\cr
}$$
\goodbreak
\noindent An integer program to find a solution for this instance of the
Boolean satisfiability problem appears below.
$$\eqalign{
{\rm maximize}\quad\rlap0\phantom{(0-x_0)+(0-x_0)}\cr
{\rm subject\ to}\quad\phantom{(0-x_0)+(0-x_0)}\llap{$x_1+x_2$}&\ge1\cr
(1-x_1)+(1-x_2)&\ge1\cr
x_3+x_4+x_5&\ge1\cr
(1-x_3)+(1-x_4)&\ge1\cr
(1-x_4)+(1-x_5)&\ge1\cr
x_1+x_4+x_5&\ge1\cr
(1-x_1)+x_3+x_5&\ge1\cr
x_2+x_4+x_5&\ge1\cr
(1-x_2)+x_3+x_5&\ge1\cr
&\phantom{{}=0}\llap{$x_i\in\{0,1\}$\quad for $1\le i\le5$}.\cr
}$$
\goodbreak
\noindent The following Maple worksheet solves this integer program.
{\smallskip
\raggedright \advance\hsize by-\parindent \hangindent=\parindent
\hangafter=0 \noindent\tt
> restart;\hfil\break
> with(Optimization);
$$\displaylines{
[\it ImportMPS,Interactive,LPSolve,LSSolve,Maximize,Minimize,NLPSolve,\hfill\cr
\qquad\it QPSolve]\hfill\cr
}$$
> clauses:=[x1+x2>=1,(1-x1)+(1-x2)>=1,x3+x4+x5>=1,(1-x3)+(1-x4)>=1,\hfil\break
\strut\qquad(1-x3)+(1-x5)>=1,(1-x4)+(1-x5)>=1,x1+x4+x5>=1,(1-x1)+x3+x5>=1,\hfil\break
\strut\qquad x2+x4+x5>=1,(1-x2)+x3+x5>=1];
$$\displaylines{
{\it clauses}:=[1\le{\it x1}+{\it x2},0\le1-{\it x1}-{\it x2},1\le{\it x3}+{\it x4}+{\it x5},0\le1-{\it x3}-{\it x4},\hfill\cr
\qquad0\le1-{\it x3}-{\it x5},0\le1-{\it x4}-{\it x5},1\le{\it x1}+{\it x4}+{\it x5},0\le-{\it x1}+{\it x3}+{\it x5},\hfill\cr
\qquad1\le{\it x2}+{\it x4}+{\it x5},0\le-{\it x2}+{\it x3}+{\it x5}]\hfill\cr
}$$
> LPSolve(0,clauses,assume=binary);
$$[0,[{\it x1}=0,{\it x2}=1,{\it x3}=0,{\it x4}=0,{\it x5}=1]\bigr]$$
}
\noindent So an assignment of truth values to variables that satisfies the
given formula is $x_1=\false$, $x_2=\true$, $x_3=\false$, $x_4=\false$,
$x_5=\true$. \qed
\medskip
\noindent[The other satisfying assignment is $x_1=\true$, $x_2=\false$,
$x_3=\false$, $x_4=\false$, $x_5=\true$.]
} % end \def\true, \def\false
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Is there a maximum possible (Euclidean) distance between the optimal
solution of an integer program and the optimal solution of its LP relaxation?
If so, give an upper bound for this distance and prove that it is an upper
bound. If not, show how to construct, given any positive real number~$M$, an
integer program whose optimal solution is at least distance~$M$ from the
optimal solution of its LP relaxation.
\solution No, there is no maximum possible distance between the optimal
solution of an integer program and the optimal solution of its LP relaxation.
Here is one construction. Let $M>0$. Let $N$ be an integer greater than or
equal to~$M$ (for example, $N=\lceil M\rceil$). Consider the integer program
$$\eqalign{
{\rm maximize}\quad x_1+4Nx_2\cr
{\rm subject\ to}\quad x_1+2Nx_2&\le N\cr
&\phantom{{}=0}\llap{$x_1\ge0$,\quad$x_2\ge0$}\cr
&\phantom{{}=0}\llap{$x_1$,~$x_2$ integer}.\cr
}$$
The LP relaxation is
$$\eqalign{
{\rm maximize}\quad x_1+4Nx_2\cr
{\rm subject\ to}\quad x_1+2Nx_2&\le N\cr
&\phantom{{}=0}\llap{$x_1\ge0$,\quad$x_2\ge0$}.\cr
}$$
The feasible region of the LP relaxation is shaded in the figure below. Note
that the corners of the feasible region are $(0,0)$, $(N,0)$, and $(0,1/2)$.
Two level curves are drawn: $x_1+4Nx_2=N$ and $x_1+4Nx_2=2N$.
$$\fig{pset07-solns-iplp.mps}$$
The (unique) optimal solution to the LP relaxation is $x_1=0$, $x_2=1/2$, with
objective value~$2N$. This can be seen to be optimal by multiplying the
constraint by~2:
$$2x_1+4Nx_2\le 2N.$$
So, since $x_1$~and~$x_2$ are nonnegative, this implies
$$x_1+4Nx_2\le2x_1+4Nx_2\le2N.$$
Hence a solution that achieves the objective value~$2N$ must be optimal.
Note that the domain $x_1\ge0$ and the constraint $x_1+2Nx_2\le N$ together
imply $2Nx_2\le N$, that~is, $x_2\le1/2$. So all feasible integer solutions
must have $x_2=0$. Therefore the optimal integer solution is $x_1=N$, $x_2=0$,
having objective value~$N$.
The $x_1$-coordinates of these two solutions differ by $N\ge M$, so certainly
their distance apart is at least~$M$. \qed
\vfill\eject %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem Solve the following integer program using the branch-and-bound
technique.
$$\eqalign{
{\rm maximize}\quad2x_1+3x_2&\cr
{\rm subject\ to}\quad\phantom1x_1+\phantom1x_2&\le\phantom06\cr
2x_1+4x_2&\le17\cr
&\phantom{{}=00}\llap{$x_1\ge0$,\quad$x_2\ge0$}\cr
&\phantom{{}=00}\llap{$x_1$,~$x_2$ integer}.\cr
}$$
\solution The feasible region of the LP relaxation appears below.
$$\fig{pset07-solns-bnb-1.mps}$$
\noindent This will correspond to node~0 of our branch-and-bound tree. We solve
the LP relaxation by evaluating the objective function at the corners of the
feasible region.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#\cr
Corner&&Obj.\thinspace value\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$(0,0)$&&0\cr
$(6,0)$&&12\cr
$(3.5,2.5)$&&14.5\cr
$(0,4.25)$&&12.75\cr}}$$
So the optimal solution to the LP relaxation is $x_1=3.5$, $x_2=2.5$, with
objective value~14.5.
Unfortunately, this is not a feasible solution to the integer program, because
neither $x_1$~nor~$x_2$ has an integer value. So we will choose a variable with
a non-integer value and branch on it.
If we choose to branch on~$x_1$ first, we will build the following
branch-and-bound tree. The nodes are numbered in the order they are created.
The top line of each node label specifies the constraint that has been added to
the LP relaxation (in addition to the constraints for nodes higher up in the
tree), and the bottom line gives the optimal solution and optimal objective
value for the corresponding linear program with the added constraints.
\vfill\eject
$$\fig{pset07-solns-bnbtree-1.mps}$$
We begin by excluding the fractional value $x_1=3.5$ by adding one of two new
constraints to the LP relaxation: $x_1\le3$ or $x_1\ge4$. Any feasible integer
solution must satisfy one or the other of these two constraints. This gives us
two new LPs to solve, represented by nodes 1~and~2 in the branch-and-bound tree
above. The feasible regions for these LPs are shown below.
$$\fig{pset07-solns-bnb-2.mps}$$
\noindent The objective function has already been evaluated at some of the
corners in this picture; the objective values at the new corners are given in
the table below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#\cr
Corner&&Obj.\thinspace value\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$(3,0)$&&6\cr
$(3,2.75)$&&14.25\cr
$(4,0)$&&8\cr
$(4,2)$&&14\cr}}$$
So the optimal solution to the LP for node~1 is $x_1=3$, $x_2=2.75$, with
objective value~14.25, and the optimal solution to the LP for node~2 is
$x_1=4$, $x_2=2$, with objective value~14.
Now, node~1 has the larger optimal objective value, but in the optimal solution
the value of~$x_2$ is not an integer. So we must branch on~$x_2$ next. We
exclude the fractional value $x_2=2.75$ by adding one of two new constraints:
$x_2\le2$ or $x_2\ge3$. This gives us two new LPs, represented by nodes 3~and~4
in the branch-and-bound tree. The feasible regions for these LPs are shown
below.
$$\fig{pset07-solns-bnb-3.mps}$$
\noindent The objective values at the new corners are given in the table below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#\cr
Corner&&Obj.\thinspace value\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$(3,2)$&&12\cr
$(0,2)$&&6\cr
$(2.5,3)$&&14\cr
$(0,3)$&&9\cr}}$$
So the optimal solution to the LP for node~3 is $x_1=3$, $x_2=2$, with
objective value~12, and the optimal solution to the LP for node~4 is $x_1=2.5$,
$x_2=3$, with objective value~14.
Now, at this point we have a feasible {\it integer\/} solution with objective
value~14 (the optimal solution to the LP for node~2), and at the other leaf
nodes (nodes 3~and~4) the optimal objective values for the LPs are no greater
than~14, so we can conclude that the solution $x_1=4$, $x_2=2$ found at
node~2 is {\it optimal}, because there cannot be a better solution anywhere
else in the branch-and-bound tree.
[In fact, with slightly more clever reasoning, we could have stopped earlier:
Because the objective function coefficients are integers, the objective value
of any integer solution must be an integer. Therefore, the bound of~14.25 at
node~1 really means that the best possible objective value for an integer
solution below that node is $\lfloor14.25\rfloor=14$, so we cannot possibly
do {\it better\/} than the objective value~14 achieved by the integer solution
at node~2. So we didn't really need to search below node~1. And actually, we
knew at the very beginning (at node~0) that no integer solution could have
objective value better than~14, because the optimal objective value of the LP
relaxation was~14.5, so the objective value of any integer solution can be no
greater than $\lfloor14.5\rfloor=14$.]
If we want to make sure that we have {\it all\/} optimal solutions to the
integer program, we must continue exploring below node~4, because there may be
another integer solution with objective value as good as~14 in that part of the
tree. So we explore below node~4 by branching on~$x_1$. We exclude the
fractional value $x_1=2.5$ by adding one of two new constraints: $x_1\le2$ or
$x_1\ge3$. This gives us two new LPs, represented by nodes 5~and~6 in the
branch-and-bound tree. The feasible regions of these new LPs are shown below.
Note that the constraint $x_1\ge3$, in conjunction with the constraints added
in higher nodes in the branch-and-bound tree, makes the LP infeasible (because
no part of the feasible region for node~4 has $x_1\ge3$).
$$\fig{pset07-solns-bnb-4.mps}$$
\noindent The objective values at the new corners are given in the table below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#\cr
Corner&&Obj.\thinspace value\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$(2,3)$&&13\cr
$(2,3.25)$&&13.75\cr}}$$
So the optimal solution to the LP for node~5 is $x_1=2$, $x_2=3.25$, with
objective value~13.75. Now we know that the integer solution found at node~2
is the unique optimal integer solution, because all of the other leaves in the
branch-and-bound tree (nodes 3,~5, and~6) either have strictly smaller bounds
or are infeasible.
Alternatively, at the beginning, after node~0, we could have chosen to branch
on~$x_2$ rather than~$x_1$. In that case, we would have built the following
branch-and-bound tree.
$$\fig{pset07-solns-bnbtree-2.mps}$$
In this case, we begin by excluding the fractional value $x_2=2.5$ by adding
one of two new constraints: $x_2\le2$ or $x_2\ge3$. This gives us two new LPs,
represented by nodes $1'$~and~$2'$ in the branch-and-bound tree. The feasible
regions of these new LPs are shown below.
$$\fig{pset07-solns-bnb-5.mps}$$
\noindent The objective values of the corners not evaluated for node~0 are
given in the table below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#\cr
Corner&&Obj.\thinspace value\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$(4,2)$&&14\cr
$(0,2)$&&6\cr
$(2.5,3)$&&14\cr
$(0,3)$&&9\cr}}$$
So the optimal solution to the LP for node~$1'$ is $x_1=4$, $x_2=2$, with
objective value~14, and the optimal solution for the LP for node~$2'$ is
$x_1=2.5$, $x_2=3$, also with objective value~14.
At node~$1'$ we have an integer solution with objective value~14, and at the
other leaf node, node~$2'$, we have a bound of~14, meaning that no solution
below that node in the tree can have an objective value better than~14. Hence
the solution $x_1=4$, $x_2=2$ is optimal.
However, as before, if we want to make sure we have {\it all\/} optimal integer
solutions, then we can continue to explore below node~$2'$. We branch on~$x_1$,
excluding the fractional value $x_1=2.5$ by adding one of two new constraints:
$x_1\le2$ or $x_1\ge3$. This gives us two new LPs, represented by the nodes
$3'$~and~$4'$ in the branch-and-bound tree above. The feasible regions of these
new LPs are shown below. Note that the LP for node~$4'$ is infeasible.
$$\fig{pset07-solns-bnb-6.mps}$$
\noindent The objective values at the new corners are given in the table below.
$$\vbox{\offinterlineskip
\halign{&\enspace\hfil\strut#\hfil\enspace&\vrule#\cr
Corner&&Obj.\thinspace value\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$(2,3)$&&13\cr
$(2,3.25)$&&13.75\cr}}$$
So the optimal solution to the LP for node~$3'$ is $x_1=2$, $x_2=3.25$. Now we
know that the integer solution found at node~$1'$ is the unique optimal integer
solution, because all of the other leaves in the branch-and-bound tree (nodes
$3'$~and~$4'$) either have strictly smaller bounds or are infeasible. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem In the {\smfont CUBIC SUBGRAPH} problem, the input is a graph
$G=(V,E)$, and the question to be answered is whether there exists a subgraph
$H=(V',E')$ of~$G$ that is {\it cubic}, meaning that every vertex in the
graph~$H$ has degree~3. Describe how to formulate an integer program to solve
this problem, given a graph $G=(V,E)$. Justify that your formulation correctly
solves the problem.
\solution For each vertex $v\in V$, let $x_v\in\{0,1\}$ indicate whether
$v\in V'$. For each edge $e\in E$, let $y_e\in\{0,1\}$ indicate whether
$e\in E'$. For a vertex $v\in V$, let $E_v=\{\,e\in E:v\in e\,\}$ denote the
set of edges incident upon~$v$. The following integer program can be used to
solve this problem.
$$\eqalign{
{\rm maximize}\quad&0\cr
{\rm subject\ to}\quad&\sum_{\mskip-54mu v\in V\mskip-54mu}x_v\ge1\cr
&\sum_{\mskip-54mu e\in E_v\mskip-54mu}y_e=3x_v\quad\hbox{for all $v\in V$}\cr
&\rlap{$x_v\in\{0,1\}$}\phantom{{}\sum y_e=3x_v}\quad\hbox{for all $v\in V$}\cr
&\rlap{$y_e\in\{0,1\}$}\phantom{{}\sum y_e=3x_v}\quad\hbox{for all $e\in E$}.\cr
}$$
The objective function is~0 because we are not minimizing or maximizing
anything; we are merely searching for a feasible solution (which corresponds to
a cubic subgraph of~$G$). The first constraint ensures that not all of the
variables~$x_v$ will be~0, so that $V'$ will be nonempty. The remaining
constraints ensure that if $x_v=1$ then exactly three edges incident upon~$v$
are chosen to be in~$E'$ (so $v$ has degree~3 in~$H$), and if $x_v=0$ then no
edges incident upon~$v$ are chosen to be in~$E'$. Therefore every feasible
solution to this integer program corresponds to a cubic subgraph of~$G$, and
vice versa, so this integer program will be feasible if and only~if $G$~has a
cubic subgraph. \qed
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bye