<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentstyle[11pt]{article}

\newenvironment{mylist}[1]{
\setbox1=\hbox{#1}
\begin{list}{}{
\setlength{\labelwidth}{\wd1}
\setlength{\leftmargin}{\wd1}
  \addtolength{\leftmargin}{1em}
  \addtolength{\leftmargin}{\labelsep}
\setlength{\rightmargin}{1em}}}{\end{list}}

\newcommand{\litem}[1]{\item[#1\hfill]}
\newcommand{\ritem}[1]{\item[#1]}

\newcounter{questnum}
\newcommand{\question}[1]{
\vspace{.1in}
  \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum: }}

\newcommand{\titledquestion}[2]{
 \refstepcounter{questnum}
{\bf \medskip Problem \thequestnum:} #2 {\normalsize (#1 pts) \\}}

\newcommand{\answerspace}{\verb+                                  +
\underline{\makebox[2.0in]{}}}
\newcommand{\smanswerspace}{\underline{\makebox[0.5in]{}}}

\setlength{\topmargin}{-0.5 in}
\setlength{\oddsidemargin}{0 in}
\setlength{\textheight}{8.75 in}
\setlength{\textwidth}{6.5 in}
\setlength{\parindent}{0.0 in}

\begin{document}

{\large 
CS294-3: Algorithms in the real world \hfill Assignment 3 (Linear and Integer Programming)\\[.03in]
Due: Wednesday Oct 15, 1997\\[.1in]
}

Please feel free to send me email if there are any ambigouous questions.

\question{??}
Strang Chapter 8 problem 8.1.9

\question{??}
Strang Chapter 8 problem 8.2.1.


\question{??} 
Strang Chapter 8 problem 8.2.13.

\question{??}

Consider the following problem

\begin{center}
\begin{tabular}{lcl}
  maximize   &amp; &amp; $x_1 + x_2$ \\
  subject to &amp; &amp; $2 x_1 + x_2 \leq 4$ \\
             &amp; &amp; $x1,x2 \geq 0$ 
\end{tabular}
\end{center}

\begin{description}
\item[(a)]
Starting with the initial solution $(x_1,x_2) = .1,.1$
solve this problem using the affine scaling interior-point method.

\item[(b)]
Illustrate the progress of the algorithm on the the graph in $x_1-x_2$ space.
\end{description}

\question{??}

Let $S = \{x \in R^n : Ax \leq b\}$
and $T = \{x \in R^n : Bx \leq d\}$.
Assuming that $S$ and $T$ are nonempty, describe a polynomial time
algorithm (in $n$) for checking whether $S \subset T$.


\question{??}

Formulate the following problem as a mixed integer programming problem.

\begin{center}
\begin{tabular}{lcl}
maximize &amp; &amp; $f_1(x) + f_2(x)$\\
subject to &amp; &amp; at least two of the following 
$\begin{array}{l}
x_1 + 3 x_2 \leq 12\\
2 x_1 + x_2 \leq 16 \\
x_1 + x_2 \leq 9
\end{array}$\\
&amp; &amp; $x_1, x_2 \geq 0$
\end{tabular}
\end{center}
where
\begin{eqnarray*}
f_1(x_1) &amp; = &amp; \left\{
\begin{array}{lll}
10 + 2 x_1, &amp; &amp; 0 \leq x_1 \leq 5\\
15 + x_1, &amp; &amp; \mbox{otherwise}
\end{array}\right. \\
f_2(x_2) &amp; = &amp; \left\{
\begin{array}{lll}
8 + x_2, &amp; &amp; 0 \leq x_2 \leq 2\\
4 + 3 x_2 &amp; &amp; \mbox{otherwise}
\end{array}\right. \\
\end{eqnarray*}

\newpage
\question{??}

Solve the following problem using the branch-and-bound integer
programming procedure describe in class.  Feel free to do
it graphically.
\begin{center}
\begin{tabular}{lcl}
maximize &amp; &amp; $2 x_1 + x_2$\\
subject to 
&amp; &amp; $2 x_1 - 2 x_2 \leq 3$\\
&amp; &amp; $- 2x_1 + x_2 \leq 2$\\
&amp; &amp; $2 x_1 + 2 x_2 \leq 13$\\
&amp; &amp; $x_1, x_2 \geq 0$\\
&amp; &amp; $x_1, x_2$ integers
\end{tabular}
\end{center}

\question{??}

Solve the following problem using implicit enumeration (the 0-1 programming
technique) describe in class.

\begin{center}
\begin{tabular}{lcl}
minimize &amp; &amp; $3 x_1 + 2 x_2 + 5 x_3 + x_4$\\
subject to 
&amp; &amp; $- 2 x_1 + x_2 - x_3 - 2 x_4 \leq -2$\\
&amp; &amp; $- x_1 - 5 x_2 - 2 x_3 + 3 x_4 \leq -3$\\
&amp; &amp; $x_1, x_2, x_3, x_4$ binary
\end{tabular}
\end{center}

\end{document}
</pre></body></html>