
	\be
	\item Use the branch and bound method to solve each of the following ILPs.
		\be
		\item
		\begin{align*}
		 \mbox{maximize } z &=2x_1+3x_2  \\
		\mbox{ subject to} \notag\\
		2x_1  +x_2 &\leq 7 \notag\\
		x_1+2x_2 &\leq 7  \notag\\
		x_1,x_2 &\geq 0; x_1,x_2 \in \Z \notag
		\end{align*}	
		\item
		\begin{align*}
		 \mbox{maximize } z &=5x_1+6x_2  \\
		\mbox{ subject to} \notag\\
		2x_1  +3x_2 &\leq 18 \notag\\
		2x_1+x_2 &\leq 12  \notag\\
    3x_1+3x_2 &\leq 20  \notag\\
		x_1,x_2 &\geq 0; x_1,x_2 \in \Z \notag
		\end{align*}
	\item
		\begin{align*}
		 \mbox{maximize } z &=4x_1 + 3x_2 +5x_3  \\
		\mbox{ subject to} \notag\\
		x_1+x_2+x_3 &\leq 17 \notag\\
		6x_1+3x_2 +3x_3 &\leq 22  \notag\\
		3x_1+3x_2  \x &\leq 13 \notag \\
		x_1,x_2,x_3 &\geq 0; x_1, x_2, x_3 \in \Z \notag
		\end{align*}
        \ee
\item Solve the mixed-integer linear programming problem that arises by restricting only $x_2$ and $x_3$ to be integers in 1c.
    	
\item To what digits (0-9) can one assign each of the letters in the phrase below to make the
	equation mathematically valid?
	\begin{equation}\label{E:IPEnigmaProblem}
	\mbox{one + one + two + two + three + eleven = twenty}
	\end{equation}
\noi
(Hint: Note that only ten letters of the alphabet are used in this statement so
that we may number the letters. For example, suppose we
number ``o'', ``n'', and ``e'' as 1, 2,
and 3, respectively.
If we define $x_{ij}$,
where $1 \leq i \leq 10$ and $0 \leq j \leq 9$ is a binary decision variable whose solution value
is 1 provided letter $i$ corresponds to digit $j$, then
the letter ``o'' is represented by the sum,
$\ds \sum_{j=0}^9 j x_{1j}$, the letter ``n'' by the sum
$\ds \sum_{j=0}^9 j x_{2j}$, and the letter ``e'' by the sum
$\ds \sum_{j=0}^9 j x_{3j}$. This means that the word ``one'' is represented
by the sum
\begin{equation*}
100 \sum_{j=0}^9 j x_{1j}+ 10 \sum_{j=0}^9 j x_{2j} + \sum_{j=0}^9 j x_{3j}.
\end{equation*}

\noi
Other words are constructed in a similar manner. Constraints arise from
Equation (\ref{E:IPEnigmaProblem}), together with the that fact
each digit corresponds to exactly one letter and that equation. Since the goal is merely one of determining feasible values for these variables, the objective function can be chosen as a constant and the goal as either maximization or minimization.)

\item Suppose Jane wishes to bring snacks high in carbohydrate content with her as she
completes her bicycle ride. Weights and carbohydrate
content for her five choices are summarized in Table \ref{Ta:Exercises_Carbs}.
If Jane believes she can only afford to bring 100 grams of food with her as she rides,
how many of each snack should she bring so as to maximize her total carbohydrate intake? What if Jane can bring 125 grams instead? 150 grams? (Note: An IP having only one constraint, such as this, is an example of a \emph{knapsack problem}.)\index{knapsack problem}

