\documentclass[11pt]{article}
\usepackage{pictex, latexsym, graphicx,amsmath,amssymb,amsbsy,amsfonts,amsthm,verbatim}
\usepackage{fullpage}
\setlength{\parindent}{0em}

\def\vx{\mathbf{x}}
\def\vc{\mathbf{c}}
\def\vb{\mathbf{b}}
\def\vy{\mathbf{y}}

\begin{document}

\thispagestyle{empty}
\begin{center}
\textbf{\large
Fall 2013 \qquad Math 566 \qquad Implementation Assignment 4 
}
\end{center}

\vspace{1em}
\textbf{\large Problem: Branch-and-Bound Techniques for ILP}

In this report, you will use a linear programming solver to assist you in evaluating some integer programs using Branch-and-Bound.
It is not expected that you build a full algorithm to automate a branch-and-bound algorithm, but you must follow such an algorithm.
You are not to use an integer programming solver.

With each integer program below, you will describe the solution and the branch-and-bound tree, including:
In what order did you expand the nodes? What variable branches were used? How did you select which node to branch on? How did you select which variable to branch on? For every leaf: why did it terminate?

\textbf{\large Questions to Answer in Your Report}

\textbf{Q1.} What linear programming solver did you use?

\textbf{Q2.} How did you store your branch-and-bound tree?

\textbf{Q3.} How did you encode the branching constraints?

\textbf{Q4.} What was the most difficult part of this assignment?


\vspace{1em}

\textbf{\large Problem Instances.}

\textbf{I1.}
\[\begin{array}{rrcrcrcl}
\min & 3x_1 & + & x_2 & + & 2x_3 &&\\
\text{subject to}
	& x_1  & + & x_2 & + & 2x_3 & \geq & 6 \\
	& & & 12x_2 & - & x_3 & \geq & 5 \\
	& 5x_1 & - & x_2 & & & \geq & 0 \\
	& x_1, & & x_2, && x_3 & \geq & 0\\
	& x_1, & & x_2, && x_3 && \text{integer}
\end{array}
\]


\textbf{I2.} 
\[\begin{array}{rrcrcrcrcrcl}
\min &&&&&&&&&x_5&&\\
\text{subject to} 
& 2x_1 & + & 2x_2 & + & 2x_3 & + & 2x_4 & + & x_5 &=&5\\
& x_1, && x_2, && x_3, && x_4, && x_5 & \in & \{0,1\}
\end{array}
\]


\textbf{I3.}
\[\begin{array}{rrcrcrcrcrcl}
\min &25x_1&+&16x_2&+&9x_3&+&4x_4&+&x_5&&\\
\text{subject to}
& x_1 & + & x_2 & + & x_3 & && && \geq & 1\\
& -x_1 & - & x_2 & & & + & x_4 &&& \geq & -1\\
& -x_1 & && &&-& x_4 & + & x_5& \geq &0\\
& &&x_2&-&x_3&&&+&x_5&\geq&0\\
&& && & x_3 & - & x_4 & - & x_5& \geq & -1\\
&x_1 & & &&& + & x_4 & - & x_5 & \geq& 0\\
& x_1, && x_2, && x_3, && x_4, && x_5 & \in & \{0,1\}
\end{array}
\]


\textbf{I4.}
\[\begin{array}{rrcrcrcrcrcrcl}
	\min & x_1 & + & x_2 & + & x_3 & + & x_4 & + & x_5 & + & x_6 & & \\
	\text{subject to}
		& x_1 & + & x_2 && && && && & \geq & \frac{5}{3}\\ 
		& x_1 &  &  &+&x_3 && && && & \geq & \frac{3}{4}\\
		& &  & x_2 && &+&x_4 && &+&x_6 & \geq & \frac{3}{2}\\
		&  & &  && && &&x_5 &+& x_6& \geq & \frac{1}{2}\\
		& && && x_3&+& x_4&+&x_5 && & \geq & 1\\
		& x_1,&& x_2,&& x_3,&& x_4,&& x_5, && x_6 &\geq & 0, \text{integer}
	\end{array}
\]


\end{document} 