%  Problem set 6
%  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

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

\headline={\hfil}
\footline={\hfil}

\newcount\pno \pno=0
\def\problem{\global\advance\pno by1%
	\medskip\filbreak\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}

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

\centerline{\titlefont Combinatorial Optimization}
\smallskip
\centerline{\bf Problem set~7}
\smallskip
\centerline{Assigned Friday, June~26, 2015. Due Wednesday, July~1, 2015.}

\medskip

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

\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}

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

\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{} [Hint: Write a formula that rules out all of the non-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.

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

\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.

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

\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.

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

\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
}$$

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

\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.

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

\bye