\begin{table}[h]
    \caption{Weight and nutritional data taken from
    manufacturer's web sites}\label{Ta:Exercises_Carbs}
	\begin{tabular}{|c|c|c|c|c|c|}
	\hline
	Item  & Cereal Bar &  Powerbar \texttrademark & Cliff Bar \texttrademark & Luna Bar \texttrademark & GU Gel \texttrademark \\ \hline
	Carbs (gms.) & 29 & 43 & 42 & 27 & 25   \\ \hline
	Weight (gms.) & 42 & 65 & 68 & 48 & 32 \\ \hline
	\end{tabular}
    \end{table}

    \item Coach Anderson must decide his baseball team's pitching rotation.\footnote{Based upon Machol, \cite{Machol_Assignment}, (1970).} The rotation  will consist of four starting pitchers, one mid-innings relief itcher, and one ``closer,'' (i.e., late inning pitcher). Coach Sparky has
    six pitchers, whose earned-run-averages (ERAs) in these various roles are summarized in Table \ref{Ta:Exercises_BaseballAssignment}.

   \begin{table}[h]
\caption{Pitching data for Coach Anderson's team}\label{Ta:Exercises_BaseballAssignment}
	\begin{tabular}{|c|c|c|c|}
	\hline
	Pitcher/E.R.A. & Starting & Mid-Innings Relief & Closer \\ \hline
	Clay & 3.5  & 2.8 & 2.7 \\ \hline
	Don & 2.42 & 2.45 & 2.8 \\ \hline
    Gary & 3.16 & 3.2 & 3.6 \\ \hline
    Jack & 2.5 & 2.6  & 2.8 \\ \hline
    Pedro & 2.7 & 2.8 & 2.95 \\ \hline
    Rawley & 3 & 2.7 &  2. 6  \\ \hline
	\end{tabular}
	\end{table}

    \noi If each pitcher serves in exactly one role and if the average combined earned-run-average is the average of the six pitchers'
    earned-run-averages
    in their assigned roles, what pitching rotation should Coach Anderson choose
    in order to minimize the average combined earned-run-average?
	
	\item The \emph{$n$-Queens Problem}\index{n-Queens Problem} asks for the largest number of queens that can be placed on an $n$-by-$n$ chessboard  so that no two queens are capable of attacking one another.\footnote{Based upon
	Letavec and Ruggiero, \cite{Letavec_NQueensProblem}, (2002).} Construct a BLP that solves the 8-Queens Problem. That is, solve the problem for the standard size chessboard. (Hint: Let $x_{ij}$, where $1 \leq i,j \leq 8$, denote a binary decision variable whose solution value equals 1 provided a queen occupies the entry in row $i$, column $j$ of the chessboard. Then the sum of the decision variables along each column, each row, and each diagonal cannot exceed 1.)


	\item Suppose $m$ is a positive integer, and let $n=m^2$. In the $n$-by-$n$ \emph{Sudoku} puzzle\index{Sudoku}, a player is given an $n$ by $n$ grid comprised of $n$, $m$ by $m$ non-overlapping sub-grids.\footnote{Based upon Bartlett, et al., \cite{Bartlett_Sudoku}, (2008).} A digit between $1$ and $n$ appears in certain grid entries. The goal of the puzzle is to enter a digit between 1 and $n$ in each of the remaining grid entries so that each row, each column, and each $m$-by-$m$ sub-grid contains exactly one of the $n$ digits. An example of a 4-by-4 puzzle is depicted in Table \ref{Ta:Exercises_Int_Prog_Sudoku}. In this case
$m=2$ and $n=4$.
	
	\begin{table}[h]
    \caption{Example of a 4-by-4 Sudoku puzzle}\label{Ta:Exercises_Int_Prog_Sudoku}
	\begin{tabular}{||c|c||c|c||}
	\hline \hline
     & 1 & &  \\  \hline
     & & 2 & \\ \hline \hline
     & & & 4 \\ \hline
     3 & & & \\ \hline \hline
	\end{tabular}
	\end{table}
    \be
	\item Formulate a BLP that solves the $n$-by-$n$ Sudoku puzzle. To get started, let $x_{ijk}$, where $1 \leq i,j,k \leq n$, denote a binary decision variable, whose solution value equals 1 provided the entry in row $i$, column $j$ of the puzzle equals $k$, and zero otherwise. Let the objective of the BLP be any constant function; the constraints correspond to feasible puzzle solutions and can be broken down as follows:
\be
\item Each column contains one entry equal to $k$, where $1 \leq k \leq n$.
\item Each row contains one entry equal to $k$, where $1 \leq k \leq n$.
\item Every position in the puzzle must be filled.
\item Certain puzzle entries are known from the outset. This can be stated as a sequence
of values, $x_{ijk}=1$, where each $(i,j,k)$ is a triple satisfying $1 \leq i,j,k \leq n$.
\item Each $m$-by-$m$ sub-grid contains exactly one of the $n$ digits. (Hint: Let $B_{p,q}$,
where $1 \leq p,q \leq m$, denote a sub-grid of the puzzle. Then the entries
of this sub-grid can be indexed by ordered pairs, $(i,j)$, where
$mp-m+1 \leq i \leq  mp$ and $mq-m+1 \leq j \leq mq$.)
\ee
\item Use your result to solve the puzzle shown in Table \ref{Ta:Exercises_Int_Prog_Sudoku}.
\ee

\item
When an individual writes numerous checks, the possibility exists that his or her bank will present several checks for payment against his or her account on the same day.\footnote{Based upon  Apte, et al.,\cite{Apte_NSFfees}, (2004).}
Depending upon the individual's account balance and the sequence in which these checks are processed, varying amounts of insufficient fund (NSF) fees can be collected
by the bank. Some banks have used sequencing policies that maximize their total collected NSF
fees, a policy that has resulted in several lawsuits.

\newpar
Consider an example in which Joe Freshman has a balance of  \$1200 in his banking account, which charges a \$20 NSF fee per bounced check. On a particular day, the bank receives seven checks that it presents against Joe Freshman's account. These checks are for the following amounts:
\$30, \$80 ,\$140, \$160, \$500, \$600, and \$800.
\be
\item Under a low-high policy, checks presented on the same day are processed in the order of lower to higher check amounts. Calculate the total amount of NSF fees the bank charges Joe under this policy.
\item Under a high-low policy, checks presented on the same day are first listed in order of descending amounts. Starting at the top of
    the list, the bank ascertains whether the current balance exceeds the given check amount. If so,
    the bank clears the check by deducting its amount from the current balance and then moves to the next check on this list. If not, the bank charges an NSF fee before proceeding to the next check, which
    is of smaller amount and therefore may not necessarily bounce. Calculate the total amount
    of NSF fees the bank charges Joe under this policy. Your value should be larger than that
    charged in (a).

\newpar
To determine which strategy is optimal for Joe and which is optimal for the bank, we let
$c_i$ represent the amount of check $i$ and let $x_i$, where $1 \leq i \leq 7$, denote a binary decision variable whose solution value equals 0 provided check $i$ ``bounces'' and equals 1 if the check ``clears.''
\item Formulate an expression for the total NSF fees collected by the bank.
\item Determine a constraint that represents the fact that the account balance is at least as large
as the sum of the cleared checks.
\item Set up and solve a BLP that
determines the order in which checks should be processed so as to minimize the total NSF fees. How does
this result compare with the low-high policy?
\item Now construct a new BLP that spells out the order in which the bank should process the checks so as to maximize
the NSF fees it collects. Your objective function will be the same as that in the previous question. However, your goal will now be to maximize as opposed to minimize. To the previous BLP you will also need to add seven new constraints, which help the bank identify checks that can be ``made to bounce,'' so to speak. By considering the separate cases, $x_j=0$ and $x_j=1$, explain why the following constraints assist the bank in achieving this goal:
\begin{equation*}
 1200x_j+c_j \geq (1200+.01) - \sum_{i=1}^7 c_i x_i \mbox{, where $1 \leq j \leq 7$.}
 \end{equation*}
\noi
\item How does the solution of the BLP from the previous question compare with that of the high-low policy?
\ee
	
\ee
