\documentclass[dvips,10pt,b5paper]{book}

\usepackage[T1]{fontenc}
\usepackage{lmodern}
\usepackage[dvips]{graphicx}

\usepackage{epsfig}
\usepackage{graphicx}

\usepackage{multirow}
\usepackage{enumerate}

\usepackage{AlgofInfColor9December2010}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Automata
\usepackage{emlines,emlines2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Compilers
\usepackage[emtex,dvips,all]{xy} 
\usepackage{hhline} 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Reliable
\usepackage{enumerate}
\usepackage{amsmath,amssymb}

\addtocounter{part}{0}
\addtocounter{chapter}{23}
\setcounter{page}{1251}
\setcounter{tocdepth}{2}

\topmargin -10mm
\oddsidemargin 0.0in
\evensidemargin 0.0in

\makeindex


\sloppy

\begin{document}


\tableofcontents


\chapter{The Branch and Bound Method\label{chapterBranch}}
%12345678901234567890123456789012345678901234567890123456789012345678901234567890
It has serious practical consequences if it is known that a combinatorial problem 
is NP-complete. Then one can conclude according to the present state of 
science that no simple combinatorial algorithm can be applied and only an 
enumerative-type method can solve the problem in question. Enumerative methods are 
investigating many cases only in a non-explicit, i.e. implicit, way. It means 
that huge majority of the cases are dropped based on consequences obtained from 
the analysis of the particular numerical problem. The three most important enumerative 
methods are (i) implicit enumeration, (ii) dynamic programming, and (iii) 
branch and bound method. This chapter is devoted to the latter one. Implicit 
enumeration and dynamic programming can be applied within the family of optimization 
problems mainly if all variables have discrete nature. Branch and bound method can 
easily handle problems having both discrete and continuous variables. Further on the 
techniques of implicit enumeration can be incorporated easily in the branch and bound 
frame. Branch and bound method can be applied even in some cases of nonlinear
programming.

The {\em Branch and Bound} (abbreviated further on as B\&B) method is just a frame of a 
large family of methods. Its substeps can be carried out in different ways depending 
on the particular problem, the available software tools and the skill of the designer 
of the algorithm.

Boldface letters denote vectors and matrices; calligraphic letters are used for sets.
Components of vectors are denoted by the same but non-boldface letter. Capital letters
are used for matrices and the same but lower case letters denote their elements.
The columns of a matrix are denoted by the same boldface but lower case letters.

Some formulae with their numbers are repeated several times in this chapter. The reason
is that always a complete description of optimization problems is provided. Thus the fact
that the number of a formula is repeated means that the formula is {\em identical} to the
previous one.

\section{An example: the Knapsack Problem}
In this section the branch and bound method is shown on a numerical example. The 
problem is a sample of the binary knapsack problem which is one of the easiest 
problems of integer programming but it is still NP-complete. The calculations are carried 
out in a brute force way to illustrate all features of B\&B. More intelligent 
calculations, i.e. using implicit enumeration techniques will be discussed only at 
the end of the section.

\subsection{The Knapsack Problem}\index{knapsack problem}
There are many different knapsack problems. The first and classical one is the binary
knapsack problem. It has the following story. A tourist is planning a tour in the
mountains. He has a lot of objects which may be useful during the tour. For example
ice pick and can opener can be among the objects. We suppose that the following conditions 
are satisfied.
\begin{itemize}
\item Each object has a positive value and a positive weight. (E.g. a balloon filled
with helium has a negative weight. See Exercises \ref{ex241-1} and \ref{ex241-2}) The value is the degree of 
contribution of the object to the success of the tour.
\item The objects are independent from each other. (E.g. can and can opener are not 
independent as any of them without the other one has limited value.)
\item The knapsack of the tourist is strong and large enough to contain all
possible objects.
\item The strength of the tourist makes possible to bring only a limited total weight.
\item But within this weight limit the tourist want to achieve the maximal total value.
\end{itemize}

The following notations are used to the mathematical formulation of the problem:
\begin{eqnarray*}
\begin{array}{ll}
n & \hbox{the number of objects;}\\
j & \hbox{the index of the objects;}\\
w_j & \hbox{the weight of object}\; j;\\
v_j & \hbox{the value of object}\; j;\\
b & \hbox{the maximal weight what the tourist can bring.}
\end{array}
\end{eqnarray*}

For each object $j$ a so-called {\em binary} or {\em zero-one} decision variable, say
$x_j$, is introduced:
\begin{eqnarray*}
x_j=\left\{\begin{array}{ll}1 & \hbox{if object }j\hbox{ is present on the tour}\\
0 & \hbox{if object }j\hbox{ isn't present on the tour.}
\end{array}\right.
\end{eqnarray*}
Notice that 
\begin{eqnarray*}
w_jx_j=\left\{\begin{array}{ll}w_j & \hbox{if object }j\hbox{ is present on the tour,}\\
0 & \hbox{if object }j\hbox{ isn't present on the tour}\end{array}
\right.
\end{eqnarray*}
is the weight of the object in the knapsack.

Similarly $v_j x_j$ is the value of the object on the tour. The total weight in the 
knapsack is
\begin{eqnarray*}
\sum_{j=1}^n w_jx_j
\end{eqnarray*}
which may not exceed the weight limit. Hence the mathematical form of the problem is
\begin{eqnarray}\label{e1}
\max \sum_{j=1}^n v_j x_j
\end{eqnarray}
\vspace{-2mm}
\begin{eqnarray}\label{e2}
\sum_{j=1}^n w_j x_j\leq b
\end{eqnarray}
\vspace{-2mm}
\begin{eqnarray}\label{e3}
x_j = 0\;\hbox{or}\,1,\;\;\;j=1,\ldots,n\;.
\end{eqnarray}

The difficulty of the problem is caused by the integrality requirement. If constraint
(\ref{e3}) is substituted by the relaxed constraint, i.e. by\index{relaxed constraint}
\begin{eqnarray}\label{e4}
0\leq x_j \leq 1,\;\;\;j=1,\ldots,n\;,
\end{eqnarray}
then the Problem (\ref{e1}), (\ref{e2}), and (\ref{e4}) is a linear programming
problem. (\ref{e4}) means that not only a complete object can be in the knapsack
but any part of it. 
Moreover it is not necessary to apply the simplex method or any other LP
algorithm to solve it as its optimal solution is described by

\begin{tetel}\label{t1}
Suppose that the numbers $v_j,w_j$ $(j=1,\ldots,n)$ are all positive and moreover the
index order satisfies the inequality
\begin{eqnarray}\label{e5}
\frac{v_1}{w_1}\geq\frac{v_2}{w_2}\cdots\geq\frac{v_n}{w_n} \koz.
\end{eqnarray}
Then there is an index $p$ $(1\leq p\leq n)$ and an optimal solution 
${\bf x}^{*}$ such that 
\begin{eqnarray*}%\label{e6}
x^{*}_1=x^{*}_2=\cdots=x^{*}_{p-1}=1,\;x^{*}_{p+1}=x^{*}_{p+2}=\cdots=x^{*}_{p+1} = 0 \koz.
\end{eqnarray*}
\end{tetel}

Notice that there is only at most one non-integer component in ${\bf x}^{*}$. This property will
be used at the numerical calculations. 

From the point of view of B\&B the relation of the Problems (\ref{e1}), (\ref{e2}), and  
(\ref{e3}) and (\ref{e1}), (\ref{e2}), and (\ref{e4}) is very important. Any feasible solution of the
first one is also feasible in the second one. But the opposite statement is not true.
In other words the set of feasible solutions of the first problem is a proper subset of
the feasible solutions of the second one. This fact has two important consequences:
\begin{itemize}
\item The optimal value of the Problem (\ref{e1}), (\ref{e2}), and (\ref{e4}) is an upper 
bound of the optimal value of the Problem (\ref{e1}), (\ref{e2}), and (\ref{e3}).
\item If the optimal solution of the Problem (\ref{e1}), (\ref{e2}), and (\ref{e4}) is 
feasible in the Problem (\ref{e1}), (\ref{e2}), and (\ref{e3}) then it is the optimal
solution of the latter problem as well.
\end{itemize}
These properties are used in the course of the branch and bound method intensively.

\subsection{A numerical example}
The basic technique of the B\&B method is that it divides the set of feasible solutions
into smaller sets and tries to fathom them. The division is called 
\ki{branching}\inddef{branching} as 
new branches are created in the enumeration tree. 
A subset is fathomed if it can be determined  exactly if it contains an optimal solution. 

To show the logic of B\&B the problem
\begin{eqnarray}\label{e7}
\begin{array}{crrrrrrrrrcl}
\max & 23x_1 & + & 19x_2 & + & 28x_3 & + & 14x_4 & + & 44x_5\\
& 8x_1 & + & 7x_2 & + & 11x_3 & + & 6x_4 & + & 19x_5 & \leq & 25\;\;\;\;\;\\
\multicolumn{12}{c}{x_1,x_2,x_3,x_4,x_5= 0\;\hbox{or}\,1}
\end{array}
\end{eqnarray}
will be solved. The course of the solution is summarized on Figure \ref{f241}.

Notice that condition (\ref{e5}) is satisfied as
\begin{eqnarray*}
\frac{23}{8}=2.875>\frac{19}{7}\approx 2.714>\frac{28}{11}\approx 2.545>
\frac{14}{6}\approx 2.333>\frac{44}{19}\approx 2.316 \koz.
\end{eqnarray*}
The set of the feasible solutions of (\ref{e7}) is denoted by ${\cal F}$, i.e.
\[{\cal F}=\{{\bf x}\mid 8x_1 + 7x_2 + 11x_3 + 6x_4 + 19x_5 \leq 25;
\;x_1,x_2,x_3,x_4,x_5= 0\;\hbox{or}\,1\}.\]
The continuous relaxation of (\ref{e7}) is
\index{relaxation}\index{continuous relaxation}
\begin{eqnarray}\label{e8}
\begin{array}{crrrrrrrrrcl}
\max & 23x_1 & + & 19x_2 & + & 28x_3 & + & 14x_4 & + & 44x_5\\
& 8x_1 & + & 7x_2 & + & 11x_3 & + & 6x_4 & + & 19x_5 & \leq & 25\;\;\;\;\;\\
\multicolumn{12}{c}{0\leq x_1,x_2,x_3,x_4,x_5\leq 1\koz.}
\end{array}
\end{eqnarray}
The set of the feasible solutions of (\ref{e8}) is denoted by ${\cal R}$, i.e.
\[{\cal R}=\{{\bf x}\mid 8x_1 + 7x_2 + 11x_3 + 6x_4 + 19x_5 \leq 25;
\;0\leq x_1,x_2,x_3,x_4,x_5\leq 1\}.\]
Thus the difference between (\ref{e7}) and (\ref{e8}) is that the
value of the variables must be either 0 or 1 in (\ref{e7}) and on the other 
hand they can take any value from the closed interval $[0,1]$ in the case
of (\ref{e8}).

Because Problem (\ref{e7}) is difficult, (\ref{e8}) is solved instead. The optimal
solution according to Theorem \ref{t1} is
\[x^{*}_1=x^{*}_2=1, x^{*}_3=\frac{10}{11}, x^{*}_4=x^{*}_5=0 \koz.\]
As the value of $x^{*}_3$ is non-integer, the optimal value 67.54 is just an upper bound
of the optimal value of (\ref{e7}) and further analysis is needed. The value 67.54
can be rounded down to 67 because of the integrality of the coefficients in the objective
function.

The key idea is that the sets of feasible solutions of both problems are divided into
two parts according the two possible values of $x_3$. The variable $x_3$ is chosen as its
value is non-integer. The importance of the choice is discussed below.
\begin{center}
\vspace{-8mm}
\begin{figure}[!t]\label{f241}
\unitlength 1mm
\vspace{-8mm}
\begin{picture}(100,150)

\put(61,22){\circle{15}}
\put(49,20){\large\bf 6}
\put(58,18){63.32}
\put(58,24){${\cal R}_5$}
\put(54,22){\line(1,0){14}}


\put(91,29){\line(-2,3){13}}
\put(92,22){\circle{15}}
\put(80,20){\large\bf 7}
\put(89,18){$-\infty$}
\put(89,24){${\cal R}_6$}
\put(85,22){\line(1,0){14}}
\put(86,38){$x_1=1$}

\put(65,29){\line(2,3){13}}
\put(79,55){\circle{15}}
\put(67,53){\large\bf 5}
\put(74,51){67.127}
\put(75,57){${\cal R}_4$}
\put(72,55){\line(1,0){14}}
\put(60,38){$x_1=0$}
\put(79,62){\line(-2,3){13}}
\put(77,68){$x_2=1$}

\put(48,62){\line(2,3){13}}
\put(48,55){\circle{15}}
\put(36,53){\large\bf 4}
\put(45,51){65}
\put(44,57){${\cal R}_3$}
\put(41,55){\line(1,0){14}}
\put(39,68){$x_2=0$}
\put(15,11){\framebox(30,20){
\parbox{28mm}{ $x_1=x_3=x_4=1$\\ $x_2=x_5=0$}}}
\put(32,32){\line(2,3){11.9}}

\put(60,95){\line(-2,3){13}}
\put(61,88){\circle{15}}
\put(49,86){\large\bf 3}
\put(58,84){67.28}
\put(58,90){${\cal R}_2$}
\put(54,88){\line(1,0){14}}
\put(58,101){$x_3=1$}

\put(28,95){\line(2,3){13}}
\put(26.0,88){\circle{15}}
\put(14,86){\large\bf 2}
\put(23,84){65.26}
\put(23,90){${\cal R}_1$}
\put(19,88){\line(1,0){14}}
\put(17,101){$x_3=0$}

\put(44.0,121){\circle{15}}
\put(32,119){\large\bf 1}
\put(39,117){67.45}
\put(41,123){${\cal R}_0$}
\put(37,121){\line(1,0){14}}

\end{picture}
\caption{ The first seven steps of the solution}
\end{figure}
\end{center}

Let 
\[{\cal F}_0={\cal F},\;{\cal F}_1={\cal F}_0\cap\{{\bf x}\mid x_3=0\},\;
{\cal F}_2={\cal F}_0\cap\{{\bf x}\mid x_3=1\}\]
and
\[{\cal R}_0={\cal R},\;
{\cal R}_1={\cal R}_0\cap\{{\bf x}\mid x_3=0\},\;
{\cal R}_2={\cal R}_0\cap\{{\bf x}\mid x_3=1\} \koz.\]
Obviously
\[{\cal F}_1\subseteq{\cal R}_1\hbox{  and  }{\cal F}_2\subseteq{\cal R}_2 \koz .\]
Hence the problem
\begin{eqnarray}\label{e9}
\max 23x_1 + 19x_2 + 28x_3 + 14x_4 + 44x_5\nonumber\\ {\bf x}\in{\cal R}_1
\end{eqnarray}
is a relaxation of the problem\index{relaxation}
\begin{eqnarray}\label{e10}
\max 23x_1 + 19x_2 + 28x_3 + 14x_4 + 44x_5\nonumber\\ {\bf x}\in{\cal F}_1\koz.
\end{eqnarray}
Problem (\ref{e9}) can be solved by Theorem \ref{t1}, too, but it must be taken into
consideration that the value of $x_3$ is 0. Thus its optimal solution is
\[x^{*}_1=x^{*}_2=1,\, x^{*}_3=0,\, x^{*}_4=1,\,x^{*}_5=\frac{4}{19}.\]
The optimal value is 65.26 which gives the upper bound 65 for the optimal value of
Problem (\ref{e10}). The other subsets of the feasible solutions are immediately
investigated. The optimal solution of the problem
\begin{eqnarray}\label{e11}
\max 23x_1 + 19x_2 + 28x_3 + 14x_4 + 44x_5\nonumber\\ {\bf x}\in{\cal R}_2
\end{eqnarray}
is
\[x^{*}_1=1,\,x^{*}_2=\frac{6}{7},\, x^{*}_3=1,\, x^{*}_4=x^{*}_5=0\]
giving the value 67.28. Hence 67 is an upper bound of the problem
\begin{eqnarray}\label{e12}
\max 23x_1 + 19x_2 + 28x_3 + 14x_4 + 44x_5\nonumber\\ {\bf x}\in{\cal F}_2\; \koz.
\end{eqnarray}
As the upper bound of (\ref{e12}) is higher than the upper bound of (\ref{e10}), i.e.
this branch is more promising, first it is fathomed further on. It is cut again into two
branches according to the two values of $x_2$ as it is the non-integer variable in the
optimal solution of (\ref{e11}). Let 
\begin{eqnarray*}
{\cal F}_3={\cal F}_2\cap\{{\bf x}\mid x_2=0\}\;,\\
{\cal F}_4={\cal F}_2\cap\{{\bf x}\mid x_2=1\}\;,\\
{\cal R}_3={\cal R}_2\cap\{{\bf x}\mid x_2=0\}\;,\\
{\cal R}_4={\cal R}_2\cap\{{\bf x}\mid x_2=1\}\;.
\end{eqnarray*}
The sets ${\cal F}_3$ and ${\cal R}_3$ are containing the feasible solution of the original
problems such that $x_3$ is fixed to 1 and $x_2$ is fixed to 0. In the sets ${\cal F}_4$ 
and ${\cal R}_4$ both variables are fixed to 1.
The optimal solution of the first relaxed problem, i.e.
\begin{eqnarray*}%\label{e13}
\max 23x_1 + 19x_2 + 28x_3 + 14x_4 + 44x_5\nonumber\\ {\bf x}\in{\cal R}_3
\end{eqnarray*}
is
\[x^{*}_1=1,\,x^{*}_2=0,\, x^{*}_3=1,\, x^{*}_4=1,\,x^{*}_5=0\koz.\]
As it is integer it is also the optimal solution of the problem
\begin{eqnarray*}%\label{e14}
\max 23x_1 + 19x_2 + 28x_3 + 14x_4 + 44x_5\nonumber\\ {\bf x}\in{\cal F}_3 \koz.
\end{eqnarray*}
The optimal objective function value is 65. The branch of the sets ${\cal F}_3$ and 
${\cal R}_3$ is completely fathomed, i.e. it is not possible to find a better solution in 
it.

The other new branch is when both $x_2$ and $x_3$ are fixed to 1. If the objective function
is optimized on ${\cal R}_4$ then the optimal solution is
\[x^{*}_1=\frac{7}{8},\,x^{*}_2=x^{*}_3=1,\, x^{*}_4=x^{*}_5=0\koz.\]
Applying the same technique again two branches are defined by the sets
\[{\cal F}_5={\cal F}_4\cap\{{\bf x}\mid x_1=0\},\;
{\cal F}_6={\cal F}_4\cap\{{\bf x}\mid x_1=1\},\]
\[{\cal R}_5={\cal R}_4\cap\{{\bf x}\mid x_2=0\},\;
{\cal R}_6={\cal R}_4\cap\{{\bf x}\mid x_2=1\}\koz.\]
The optimal solution of the branch of ${\cal R}_5$ is
\[x^{*}_1=0,\,x^{*}_2=x^{*}_3=x^{*}_4=1,\,x^{*}_5=\frac{1}{19}\koz.\]
The optimal value is 63.32. It is strictly less than the objective function
value of the feasible solution found in the branch of ${\cal R}_3$. Therefore it cannot
contain an optimal solution. Thus its further exploration can be omitted although the best
feasible solution of the branch is still not known. The branch of ${\cal R}_6$ is
infeasible as objects 1, 2, and 3 are overusing the knapsack. Traditionally this fact is
denoted by using $-\infty$ as optimal objective function value.

At this moment there is only one branch which is still unfathomed. It is the branch of
${\cal R}_1$. The upper bound here is 65 which is equal to the objective function value of
the found feasible solution. One can immediately conclude that this feasible solution is 
optimal. If there is no need for alternative optimal solutions then the exploration of
this last branch can be abandoned and the method is finished. If alternative optimal
solutions are required then the exploration must be continued. The non-integer variable
in the optimal solution of the branch is $x_5$. The subbranches referred later as the 7th and 8th branches,
defined by the equations
$x_5=0$ and $x_5=1$, give the upper bounds 56 and 61, respectively. Thus they do not
contain any optimal solution and the method is finished.

\subsection{Properties in the calculation of the numerical example}\label{ss3}
The calculation is revisited to emphasize the general underlying logic of the method.
The same properties are used in the next section when the general frame of B\&B is
discussed.

Problem (\ref{e7}) is a difficult one. Therefore the very similar but much easier
Problem (\ref{e8}) has been solved instead of (\ref{e7}). A priori it was not possible to
exclude the case that the optimal solution of (\ref{e8}) is the optimal solution of
(\ref{e7}) as well. Finally it turned out that the optimal solution of (\ref{e8})
does not satisfy all constraints of (\ref{e7}) thus it is not optimal there. But the
calculation was not useless, because an upper bound of the optimal value of (\ref{e7})
has been obtained. These properties are reflected in the definition of {\em relaxation}
in the next section.\index{relaxation}

As the relaxation did not solved Problem (\ref{e7}) therefore it was divided into 
Subproblems (\ref{e10}) and  (\ref{e12}). Both subproblems have their own optimal 
solution and the better one is the
optimal solution of (\ref{e7}). They are still too difficult to be solved directly, 
therefore relaxations were generated to both of them. These problems are (\ref{e9})
and (\ref{e11}). The nature of (\ref{e9}) and (\ref{e11}) from mathematical point of
view is the same as of (\ref{e8}).

Notice that the union of the sets of the feasible solutions of (\ref{e9}) and (\ref{e11})
is a proper subset of the relaxation (\ref{e8}), i.e.
\[{\cal R}_1\cup{\cal R}_2\subset{\cal R}_0\koz.\]
Moreover the two subsets have no common element, i.e.
\[{\cal R}_1\cap{\cal R}_2=\emptyset\koz.\]
It is true for all other cases, as well.
The reason is that the branching, i.e. the determination of the Subproblems (\ref{e10}) 
and (\ref{e12}) was made in a way that the optimal solution of the relaxation, 
i.e. the optimal solution of (\ref{e8}), was cut off.

The branching policy also has consequences on the upper bounds. Let $\nu({\cal S})$ be the
optimal value of the problem where the objective function is unchanged and the set of 
feasible solutions is ${\cal S}$. Using this notation the optimal objective function
values of the original and the relaxed problems are in the relation
\[\nu({\cal F})\leq\nu({\cal R})\koz.\]
If a subset ${\cal R}_k$ is divided into ${\cal R}_p$ and ${\cal R}_q$ then
\begin{eqnarray}\label{e15}
\nu({\cal R}_k)\geq\max\{\nu({\cal R}_p),\nu({\cal R}_q)\}\koz.
\end{eqnarray}
Notice that in the current Problem (\ref{e15}) is always satisfied with strict inequality
\begin{eqnarray*}\nu({\cal R}_0)>\max\{\nu({\cal R}_1),\nu({\cal R}_2)\}\koz,\\
\nu({\cal R}_1)>\max\{\nu({\cal R}_7),\nu({\cal R}_8)\}\koz,\\
\nu({\cal R}_2)>\max\{\nu({\cal R}_3),\nu({\cal R}_4)\}\koz,\\
\nu({\cal R}_4)>\max\{\nu({\cal R}_5),\nu({\cal R}_6)\}\koz.
\end{eqnarray*}
(The values $\nu({\cal R}_7)$ and $\nu({\cal R}_8)$ were mentioned only.)
If the upper bounds of a certain quantity are compared then one can conclude that
the smaller the better as it is closer to the value to be estimated. An equation similar to
(\ref{e15}) is true for the non-relaxed problems, i.e. if ${\cal F}_k={\cal F}_p\cup
{\cal F}_q$ then
\begin{eqnarray}\label{e16}
\nu({\cal F}_k)=\max\{\nu({\cal F}_p),\nu({\cal F}_q)\}\koz,
\end{eqnarray}
but because of the difficulty of the solution of the problems,
practically it is not possible to use (\ref{e16}) for getting further information.

A subproblem is fathomed and no further investigation of it is needed if either
\begin{itemize}
\item its integer (non-relaxed) optimal solution is obtained, like in the case of
${\cal F}_3$, or
\item it is proven to be infeasible as in the case of ${\cal F}_6$, or
\item its upper bound is not greater than the value of the best known feasible
solution (cases of ${\cal F}_1$ and ${\cal F}_5$).
\end{itemize}
If the first or third of these conditions are satisfied then all feasible solutions
of the subproblem are enumerated in an implicit way.

The subproblems which are generated in the same iteration, are
represented by two branches on the enumeration tree. They are siblings and have
the same parent. Figure 24.1 visualize the course of the calculations using the 
parent--child relation.

The enumeration tree is modified by constructive steps when new branches are formed and
also by reduction steps when some branches can be deleted as one of the three 
above-mentioned criteria are satisfied. The method stops when no subset remained 
which has to be still fathomed. 

\subsection{How to accelerate the method}\label{ss5}
As it was mentioned in the introduction of the chapter, B\&B and implicit enumeration can 
co-operate easily. Implicit enumeration uses
so-called tests and obtains consequences on the values of the variables. 
For example if $x_3$ is fixed to 1 then the knapsack inequality immediately 
implies that $x_5$ must be 0, otherwise the capacity of the tourist is
overused. It is true for the whole branch 2.

On the other hand if the objective function value must be at least 65, which is the
value of the found feasible solution then it possible to conclude in
branch 1 that the fifth object must be in the knapsack, i.e. $x_5$ must be 1,
 as the total value of the remaining 
objects 1, 2, and 4 is only 56.

Why such consequences accelerate the algorithm? In the example there are
5 binary variables, thus the number of possible cases is $32=2^5$. 
Both branches 1 and 2 have 16 cases. If it is possible to determine the
value of a variable, then the number of cases is halved. In the above 
example it means that only 8 cases remain to be investigated in both 
branches. This example is a small one. But in the case of larger problems the
acceleration process is much more significant. E.g. if in a branch there are 21 free,
i.e. non-fixed, variables but it is possible to determine the value of one of them then
the investigation of 1\,048\,576 cases is saved. The application of the tests needs some
extra calculation, of course. Thus a good trade-off must be found.

The use of information provided by other tools is further discussed in Section \ref{s1}.

\begin{gyak}
\ujgyak\label{ex241-1} What is the suggestion of the optimal solution of 
a Knapsack Problem\gyakindex{Knapsack Problem} in connection of an
object having (a) negative weight and positive value, (b) positive weight and negative
value?
\ujgyak\label{ex241-2} Show that an object of a knapsack problem having negative weight and negative value
can be substituted by an object having positive weight and positive value such that the
two knapsack problems are equivalent. ({\em Hint.} Use complementary variable.)
\ujgyak Solve Problem (\ref{e7}) with a branching strategy such that an integer valued 
variable is used for branching provided that such a variable exists.
\end{gyak}

\section{The general frame of the B\&B method}
The aim of this section is to give a general description of the B\&B method.
Particular realizations of the general frame are discussed in later sections.

B\&B is based on the notion of \ki{relaxation.}\inddef{relaxation} It has not been defined yet. As there
are several types of relaxations the first subsection is devoted to this notion.
The general frame is discussed in the second subsection. 

\subsection{Relaxation}\index{relaxation}
Relaxation is discussed in two steps. There are several techniques to define relaxation
to a particular problem. There is no rule for choosing among them. It depends on the
design of the algorithm which type serves the algorithm well. The different types are discussed
in the first part titled ``Relaxations of a particular problem''.
In the course of the solution of Problem
(\ref{e7}) subproblems were generated which were still knapsack problems. They had their
own relaxations which were not totally independent from the relaxations of each other and
the main problem. The expected common properties and structure is analyzed in the second 
step under the title ``Relaxation of a problem class''.

\subsubsection{Relaxations of a particular problem}\index{relaxation}
The description of Problem (\ref{e7}) consists of three parts: (1) the objective function, 
(2) the algebraic constraints, and (3) the requirement that the variables must be binary. 
This structure is typical for optimization problems. In a general formulation an 
optimization problem can be given as
\begin{eqnarray}\label{e17}
\max f({\bf x})
\end{eqnarray}
\begin{eqnarray}\label{e18}
{\bf g}({\bf x})\leq{\bf b}
\end{eqnarray}
\begin{eqnarray}\label{e19}
\;\;{\bf x}\in{\cal X}\koz.
\end{eqnarray}

\subsubsection{Relaxing the non-algebraic constraints}\index{relaxation}
The underlying logic of generating relaxation (\ref{e8}) is that constraint (\ref{e19})
has been substituted by a looser one. In the particular case it was allowed that the
variables can take any value between 0 and 1. In general (\ref{e19}) is replaced by a
requirement that the variables must belong to a set, say ${\cal Y}$, which is larger
than ${\cal X}$, i.e. the relation ${\cal X} \subseteq {\cal Y}$ must hold. More formally
the relaxation of Problem (\ref{e17})-(\ref{e19}) is the problem
$$\max f({\bf x})\eqno(\ref{e17})$$
$${\bf g}({\bf x})\leq{\bf b}\eqno(\ref{e18})$$
\begin{eqnarray}\label{e20}
\;\;\hbox{  }{\bf x}\in{\cal Y}.
\end{eqnarray}
This type of relaxation can be applied if a large amount of difficulty can be eliminated
by changing the nature of the variables.

\subsubsection{Relaxing the algebraic constraints}\index{relaxation}
There is a similar technique such that (\ref{e19}) the inequalities (\ref{e18}) 
are relaxed instead of the constraints. A natural way of this type of relaxation is the 
following. Assume that there are $m$ inequalities in (\ref{e18}).
Let $\lambda_i\geq 0$ $(i=1,\ldots,m)$ be fixed numbers.
Then any ${\bf x}\in{\cal X}$ satisfying (\ref{e18}) also satisfies the
inequality
\begin{eqnarray}\label{e22}
\sum_{i=1}^m \lambda_i g_i({\bf x})\leq \sum_{i=1}^m\lambda_i b_i\koz.
\end{eqnarray}
Then the relaxation is the optimization of the (\ref{e17}) objective function
under the conditions (\ref{e22}) and (\ref{e19}). The name of the inequality
(\ref{e22}) is \ki{surrogate constraint.}\inddef{surrogate constraint} 

The problem
\begin{eqnarray}\label{e23}
\begin{array}{crrrrrrrrrcl}
\max & 23x_1 & + & 19x_2 & + & 28x_3 & + & 14x_4 & + & 44x_5\\
& 5x_1 & + & 4x_2 & + & 6x_3 & + & 3x_4 & + & 5x_5 & \leq & 14\\
& 2x_1 & - & 2x_2 & - & 3x_3 & + & 5x_4 & + & 6x_5 & \leq & 4\\
& 1x_1 & + & 5x_2 & + & 8x_3 & - & 2x_4 & + & 8x_5 & \leq & 7\\
\multicolumn{12}{c}{x_1,x_2,x_3,x_4,x_5= 0\;\hbox{or}\,1}
\end{array}
\end{eqnarray}
is a general zero-one optimization problem. If $\lambda_1=\lambda_2=\lambda_3=1$ then 
the relaxation obtained in this way is Problem (\ref{e7}). Both
problems belong to NP-complete classes. However the knapsack problem is
significantly easier from practical point of view than the general problem,
thus the relaxation may have sense. Notice that in this particular problem the optimal 
solution of the knapsack problem, i.e. (1,0,1,1,0), satisfies the constraints of
(\ref{e23}), thus it is also the optimal solution of the latter problem.

Surrogate constraint is not the only option in relaxing the algebraic constraints.
A region defined by nonlinear boundary surfaces can be approximated by tangent
planes. For example if the feasible region is the unit circuit which is described
by the inequality
\begin{eqnarray*}
x_1^2+x_2^2\leq 1
\end{eqnarray*}
can be approximated by the square
\begin{eqnarray*}
-1\leq x_1,\,x_2\leq  1\koz.
\end{eqnarray*}
If the optimal solution on the enlarged region is e.g. the point (1,1) which is not
in the original feasible region then a {\em cut} must be found which cuts it from
the relaxed region but it does not cut any part of the original feasible region.
It is done e.g. by the inequality
\begin{eqnarray*}
x_1+x_2\leq\sqrt{2}\koz.
\end{eqnarray*}
 A new relaxed problem is defined by the introduction of the cut. The method is similar
 to one of the method relaxing of the objective function discussed below.

\subsubsection{Relaxing the objective function}\index{relaxation}
In other cases the difficulty of the problem is caused by the objective function. If
it is possible to use an easier objective function, say $h({\bf x})$,
but to obtain an upper bound the condition
\begin{eqnarray}\label{e21}
\forall\,{\bf x}\in{\cal X}:\;h({\bf x})\geq f({\bf x})
\end{eqnarray}
must hold. Then the relaxation is
\begin{eqnarray}\label{e24}
\max h({\bf x})
\end{eqnarray}
$${\bf g}({\bf x})\leq{\bf b}\eqno(\ref{e18})$$
$${\bf x}\in{\cal X}\koz.\eqno(\ref{e19})$$

This type of relaxation is typical if B\&B is applied in (continuous)
nonlinear optimization. An important subclass of the nonlinear optimization problems 
is the so-called convex programming problem. It is again a relatively
easy subclass. Therefore it is reasonable to generate a relaxation of this type
if it is possible. A Problem (\ref{e17})-(\ref{e19}) is a convex programming
problem, if ${\cal X}$ is a convex set, the functions $g_i({\bf x})$ 
$(i=1,\ldots,m)$ are convex
and the objective function $f({\bf x})$ is concave. Thus the relaxation can be a
convex programming problem if only the last condition is violated. Then it is
enough to find a concave function $ h({\bf x})$ such that (\ref{e21}) is satisfied.

For example the single variable function $f(x)=2x^2-x^4$ is not concave in the
interval $[\frac{-\sqrt{3}}{3},\frac{\sqrt{3}}{3}]$.\footnote{A continuous function 
is concave if its second derivative is negative. $f^{''}(x)=4-12x^2$
which is positive in the open interval $\left (\frac{-\sqrt{3}}{3},\frac{\sqrt{3}}{3}\right)$.}
Thus if it is the objective function in an optimization problem it might be
necessary that it is substituted by a concave function $h(x)$ such that 
$\forall x\in[\frac{-\sqrt{3}}{3},\frac{\sqrt{3}}{3}]:\,f(x)\leq h(x)$. It is easy 
to see that $h(x)=\frac{8}{9}-x^2$ satisfies the requirements.

Let ${\bf x}^{*}$ be the optimal solution of the relaxed problem (\ref{e24}), 
(\ref{e18}), and (\ref{e19}). It solves the original problem if the optimal
solution has the same objective function value in the original and 
relaxed problems, i.e. $f({\bf x}^{*})=h({\bf x}^{*})$.

Another reason why this type of relaxation is applied that in certain cases the
objective function is not known in a closed form, however it can be determined
in any given point. It might happen even in the case if the objective function
is concave. Assume that the value of $f({\bf x})$ is known in the points 
${\bf y}_1,\ldots,{\bf y}_k$. If $f({\bf x})$ concave then it is smooth, i.e. its
gradient exists. The gradient determines a tangent plane which is above the function.
The equation of the tangent plane in point ${\bf y_p}$ is\footnote{The gradient 
is considered being a row vector.} 
\begin{eqnarray*}
\nabla(f({\bf y_p}))({\bf x}-{\bf y_p})=0.
\end{eqnarray*}
Hence in all points of the domain of the function $f({\bf x})$
we have that
\begin{eqnarray*}%\label{e25}
h({\bf x})=\min\left\{f({\bf y_p})+\nabla(f({\bf y_p}))({\bf x}-
{\bf y_p})\mid p=1,\ldots,k\right\}\geq f({\bf x}).
\end{eqnarray*}
Obviously the function $h({\bf x})$ is an approximation of function $f({\bf x})$.

The idea if the method is illustrated on the following numerical example.
Assume that an ``unknown'' concave function is to be maximized on the [0,5] closed
interval. The method can start from any point of the interval which is in the feasible 
region. Let 0 be the starting point. According to the assumptions although the closed
formula of the function is not known, it is possible to determine the values of function
and its derivative. Now the values $f(0)=-4$ and $f^{'}(0)=4$ are obtained. The
general formula of the tangent line in the point $(x_0,f(x_0))$ is 
\[y=f^{'}(x_0)(x-x_0)+f(x_0).\] 
Hence the equation of the first tangent line is $y=4x-4$ giving the first optimization
problem as
\begin{eqnarray*}
\begin{array}{c}
\max\,h\\ h\leq 4x-4\\ x\in[0,5].
\end{array}
\end{eqnarray*}
As $4x-4$ is a monotone increasing function, the optimal solution is $x=5$. Then the 
values $f(5)=-9$ and $f^{'}(5)=-6$ are provided by the method calculating the function.
The equation of the second tangent line is $y=-6x+21$. Thus the second optimization 
problem is
\begin{eqnarray*}
\begin{array}{c}
\max\,h\\ h\leq 4x-4,\;\;\;\;h\leq-6x+21\\ x\in[0,5].
\end{array}
\end{eqnarray*}
As the second tangent line is a monotone decreasing function, the optimal solution is in
the intersection point of the two tangent lines giving $x=2.5$. Then the values
$f(2.5)=-0.25$ and $f^{'}(2.5)=-1$ are calculated and the equation of the tangent line is
$y=-x+2.25$. The next optimization problem is
\begin{eqnarray*}
\begin{array}{c}
\max\,h\\ h\leq 4x-4,\;\;\;\;h\leq-6x+21,\;\;\;\;h\leq -x+2.25\\ x\in[0,5].
\end{array}
\end{eqnarray*}
The optimal solution is $x=1.25$. It is the intersection point of the first and third
tangent lines. Now both new intersection points are in the interval [0,5]. In general
some intersection points can be infeasible. The method goes in the same way further on.
The approximated ``unknow'' function is $f(x)=-(x-2)^2$.

\subsubsection{The Lagrange Relaxation}\index{relaxation}\index{Lagrange relaxation}
Another relaxation called \ki{Lagrange relaxation.}\inddef{Lagrange relaxation} 
In that method both the objective
function and the constraints are modified. The underlying idea is the following.
The variables must satisfy two different types of constraints, i.e. they must satisfy
both (\ref{e18}) and (\ref{e19}). The reason that the constraints are written in two
parts is that the nature of the two sets of constraints is different. The  difficulty
of the problem caused by the requirement of {\em both} constraints. It is significantly
easier to satisfy only one type of constraints. {\em So what about to eliminate one of
them?}

Assume again that the number of inequalities in (\ref{e18}) is $m$. Let $\lambda_i\geq0$
$(i=1,\ldots,m)$ be fixed numbers. The Lagrange relaxation of the problem  
(\ref{e17})- (\ref{e19}) is 
\begin{eqnarray}\label{e26}
\max\,f({\bf x})+\sum_{i=1}^m\lambda_i(b_i-g_i({\bf x}))
\end{eqnarray}
$${\bf x}\in{\cal X}\koz.\eqno(\ref{e19})$$
Notice that the objective function (\ref{e26}) penalizes the violation of the constraints,
e.g. trying to use too much resources, and rewards the saving of resources. The first set
of constraints disappeared from the problem. In most of the cases the Lagrange relaxation
is a much easier one than the original problem. In what follows Problem
(\ref{e17})- (\ref{e19}) is also denoted by $(P)$ and the Lagrange relaxation is referred as
$(L(\lambda))$. The notation reflects the fact that the Lagrange relaxation problem
depends on the choice of $\lambda_i$'s. The numbers $\lambda_i$'s are called
Lagrange multipliers.

It is not obvious that $(L(\lambda))$ is really a relaxation of $(P)$. This relation is 
established by

\begin{tetel}\label{t2}
Assume that both $(P)$ and $(L(\lambda))$ have optimal solutions. Then for any nonnegative 
$\lambda_i$ $(i=1,\ldots,m)$ the inequality
\begin{eqnarray*}%\label{e27}
\nu(L(\lambda))\geq\nu(P)
\end{eqnarray*}
holds.
\end{tetel}
\begin{biz}
The statement is that the optimal value of $(L(\lambda))$ is an upper bound
of the optimal value of $(P)$. Let ${\bf x}^{*}$ be the optimal solution of $(P)$. It
is obviously feasible in both problems. Hence for all $i$ the inequalities
$\lambda_i\geq0$, $b_i\geq g_i({\bf x}^{*})$ hold. Thus $\lambda_i(b_i-g_i({\bf x}^{*}))\geq0$ 
which implies that
\[f({\bf x}^{*})\leq f({\bf x}^{*})+\sum_{i=1}^m\lambda_i(b_i-g_i({\bf x}^{*})).\]
Here the right-hand side is the objective function value of a feasible solution of
$(L(\lambda))$, i.e.
\[\nu(P)=f({\bf x}^{*})\leq 
f({\bf x}^{*})+\sum_{i=1}^m\lambda_i(b_i-g_i({\bf x}^{*}))\leq\nu(L(\lambda))\koz.\]
\hfill
\end{biz}

There is another connection between $(P)$ and $(L(\lambda))$ which is also
important from the point of view of the notion of relaxation.

\begin{tetel}\label{t3}
Let ${\bf x}_L$ be the optimal solution of the Lagrange relaxation. If
\begin{eqnarray}\label{e28}
{\bf g}({\bf x}_L)\leq{\bf b}
\end{eqnarray}
and
\begin{eqnarray}\label{e29}
\sum_{i=1}^m\lambda_i(b_i-g_i({\bf x}_L))=0
\end{eqnarray}
then ${\bf x}_L$ is an optimal solution of $(P)$.
\end{tetel}
\begin{biz}
(\ref{e28}) means that ${\bf x}_L$ is a feasible solution of $(P)$.
For any feasible solution ${\bf x}$ of $(P)$ it follows from the optimality of ${\bf x}_L$
that
\[f({\bf x})\leq f({\bf x})+\sum_{i=1}^m\lambda_i(b_i-g_i({\bf x}))\leq
f({\bf x}_L)+\sum_{i=1}^m\lambda_i(b_i-g_i({\bf x}_L))=f({\bf x}_L)\koz,\]
i.e. ${\bf x}_L$ is at least as good as ${\bf x}$.\hfill 
\end{biz}

The importance of the conditions (\ref{e28}) and (\ref{e29}) is that they give an optimality
criterion, i.e. if a point generated by the Lagrange multipliers satisfies them then it is
optimal in the original problem. The meaning of (\ref{e28}) is that the optimal solution
of the Lagrange problem is feasible in the original one and the meaning of (\ref{e29})
is that the objective function values of ${\bf x}_L$ are equal in the two problems, just as
in the case of the previous relaxation.
It also indicates that the optimal solutions of the
two problems are coincident in certain cases.

There is a practical necessary condition for being a useful relaxation which is that the
relaxed problem is easier to solve than the original problem. The Lagrange relaxation
has this property. It can be shown on Problem (\ref{e23}). Let $\lambda_1=1$,
$\lambda_2=\lambda_3=3$. Then the objective function (\ref{e26}) is the following
\begin{eqnarray*}
(23x_1+19x_2+28x_3+14x_4+44x_5)+(14-5x_1-x_2-6x_3-3x_4-5x_5)\\
+3(4-2x_1-x_2+3x_3-5x_4-6x_5)+3(7-x_1-5x_2-8x_3+2x_4-8x_5)\\
=47+(23-5-6-3)x_1+(19-1-3-15)x_2+(28-6+9-24)x_3\\+(14-3-15+5)x_4+(44-5-18-24)x_5\\
=47+9x_1+0x_2+7x_3+x_4-3x_5\koz.
\end{eqnarray*}
The only constraint is that all variables are binary. It implies that if a coefficient
is positive in the objective function then the variable must be 1 in the optimal
solution of the Lagrange problem, and if the coefficient is negative then the variable
must be 0. As the coefficient of $x_2$ is zero, there are two optimal solutions:
(1,0,1,1,0) and (1,1,1,1,0). The first one satisfies the optimality condition thus it is
an optimal solution. The second one is infeasible.

\subsubsection{What is common in all relaxation?} 
They have three common properties.
\begin{enumerate}
\item All feasible solutions are also feasible in the relaxed problem.
\item The optimal value of the relaxed problem is an upper bound of the optimal value
of the original problem.
\item There are cases when the optimal solution of the relaxed problem is also optimal
in the original one.
\end{enumerate}
The last property cannot be claimed for all particular case as then the relaxed problem
is only an equivalent form of the original one and needs very likely approximately
the same computational effort, i.e. it does not help too much. Hence the first two
properties are claimed in the definition of the relaxation of a particular problem.

\begin{defi}\label{d1}
Let $f,h$ be two functions mapping from the $n$-dimensional Euclidean space into the real
numbers. Further on let ${\cal U,V}$ be two subsets of the $n$-dimensional Euclidean 
space. The problem 
\begin{eqnarray}\label{e30}
\max\{h({\bf x})\mid {\bf x}\in{\cal V}\}
\end{eqnarray}
is a relaxation of the problem
\begin{eqnarray}\label{e31}
\max\{f({\bf x})\mid {\bf x}\in{\cal U}\}
\end{eqnarray}
if\\ (i) ${\cal U\subset V}$ and\\ (ii) it is known {\em a priori}, i.e. without
solving the problems that $\nu(\ref{e30})\geq\nu(\ref{e31})$.
\end{defi}

\subsubsection{Relaxation of a problem class}
No exact definition of the notion of {\em problem class} will be given. There are many
problem classes in optimization. A few examples are the knapsack problem, the more
general zero-one optimization,
the traveling salesperson problem, linear programming, convex programming, etc. In what
follows problem class means only an infinite set of problems.

One key step in the solution of (\ref{e7}) was that the problem was divided into
subproblems and even the subproblems were divided into further subproblems, and so on.

The division must be carried out in a way such that the subproblems belong to the same
problem class. By fixing the value of a variable the knapsack problem just becomes
another knapsack problem of lesser dimension. The same is true for almost all 
optimization problems, i.e. a restriction on the value of a single variable (introducing
either a lower bound, or upper bound, or an exact value) creates a new problem in the 
same class. But restricting a single variable is not the only possible way to divide
a problem into subproblems. Sometimes special constraints on a set of variables may have 
sense. For example it is easy to see from the first constraint of (\ref{e23}) that at
most two out of the variables $x_1$, $x_3$, and $x_5$ can be 1. Thus it is possible to 
divide it into two subproblems by introducing the new constraint which is either 
$x_1+x_3+x_5=2$, or $x_1+x_3+x_5\leq 1$. The resulted problems are still in the class of
binary optimization. The same does not work in the case of the knapsack problem as
it must have only one constraint, i.e. if a second inequality is added to the problem
then the new problem is out of the class of the knapsack problems.

The division of the problem into subproblems means that the set of feasible solutions
is divided into subsets not excluding the case that one or more of the subsets turn
out to be empty set. ${\cal R}_5$ and ${\cal R}_6$ gave such an example.

Another important feature is summarized in formula (\ref{e15}). It says that the upper
bound of the optimal value obtained from the undivided problem is at most as accurate
as the upper bound obtained from the divided problems.

Finally, the further investigation of the subset ${\cal F}_1$ could be abandoned as 
${\cal R}_1$ was not giving a higher upper bound as the objective function value of 
the optimal solution on ${\cal R}_3$ which lies at the same time in ${\cal F}_3$, too,
i.e. the subproblem defined on the set ${\cal F}_3$ was solved.

The definition of the relaxation of a problem class reflects the fact that relaxation
and defining subproblems (branching) are not completely independent. In the definition
it is assumed that the branching method is a priori given. 

\begin{defi}\label{d2}
Let ${\cal P}$ and ${\cal Q}$ be two problem classes. Class ${\cal Q}$ is a relaxation of
class ${\cal P}$ if there is a map $R$ with the following properties.
\begin{enumerate}
\item $R$ maps the problems of ${\cal P}$ into the problems of ${\cal Q}$.
\item If a problem (P) $\in{\cal P}$ is mapped into (Q) $\in{\cal Q}$ 
then (Q) is a relaxation of (P) in the sense of 
Definition \ref{d1}.
\item If (P) is divided into (P$_1$),$\ldots$,(P$_k$) and these problems are mapped into
(Q$_1$),$\ldots$,(Q$_k$), then the inequality
\begin{eqnarray}\label{e40}
\nu(\hbox{Q})\geq\max\{\nu(\hbox{Q}_1),\ldots,\nu(\hbox{Q}_k)\}
\end{eqnarray}
holds.
\item There are infinite many pairs (P), (Q) such that an optimal solution of (Q) is also
optimal in (P).
\end{enumerate}
\end{defi}


\subsection{The general frame of the B\&B method}
As the Reader has already certainly observed B\&B divides the problem into subproblems
and tries to fathom each subproblem by the help of a relaxation. A subproblem is fathomed
in one of the following cases:
\begin{enumerate}
\item The optimal solution of the relaxed subproblem satisfies the constraints of the
unrelaxed subproblem and its relaxed and non-relaxed objective function values are equal.
\item The infeasibility of the relaxed subproblem implies that the unrelaxed 
subproblem is infeasible as well.
\item The upper bound provided by the relaxed subproblem is less (in the case if alternative
optimal solution are sought) or less or equal (if no alternative optimal solution is
requested) than the objective function value of the best known feasible solution.
\end{enumerate} 
The algorithm can stop if all subsets (branches) are fathomed. If nonlinear programming
problems are solved by B\&B then the finiteness of the algorithm cannot be always 
guaranteed.

In a typical iteration the algorithm executes the following steps.
\begin{itemize}
\item It selects a leaf of the branching tree, i.e. a subproblem
not divided yet into further subproblems.
\item The subproblem is divided into further subproblems (branches) and their relaxations 
are defined.
\item Each new relaxed subproblem is solved and checked if it belongs to one of the 
above-mentioned cases. If so then it is fathomed and no further investigation is needed.
If not then it must be stored for further branching.
\item If a new feasible solution is found which is better than the so far best one, then
even stored branches having an upper bound less than the value of the new best feasible
solution 
can be deleted without further investigation.
\end{itemize}

In what follows it is supposed that the relaxation satisfies definition \ref{d2}.

The original problem to be solved is
$$\max\,f(\bf x)\eqno(\ref{e17})$$
$${\bf g}({\bf x})\leq{\bf b}\eqno(\ref{e18})$$
$${\bf x}\in{\cal X}.\eqno(\ref{e19})$$
Thus the set of the feasible solutions is
\begin{eqnarray}\label{e35}
{\cal F}={\cal F}_0=\{{\bf x}\mid {\bf g}({\bf x})\leq{\bf b}; {\bf x}\in{\cal X}\}\koz.
\end{eqnarray}
The relaxed problem satisfying the requirements of definition \ref{d2} is
\begin{eqnarray*}%\label{e36}
\max\,h(\bf x)
\end{eqnarray*}
\vspace{-3mm}
\begin{eqnarray*}%\label{e37}
{\bf k}({\bf x})\leq{\bf b}
\end{eqnarray*}
\vspace{-3mm}
\begin{eqnarray*}%\label{e38}
{\bf x}\in{\cal Y},
\end{eqnarray*}
where ${\cal X\subseteq Y}$ and for all points of the domain of the objective functions
$f({\bf x})\leq h({\bf x})$ and for all points of the domain of the constraint functions
${\bf k}({\bf x})\leq h({\bf x})$.
Thus the set of the feasible solutions of the relaxation is
\begin{eqnarray*}%\label{e39}
{\cal R}={\cal R}_0=\{{\bf x}\mid {\bf k}({\bf x})\leq{\bf b}; {\bf x}\in{\cal Y}\}\koz.
\end{eqnarray*}
Let ${\cal F}_k$ be a previously defined subset. Suppose that it is divided into the
subsets ${\cal F}_{t+1}$,\ldots,${\cal F}_{t+p}$, i.e.
\vspace{-1mm}
\begin{eqnarray*}
{\cal F}_k=\bigcup_{l=1}^p{\cal F}_{t+l} \koz .
\end{eqnarray*}
Let ${\cal R}_k$ and ${\cal R}_{t+1}$,\ldots,${\cal R}_{t+p}$ be the feasible sets of the 
relaxed subproblems. To satisfy the requirement (\ref{e40}) of definition \ref{d2} it is
assumed that
\begin{eqnarray*}%\label{e41}
{\cal R}_k\supseteq\bigcup_{l=1}^p{\cal R}_{t+l} \koz .
\end{eqnarray*}

The subproblems are identified by their sets of feasible solutions. The unfathomed 
subproblems are stored in a list. The algorithm selects a subproblem from the list for
further branching. In the formal description of the general frame of B\&B the following
notations are used.
\begin{eqnarray*}
\begin{array}{ll}
\hat{z} & \hbox{the objective function value of the best feasible solution found so far}\\
{\cal L} & \hbox{the list of the unfathomed subsets of feasible solutions}\\
t & \hbox{the number of branches generated so far}\\
{\cal F}_0 & \hbox{the set of all feasible solutions}\\
r & \hbox{the index of the subset selected for branching}\\
p(r) & \hbox{the number of branches generated from}\; {\cal F}_r\\
{\bf x}_i & \hbox{the optimal solution of the relaxed subproblem defined on}\; {\cal R}_i\\
z_i & \hbox{the upper bound of the objective function on subset}\; {\cal F}_i\\
{\cal L}+{\cal F}_i & \hbox{the operation of adding the subset}\; {\cal F}_i \hbox{ to the list } 
{\cal L}\\
{\cal L}-{\cal F}_i & \hbox{the operation of deleting the subset}\; {\cal F}_i \hbox{ from the 
list}\; {\cal L}\\
\end{array}
\end{eqnarray*}
Note that $y_i=\max\{h({\bf x})\mid {\bf x}\in{\cal R}_i\}$.
 
The frame of the algorithms can be found below. It simply describes the basic
ideas of the method and does not contain any tool of acceleration.
 
\begin{algN}{Branch-and-Bound}\inddef{\textsc{Branch-and-Bound}}
 1 \' $\hat{z}\,\leftarrow\,-\infty$\\
 2 \' ${\cal L}\,\leftarrow\,\{\,{\cal F}_0\,\}$\\
 3 \' $t\,\leftarrow\,0$\\
 4 \' \key{while} \= ${\cal L}\neq\emptyset$ \\
 5 \'             \> \key{do} \= determination of $r$\\
 6 \'             \>          \> ${\cal L}\,\leftarrow\,{\cal L}-{\cal F}_r$\\
 7 \'             \>          \> determination of $p(r)$\\
 8 \'             \>          \> determination of branching ${\cal F}_r\subset{\cal R}_1\cup...\cup{\cal R}_{p(r)}\;$\\
 9 \'             \>          \> \key{for} \= $i\leftarrow 1$ \key{to} $p(r)$ \key{do}\\
10 \'             \>          \>           \> ${\cal F}_{t+i}\,\leftarrow\,{\cal F}_r\cap{\cal R}_i$\\
11 \'             \>          \>           \> calculation of $({\bf x}_{t+i},z_{t+i})$\\
12 \'             \>          \>           \> \key{if} \= $z_{t+i}>\hat{z}$ \\
13 \'             \>          \>           \>          \> \key{then} \= \key{if} \= ${\bf x}_{t+i} \in{\cal F}$ \\ 
14 \'             \>          \>           \>          \>                     \> \key{then} \= $\hat{z}\,\leftarrow\,z_{t+i}$\\
15 \'             \>          \>           \>          \> \key{else} \> ${\cal L}\,\leftarrow\,{\cal L}+{\cal F}_{t+i}$ \\
16 \'             \> $t\,\leftarrow\,t+p(r)$\\
17 \'             \> \key{for} \= $i\leftarrow 1$ \key{to} $t$ \key{do}\\
18 \'             \>           \> \key{if} \= $z_i\leq\hat{z}$ \\
19 \'             \>           \>          \> \key{then} ${\cal L}\,\leftarrow\, {\cal L}-{\cal F}_i$\\
20 \' \key{return} \textbf{x}
\end{algN}
\vspace{-4mm}
\newpage
\noindent The operations in rows 5, 7, 8, and 11 depend on the particular problem class and 
on the skills of the designer of the algorithm. The relaxed subproblem is solved in row 14.
A detailed example is discussed in the next section.
The handling of the list needs also careful consideration. Section \ref{s2} is devoted to this topic. 

The loop in rows 17 and 18 can be executed in an implicit way. If the selected
subproblem in row 5 has a low upper bound, i.e. $z_r\leq \hat{z}$ then the
subproblem is fathomed and a new subproblem is selected.

However the most important issue is the number of required operations including
the finiteness of the algorithm. The method is not necessarily finite. Especially
nonlinear programming has infinite versions of it. Infinite loop may occur even
in the case if the number of the feasible solutions is finite. The problem can be
caused by an incautious branching procedure. A branch can belong to an empty set.
Assume that that the branching procedure generates subsets from ${\cal F}_r$ such
that one of the subsets ${\cal F}_{t+1},...,{\cal F}_{t+p(r)}$ is equal to 
${\cal F}_r$ and the other ones are empty sets. Thus there is an index i such that
\begin{eqnarray}\label{e42}
{\cal F}_{t+i}\;=\;{\cal F}_r,\;\;{\cal F}_{t+1}=...={\cal F}_{t+i-1}=
{\cal F}_{t+i+1}=...={\cal F}_{t+p(r)}=\emptyset \koz.
\end{eqnarray}
If the same situation is repeated at the branching of ${\cal F}_{t+i}$ 
then an infinite loop is possible.

Assume that a zero-one optimization problem of $n$ variables
is solved by B\&B and the branching is
made always according to the two values of a free variable. Generally it is
not known that how large is the number of the feasible solutions. There are at most 
$2^n$ feasible solutions as it is the number of the zero-one vectors. After the
first branching there are at most $2^{n-1}$ feasible solutions in the two 
first level leaves, each. This number is halved with each branching, i.e. in a
branch on level $k$ there are at most $2^{n-k}$ feasible solutions. It implies
that on level $n$ there is at most $2^{n-n}=2^0=1$ feasible solution. As a matter
of fact on that level there is exactly 1 zero-one vector and it is possible to
decide whether or not it is feasible. Hence after generating all branches on
level $n$ the problem can be solved. This idea is generalized in the following 
finiteness theorem. While formulating the statement the previous notations are
used.

\begin{tetel}\label{t4}
Assume that\\
(i) The set ${\cal F}$ is finite.\\
(ii) There is a finite set ${\cal U}$ such that the following conditions are
satisfied. If a subset ${\cal \hat{F}}$ is generated in the course of the
branch and bound method then there is a subset ${\cal \hat{U}}$ of ${\cal U}$
such that  ${\cal \hat{F}}\subseteq {\cal \hat{U}}$. Furthermore if the branching
procedure creates the cover ${\cal R}_1\cup\ldots\cup{\cal R}_p\supseteq{\cal \hat{F}}$
then  ${\cal \hat{U}}$ has a partitioning such that
\begin{eqnarray*}
{\cal \hat{U}}={\cal \hat{U}}_1\cup\cdots\cup{\cal \hat{U}}_p,\;
{\cal \hat{U}}_i\cap{\cal \hat{U}}_j=\emptyset (i\neq j)\\
{\cal \hat{F}}\cap{\cal \hat{R}}j\subseteq{\cal \hat{U}}_j (j=1,\ldots,p)
\end{eqnarray*}
and moreover
\begin{eqnarray}\label{e43}
1\leq\mid{\cal \hat{U}}_j\mid<\mid{\cal \hat{U}}\mid\;\;(j=1,\ldots,p)\koz.
\end{eqnarray}
(iii) If a set ${\cal \hat{U}}$ belonging to set ${\cal \hat{F}}$ has only a single
element then the relaxed subproblem solves the unrelaxed subproblem as well.


Then the \textsc{Branch-and-Bound} procedure stops after finite many steps. If
$\hat{z}=-\infty$ then there is no feasible solution. Otherwise $\hat{z}$ is
equal to the optimal objective function value. 
 \end{tetel}


{\bf Remark.} Notice that the binary problems mentioned above with ${\cal \hat{U}}_j$'s
of type
\[{\cal \hat{U}}_j\,=\,\{{\bf x}\in\{0,1\}^n\mid x_k=\delta_{kj},\; k\in I_j\}\koz,\]
where $I_j\subset\{1,2,\ldots,n\}$ is the set of fixed variables and 
$\delta_{kj}\in\{0,1\}$ is a fixed value, satisfy the conditions of the theorem.

\smallskip
\begin{biz}
Assume that the procedure \textsc{Branch-and-Bound} executes
infinite many steps. As the set ${\cal F}$ is finite it follows that there is at
least one subset of ${\cal F}$ say ${\cal F}_r$ such that it defines infinite
many branches implying that the situation
described in (\ref{e42}) occurs infinite many times. Hence there is an infinite
sequence of indices, say $r_0=r<r_1<\cdots$, such that ${\cal F}_{r_{j+1}}$ is
created at the branching of ${\cal F}_{r_{j}}$ and 
${\cal F}_{r_{j+1}}={\cal F}_{r_{j}}$. On the other hand the parallel sequence of
the ${\cal U}$ sets must satisfy the inequalities
\begin{eqnarray*}
\mid{\cal U}_{r_{0}}\mid>\mid{\cal U}_{r_{1}}\mid>\cdots\geq 1 \koz.
\end{eqnarray*}
It is impossible because the ${\cal U}$s are finite sets.

The finiteness of ${\cal F}$ implies that optimal solution exists if and only if
${\cal F}$ is nonempty, i.e. the problem cannot be unbounded and if feasible solution
exist then the supremum of the objective function is its maximum. The initial value of
$\hat{z}$ is $-\infty$. It can be changed only in Row 18 of the algorithm and if it
is changed then it equals to the objective function value of a feasible solution. Thus
if there is no feasible solution then it remains $-\infty$. Hence if the second half
of the statement is not true, then at the end of the algorithm $\hat{z}$ equal
the objective function value of a non-optimal feasible solution or it remains $-\infty$.

Let $r$ be the maximal index such that ${\cal F}_r$ still contains the optimal
solution. Then
\[z_r\geq\hbox{optimal value}>\hat{z} \koz.\]
Hence it is not possible that the branch containing the optimal solution has been deleted
from the list in the loop of Rows 22 and 23, as $z_r>\hat{z}$. It is also sure that
the subproblem 
\[\max\{f({\bf x})\mid{\bf x}\in{\cal F}_r\}\]
has not been solved, otherwise the equation $z_r=\hat{z}$ should hold. Then only
one option remained that ${\cal F}_r$ was selected for branching once in the course
of the algorithm. The optimal solution must be contained in one of its subsets,
say ${\cal F}_{t+i}$ which contradicts the assumption that ${\cal F}_r$ has the
highest index among the branches containing the optimal solution.
\end{biz}

If an optimization problem contains only bounded integer variables then the sets 
${\cal U}$s are the sets the integer vectors in certain boxes. In the case of some
scheduling problems where the optimal order of tasks is to be determined even the
relaxations have combinatorial nature because they consist of permutations. Then
${\cal U}={\cal R}$ is also possible. In both of the cases Condition (iii) of
the theorem is fulfilled in a natural way.

\begin{gyak}
\ujgyak Decide if the Knapsack Problem\gyakindex{Knapsack Problem} 
can be a relaxation of the Linear Binary Optimization 
Problem in the sense of Definition \ref{d2}. Explain your solution regardless that your answer is YES or NO.
\end{gyak}

\section{Mixed integer programming with bounded variables}
Many decisions have both continuous and discrete nature. For example in the production
of electric power the discrete decision is to switch on or not an equipment. The
equipment can produce electric energy in a relatively wide range. Thus if the first
decision is to switch on then a second decision must be made on the level of the
produced energy. It is a continuous decision. The proper mathematical model of such
problems must contain both discrete and continuous variables.

This section is devoted to the mixed integer linear programming problem with bounded
integer variables. It is assumed that there are $n$ variables and a subset of them,
say ${\cal I}\subseteq\{1,\ldots,n\}$ must be integer. The model has $m$ linear
constraints in equation form and each integer variable has an explicit integer
upper bound. It is also supposed that all variables must be nonnegative. More
formally the mathematical problem is as follows.
\begin{eqnarray}\label{e44}
\max\,{\bf c}^T{\bf x}
\end{eqnarray}
\begin{eqnarray}\label{e45}
{\bf A}{\bf x}={\bf b}
\end{eqnarray}
\begin{eqnarray}\label{e46}
\forall\,j\in{\cal I}:\;x_j\leq g_j
\end{eqnarray}
\begin{eqnarray}\label{e47}
x_j\geq 0\;\;j=1,\ldots,n
\end{eqnarray}
\begin{eqnarray}\label{e48}
\forall\,j\in{\cal I}:\;x_j\;\hbox{ is integer \koz,}
\end{eqnarray}
where ${\bf c}$ and ${\bf x}$ are $n$-dimensional vectors, 
${\bf A}$ is an $m\times n$ matrix,
${\bf b}$ is an $m$-dimensional vector and finally all $g_j\,(j\in{\cal I})$ is
a positive integer.

In the mathematical analysis of the problem below the the explicit upper bound constraints
(\ref{e46}) will not be used. The Reader may think that they are formally included into
the other algebraic constraints (\ref{e45}).

There are technical reasons that the algebraic constraints in (\ref{e45}) are claimed 
in the form of equations. Linear programming relaxation is used in the method. The
linear programming problem is solved by the simplex method which needs this form. But
generally speaking equations and inequalities can be transformed into one another in
an equivalent way. Even in the numerical example discussed below inequality form
is used.

First a numerical example is analyzed. The course of the method is discussed from 
geometric point of view. Thus some technical details remain concealed. Next
simplex method and related topics are discussed. All technical details can be
described only in the possession of them. Finally some strategic points of the algorithm
are analyzed.

\subsection{The geometric analysis of a numerical example}\label{ss4}
The problem to be solved is
\begin{eqnarray}\label{e49}
\begin{array}{cccrrrrr}
\max & x_0 & = & 2x_1 & + & x_2\\ &&& 3x_1 & - & 5x_2 & \leq & 0\\
 &&& 3x_1 & + & 5x_2 & \leq & 15\\ &&&
\multicolumn{5}{c}{x_1,\,x_2\,\geq\,0}\\ &&&
\multicolumn{5}{c}{x_1,\,x_2\,\hbox{is integer}\koz.}
\end{array}
\end{eqnarray}
To obtain a relaxation the integrality constraints are omitted from the problem.
Thus a linear programming problem of two variables is obtained.


\begin{center}
\begin{figure}[!t]
\unitlength 1mm
\begin{picture}(120,100)
\multiput(10,10)(20,0){6}{\line(0,1){90}}
\multiput(10,10)(0,20){5}{\line(1,0){110}}
\put(10,10){\line(5,3){100}}
\put(10,70){\line(5,-3){100}}
\put(29,5){{\Large\bf 1}}
\put(49,5){{\Large\bf 2}}
\put(69,5){{\Large\bf 3}}
\put(89,5){{\Large\bf 4}}
\put(109,5){{\Large\bf 5}}
\put(12,37){{\bf Feasible region}}

\put(5,5){{\Large\bf O}}
\put(59,42){{\Large\bf B}}
\put(12,72){{\Large\bf A}}

\put(5,28){{\Large\bf 1}}
\put(5,48){{\Large\bf 2}}
\put(5,68){{\Large\bf 3}}
\put(5,88){{\Large\bf 4}}

\put(75,10){\line(-1,2){45}}
\put(45,80){$2x_1+x_2=\frac{13}{2}$}
\end{picture}
\caption{ The geometry of linear programming relaxation of
Problem (\ref{e49}) including the feasible region 
(triangle $\overline{{\bf\hbox{OAB}}}$), the optimal solution ($x_1=2.5,\,x_2=1.5$),
and the optimal level of the
objective function represented by the line $2x_1+x_2=\frac{13}{2}$.\label{f242}}
\end{figure}
\end{center}

\begin{center}
\begin{figure}[!t]
\unitlength 1mm
\begin{picture}(80,80)
\multiput(10,10)(20,0){4}{\line(0,1){70}}
\multiput(10,10)(0,20){4}{\line(1,0){70}}
\put(10,10){\line(5,3){50}}
\put(10,70){\line(5,-3){50}}
\put(29,5){{\Large\bf 1}}
\put(49,5){{\Large\bf 2}}
\put(69,5){{\Large\bf 3}}

\put(5,5){{\Large\bf O}}
\put(59,42){{\normalsize\bf B}}
\put(12,72){{\normalsize\bf A}}
\put(46,43){{\normalsize\bf C}}
\put(51,31){{\normalsize\bf D}}

\put(45,51){{\normalsize\bf E}}
\put(11,46){{\normalsize\bf F}}
\put(45,26){{\normalsize\bf G}}
\put(11,26){{\normalsize\bf H}}
\put(27,55){{\normalsize\bf I}}
\put(31,46){{\normalsize\bf J}}

\put(5,28){{\Large\bf 1}}
\put(5,48){{\Large\bf 2}}
\put(5,68){{\Large\bf 3}}

\put(50,60){\vector(-1,0){5}}
\put(31,59){Branch 2}
\put(70,60){\vector(1,0){5}}
\put(76,59){Branch 3; EMPTY}
\put(73,30){\vector(0,-1){5}}
\put(71,22){Branch 4}
\put(20,50){\vector(0,1){5}}
\put(10.5,56){Branch 5}
\put(30,77){\vector(-1,0){5}}
\put(11,76){Branch 6}
\end{picture}
\caption{ The geometry of the course of the solution. The co-ordinates of the points
are: O=(0,0), A=(0,3), B=(2.5,1.5), C=(2,1.8), D=(2,1.2), E=($\frac{5}{3}$,2),
F=(0,2), G=($\frac{5}{3}$,1), H=(0,1), I=(1,2.4), and J=(1,2).
The feasible regions of the relaxation are
as follows.
Branch 1: $\overline{OAB}$, Branch 2: $\overline{OACD}$, Branch 3: empty set,
Branch 4: $\overline{OHG}$, Branch 5: $\overline{AEF}$, Branch 6:
$\overline{AIJF}$, Branch 7: empty set (not on the figure). Point J is the
optimal solution.\label{f244}
}
\end{figure}
\end{center}



\begin{center}
\begin{figure}[!t]
\unitlength 1mm
\begin{picture}(120,160)
\put(50,5){\framebox(20,20){\hbox{  }
\parbox{18mm}{ $\;\;x_1=1$\\ \hbox{    }$x_2\,=\,2$\\ solution}}}
\put(60,25){\line(0,1){10}}
\put(60,42){\circle{16}}
\put(48,40){\large\bf 6}
\put(59,38){4}
\put(57,44){4/3}
\put(53,42){\line(1,0){14}}

\put(60,49){\line(2,3){13}}
\put(74,75){\circle{16}}
\put(62,73){\large\bf 5}
\put(69,71){5 1/3}
\put(70,77){7/15}
\put(67,75){\line(1,0){14}}
\put(55,58){$x_1\leq 1$}
\put(74,82){\line(-2,3){13}}
\put(72,88){$x_2\geq 2$}

\put(90,49){\line(-2,3){13}}
\put(91,42){\circle{16}}
\put(79,40){\large\bf 7}
\put(88,38){$-\infty$}
\put(84,42){\line(1,0){14}}
\put(85,58){$x_1=2$}

\put(43,82){\line(2,3){13}}
\put(43,75){\circle{16}}
\put(31,73){\large\bf 4}
\put(38,71){4 1/3}
\put(39,77){4/5}
\put(36,75){\line(1,0){14}}
\put(34,88){$x_2\leq 1$}

\put(58,115){\line(2,3){13}}
\put(57.0,108){\circle{16}}
\put(44,106){\large\bf 2}
\put(53,104){5 4/5}
\put(53,110){7/10}
\put(49,108){\line(1,0){14}}
\put(47,121){$x_1\leq 2$}

\put(74.0,141){\circle{16}}
\put(62,139){\large\bf 1}
\put(69,137){6 1/2}
\put(67,141){\line(1,0){14}}

\put(90,115){\line(-2,3){13}}
\put(91,108){\circle{16}}
\put(79,106){\large\bf 3}
\put(88,104){$-\infty$}
\put(84,108){\line(1,0){14}}
\put(88,121){$x_1\geq 3$}
\end{picture}
\caption{ The course of the solution of Problem (\ref{e49}).
The upper numbers in the circuits are explained in subsection \ref{ss1}. They are
the corrections of the previous bounds obtained from the first pivoting step of the
simplex method.
The lower numbers are the (continuous) upper bounds obtained in the branch.\label{f243}}
\end{figure}
\end{center}

The branching is made according to a non-integer variable. Both
$x_1$ and $x_2$ have fractional values. To keep the number of branches as low
as possible, only two new branches are created in a step. 

The numbering of the branches is as follows. The original set of feasible
solutions is No. 1. When the two new branches are generated then the branch
belonging to the smaller values of the branching variable has the smaller number.
The numbers are positive integers started at 1 and not skipping any integer.
Branches having no feasible solution are numbered, too.

The  optimal solution of the relaxation is $x_1=2.5,\,x_2=1.5$,
and the optimal value is $\frac{13}{2}$ as it can be seen from figure \ref{f242}. 
The optimal solution is
the intersection point the lines determined by the equations
\[3x_1 - 5x_2 =  0\]
and
\[ 3x_1 + 5x_2 = 15 \koz.\]
If the branching
is based on variable $x_1$ then they are defined by the inequalities
\[x_1\leq 2\;\;\hbox{ and }\;\;x_1\geq 3\;.\]
Notice that the maximal value of $x_1$ is 2.5. In the next subsection
the problem is revisited. Then this fact will be observed from the simplex
tableaux. Variable $x_2$ would
create the branches
\[x_2\leq 1\;\;\hbox{ and }\;\;x_2\geq 2\;.\]
None of them is empty. Thus it is more advantageous the branch according to
$x_1$. Geometrically it means that the set of the feasible solutions 
in the relaxed problem is cut by the line $x_1=2$. Thus the new set 
becomes the quadrangle $\overline{OACD}$ on Figure \ref{f244}. The optimal
solution on that set is $x_1=2,\,x_2=1.8$. It is point C on the figure.

Now branching is possible according only to variable $x_2$. Branches 4 and
5 are generated by the cuts $x_2\leq 1$ and $x_2\geq 2$, respectively. 
The feasible regions of the relaxed problems are $\overline{OHG}$ of Branch 4, and
$\overline{AEF}$ of Branch 5. The method continues with the investigation 
of Branch 5. The reason will be given in the next subsection when the 
quickly calculable upper bounds are discussed. On the other hand it is
obvious that the set $\overline{AEF}$ is more promising than $\overline{OHG}$
if the Reader takes into account the position of the contour, i.e. the level line, of the
objective function on Figure \ref{f244}. The algebraic details discussed in
the next subsection serve to realize the decisions in higher dimensions what
is possible to see in 2-dimension.

Branches 6 and 7 are defined by the inequalities $x_1\leq 1$ and $x_1\geq 2$,
respectively. The latter one is empty again. The feasible region of Branch
6 is $\overline{AIJF}$. The optimal solution in this quadrangle is the Point I.
Notice that there are only three integer points in $\overline{AIJF}$ which
are (0,3), (0,2), and (1,2). Thus the optimal integer solution of this branch
is (1,2). There is a technique which can help to leap over the continuous
optimum. In this case it reaches directly point J, i.e. the optimal integer
solution of the branch as it will be seen in the next section, too. Right now
assume that the integer optimal solution with objective function value 4 is
uncovered.

At this stage of the algorithm the only unfathomed branch is Branch 4 with
feasible region $\overline{OHG}$. Obviously the optimal solution is point
G=($\frac{5}{3}$,1). Its objective function value is $\frac{13}{3}$. Thus it
cannot contain a better feasible solution than the known (1,2). Hence
the algorithm is finished.

\subsection{The linear programming background of the method}\label{ss1}
The first ever general method solving linear programming problems were discovered
by George Dantzig and called {\em simplex method}.\index{simplex method}
\nevindex{Dantzig, George Bernard (1914--2005)}\index{dual simplex method} There are plenty of versions
of the simplex method. The main tool of the algorithm is the so-called 
{\em dual simplex method}. Although simplex method is discussed in 
a previous volume,
the basic knowledge is summarized here.

Any kind of simplex method is a so-called pivoting algorithm. 
{\em An important property of the pivoting algorithms is that they generate 
equivalent forms of the equation system and -- in the case of linear programming
-- the objective function}.
Practically it
means that the algorithm works with equations. As many variables as many
linearly independent equations exist are expressed with other variables and
further consequences are drawn from the current equivalent form of the
equations.

If there are inequalities in the problem then they are reformulated by
introducing nonnegative slack variables. E.g. in case of LP-relaxation of Problem
(\ref{e49}) the equivalent form of the problem is
\begin{eqnarray}\label{e50}
\begin{array}{cccrrrrrrrrr}
\max & x_0 & = & 2x_1 & + & x_2 & + & 0x_3 & + & 0x_4\\ 
&&& 3x_1 & - & 5x_2 & + & x_3 & + & 0x_4 & = & 0\\
 &&& 3x_1 & + & 5x_2 & + & 0x_3 & + & x_4 & =  & 15\\ &&&
\multicolumn{5}{c}{x_1,\,x_2\,x_3,\,x_4\,\geq\,0\koz.}
\end{array}
\end{eqnarray}
Notice that all variables appear in all equations including the objective function,
but it is allowed that some coefficients are zeros. The current version (\ref{e50})
can be considered as a form where the variables $x_3$ and $x_4$  are expressed by
$x_1$ and $x_2$ and the expression is substituted into the objective function.
If $x_1=x_2=0$ then $x_3=0$ and $x_4=15$, thus the solution is feasible. Notice that
the value of the objective function is 0 and if it is possible to increase the value
of any of $x_1$ and $x_2$ and still getting a feasible solution
then a better feasible solution is obtained. 
It is true, because the method uses equivalent forms of the objective function. 
The method obtains better feasible solution by pivoting. 
Let $x_1$ and $x_2$ be the
two expressed variables. Skipping some pivot steps the equivalent form of (\ref{e50}) is
\begin{eqnarray}\label{e51}
\begin{array}{cccrrrrrrrrr}
\max & x_0 & = & 0x_1 & + & 0x_2 & - & \frac{7}{30}x_3 & - & \frac{13}{30}x_4 & + & 
\frac{13}{2}\\ \;\\ 
&&& x_1 & + & 0x_2 & + & \frac{1}{6}x_3 & + & \frac{1}{6}x_4 & = & \frac{5}{2}\\ \;\\
 &&& 0x_1 & + & x_2 & - & \frac{1}{10}x_3 & + & \frac{1}{10}x_4 & =  & \frac{3}{2}\\ &&&
\multicolumn{5}{c}{x_1,\,x_2\,x_3,\,x_4\,\geq\,0\koz.}
\end{array}
\end{eqnarray}
That form has two important properties. First if $x_3=x_4=0$ then 
$x_1=\frac{5}{2}$ and $x_2=\frac{3}{2}$, thus the solution is feasible, similarly to the
previous case. Generally this property is called {\em primal feasibility}.
\index{primal feasibility}\index{dual feasibility}
Secondly, the coefficients of the non-expressed variables are negative
in the objective function. It is called {\em dual feasibility}.
It implies that if any of the non-expressed variables
is positive in a feasible solution then that is worse than the current one.
It is true again, because the current form of the objective function is equivalent to
the original one.
Thus the current value of the objective function which is $\frac{13}{2}$, is optimal. 

In what follows the sign of maximization and the nonnegativity of the variables will
be omitted from the problem but they are kept in mind.

In the general case it may be assumed without loss of generality that all equations
are independent. Simplex method uses the form of the problem
\begin{eqnarray}\label{e52}
\max\,x_0={\bf c}^T{\bf x}\\ \label{e53}
{\bf A}{\bf x}={\bf b}\\ \label{e54}
{\bf x}\geq {\bf 0}\koz,
\end{eqnarray}
where ${\bf A}$ is an $m\times n$ matrix, ${\bf c}$ and ${\bf x}$ are 
$n$-dimensional vectors, and ${\bf b}$ is an $m$-dimensional vector.
According to the assumption that all equations are independent, ${\bf A}$
has $m$ linearly independent columns. They form a basis of the $m$-dimensional linear
space. They also form an $m\times m$ invertible submatrix. It is denoted by ${\bf B}$.
The inverse of ${\bf B}$ is ${\bf B}^{-1}$.
Matrix ${\bf A}$ is partitioned into the basic and non-basic parts: ${\bf A=(B,N)}$
and the vectors ${\bf c}$ and ${\bf x}$ are partitioned accordingly. Hence
\[{\bf Ax}={\bf Bx}_B+{\bf Nx}_N={\bf b}\,.\]
The expression of the basic variables is identical with the multiplication of the
equation by ${\bf B}^{-1}$ from left
\[{\bf B}^{-1}{\bf Ax}={\bf B}^{-1}{\bf Bx}_B+{\bf B}^{-1}{\bf Nx}_N
={\bf Ix}_B+{\bf B}^{-1}{\bf Nx}_N={\bf B}^{-1}{\bf b},\koz\]
where ${\bf I}$ is the unit matrix. Sometimes the equation is used in the form
\begin{eqnarray}\label{e60}
{\bf x}_B={\bf B}^{-1}{\bf b}-{\bf B}^{-1}{\bf Nx}_N\koz.
\end{eqnarray}

The objective function can be transformed into the equivalent form
\[{\bf c}^T{\bf x}={\bf c}_B^T{\bf x}_B+{\bf c}_N^T{\bf x}_N \] 

\[{\bf c}_B^T({\bf B}^{-1}{\bf b}-{\bf B}^{-1}{\bf Nx}_N)+{\bf c}_N^T{\bf x}_N=
{\bf c}_B^T{\bf B}^{-1}{\bf b}+({\bf c}_N^T-{\bf c}_B^T{\bf B}^{-1}{\bf N}){\bf x}_N\koz.\]
Notice that the coefficients of the basic variables are zero.
If the non-basic variables are zero valued then the value of the
basic variables is given by the equation
\[{\bf x}_B={\bf B}^{-1}{\bf b}\koz.\]
Hence the objective function value of the basic solution is 
\begin{eqnarray}\label{e58}
{\bf c}^T{\bf x}={\bf c}_B^T{\bf x}_B+{\bf c}_N^T{\bf x}_N
={\bf c}_B^T{\bf B}^{-1}{\bf b}+{\bf c}_N^T{\bf 0}={\bf c}_B^T{\bf B}^{-1}{\bf b}\koz.
\end{eqnarray}

\begin{defi}\label{d3}
A vector ${\bf x}$ is a {\em\bf solution} of Problem (\ref{e52})-(\ref{e54})
if it satisfies the equation (\ref{e53}). It is a {\em\bf feasible solution}
or equivalently a {\em\bf primal feasible solution} if it satisfies both
(\ref{e53}) and (\ref{e54}). A solution ${\bf x}$ is a {\em\bf basic solution} 
if the columns of
matrix ${\bf A}$ belonging to the non-zero components of ${\bf x}$ are
linearly independent. A basic solution is a {\em\bf basic
feasible} or equivalently a {\em\bf basic primal feasible} solution if it is
feasible. Finally a basic solution is {\em\bf basic dual feasible solution}
if 
\begin{eqnarray}\label{e55}
{\bf c}_N^T-{\bf c}_B^T{\bf B}^{-1}{\bf N}\leq{\bf 0}^T\koz.
\end{eqnarray}
\end{defi}
\index{solution (of linear programming problem)}
\index{feasible solution}
\index{basic solution}
\index{basic feasible solution}
\index{basic primal feasible solution}
\index{basic dual feasible solution}

The primal feasibility of a basic feasible solution is equivalent to
\begin{eqnarray*}%\label{e56}
{\bf B}^{-1}{\bf b}\geq{\bf 0}\koz.
\end{eqnarray*}
Let ${\bf a}_1,\ldots,{\bf a}_n$ be the column vectors of matrix ${\bf A}$.
Further on let ${\cal I}_B$ and ${\cal I}_N$ be the set of indices of the basic
and non-basic variables, respectively. Then componentwise reformulation of (\ref{e55}) is
\begin{eqnarray*}%\label{e57}
\forall\,j\in{\cal I}_N:\;c_j-{\bf c}_B^T{\bf B}^{-1}{\bf a}_j\leq 0\koz.
\end{eqnarray*}
The meaning of the dual feasibility is this. The current value of the objective
function given in (\ref{e58}) is an upper bound of the optimal value as all
coefficients in the equivalent form of the objective function is nonpositive.
Thus if any feasible, i.e. nonnegative, solution is substituted in it then
value can be at most the constant term, i.e. the current value. 
\begin{defi} A basic solution is \ki{OPTIMAL} if it is both
primal and dual feasible.
\end{defi}

It is known from the theory of linear programming that among the optimal solutions
there is always at least one basic solution. To prove this statement is beyond the scope
of the chapter.

In Problem (\ref{e50})
\begin{eqnarray*}
{\bf A}=\left(\begin{array}{rrrr}3 & -5 & 1 & 0\\ 3 & 5 & 0 & 1\end{array}\right)\;\;
{\bf b}=\left(\begin{array}{r}0\\ 15 \end{array}\right)\;\;
{\bf c}=\left(\begin{array}{r}2 \\ 1 \\ 0 \\ 0\end{array}\right)\;.
\end{eqnarray*}
If the basic variables are $x_1$ and $x_2$ then
\begin{eqnarray*}
{\bf B}=\left(\begin{array}{rr}3 & -5 \\ 3 & 5\end{array}\right)\;\;
{\bf B}^{-1}=\frac{1}{30}\left(\begin{array}{rr}5 & 5\\ -3 & 3 \end{array}\right)\;\;
{\bf N}=\left(\begin{array}{rr}1 & 0 \\  0 & 1\end{array}\right)\;\;
{\bf c}_{B}=\left(\begin{array}{r}2 \\ 1 \end{array}\right)\koz.
\end{eqnarray*}
Hence
\begin{eqnarray*}
{\bf c}_{B}^T{\bf B}^{-1}=(2,1)\frac{1}{30}\left(\begin{array}{rr}5 & 5\\ -3 & 3 \end{array}\right)=
\left(\frac{7}{30},\,\frac{13}{30}\right)
\end{eqnarray*}
\begin{eqnarray*}
{\bf B}^{-1}{\bf b}=\frac{1}{30}\left(\begin{array}{rr}5 & 5\\ -3 & 3 \end{array}\right)
\left(\begin{array}{r}0\\ 15 \end{array}\right)=
\left(\begin{array}{r}{75/30}\\ {45/30}\end{array}\right)=
\left(\begin{array}{r}{5/2}\\ {3/2}\end{array}\right),\;\;
{\bf B}^{-1}{\bf N}={\bf B}^{-1}\koz.
\end{eqnarray*}
The last equation is true as ${\bf N}$ is the unit matrix. Finally
\begin{eqnarray*}
{\bf c}_{N}^T-{\bf c}_{B}^T{\bf B}^{-1}{\bf N}=(0,\,0)-\left(\frac{7}{30},\,\frac{13}{30}\right)
\left(\begin{array}{rr}1 & 0 \\  0 & 1\end{array}\right)=\left(-\frac{7}{30},\,-\frac{13}{30}\right)\koz.
\end{eqnarray*}
One can conclude that this basic solution is both primal and dual feasible.

There are two types of simplex methods. Primal simplex method starts from 
a\index{primal simplex method} primal feasible basic solution. Executing
pivoting steps it goes through primal feasible basic solutions and finally
even the dual feasibility achieved. The objective function values are monotone
increasing in the primal simplex method.

\index{dual simplex method}The dual simplex method starts from a dual feasible
basic solution it goes through dual feasible basic solutions until even primal
feasibility is achieved in the last iteration. The objective function values are monotone decreasing
in the dual simplex method. We discuss it in details as it is the main algorithmic
tool of the method.

Each simplex method uses its own simplex tableau. Each tableau contains the transformed
equivalent forms of the equations and the objective function. In the case of the
dual simplex tableau the elements of it are derived from the form of the equations
\[{\bf x}_B={\bf B}^{-1}{\bf b}-{\bf B}^{-1}{\bf Nx}_N
={\bf B}^{-1}{\bf b}+{\bf B}^{-1}{\bf N}(-{\bf x}_N)\koz,\]
where the second equation indicates that the minus sign is associated to non-basic
variables. The dual simplex tableau contains the expression of {\em all} variables by
the negative non-basic variables including the objective function variable $x_0$ and the
non-basic variables. For the latter ones the trivial
\[x_j=-(-x_j)\]
equation is included. For example the dual simplex tableau for (\ref{e50}) is 
provided that the basic variables are $x_1$ and $x_2$ (see (\ref{e51}))
\begin{eqnarray*}
\begin{array}{l||r|rr}
\hbox{variable} & \hbox{constant} & -x_3 & -x_4\\ \hline x_0 & 13/2 & 7/30 & 13/30\\
\hline  x_1 & 5/2 & 1/6 & 1/6 \\ 
\hline x_2 & 3/2 & -1/10 & 1/10 \\
\hline x_3 & 0 & -1 & 0\\ \hline x_4 & 0 & 0 & -1\\ \hline
\end{array}
\end{eqnarray*}
Generally speaking the potentially non-zero coefficients of the objective function
are in the first row, the constant terms are in the first column and all other coefficients are
in the inside of the tableau. The order of the rows is never changed. On the other hand a variable
which left the basis immediately has a column instead of that variable which entered the basis.

The elements of the dual simplex tableau are denoted by $d_{jk}$ where $k=0$ refers to the constant
term of the equation of variable $x_j$ and otherwise $k\in I_N$ and $d_{jk}$ is the coefficient of
the non-basic variable $-x_k$ in the expression of the variable $x_j$. 
As $x_0$ is the objective function variable $d_{0k}$ is the coefficient of $-x_k$
in the equivalent form (\ref{e60}) of the objective function.
The dual simplex tableau can be seen on Figure \ref{f245}.
\begin{center}
\begin{figure}[!t]
\unitlength 1mm
\begin{picture}(100,80)
\put(10,10){\line(0,1){45}}
\put(50,10){\line(0,1){45}}
\put(0,45){\line(1,0){50}}
\put(3,47){{\Large\bf $d_{00}$}}
\put(7,68){\vector(0,-1){15}}
\put(0,70){\bf objective function value}
\put(20,47){{\Large\bf $d_{0k}$}}
\put(43,60){\vector(-3,-2){17}}
\put(35,61){\bf objective function coefficient}
\put(3,27){{\Large\bf $d_{j0}$}}
\put(0,10){\line(1,0){50}}
\put(7,8){\vector(0,1){18}}
\put(0,5){\bf constant term in the equation of {\Large $x_j$}}
\put(20,27){{\Large\bf $d_{jk}$}}
\put(21,18){\vector(0,1){8}}
\put(12,15){\bf the coefficient of {\Large $-x_k$} in the equation of {\Large $x_j$}}
\end{picture}
\caption{The elements of the dual simplex tableau.\label{f245}}
\end{figure}
\end{center}

Notice that dual feasibility means that there are nonnegative elements in the first row of the
tableau with the potential exception of its first element, i.e. with the potential exception
of the objective function value.

Without giving the proof of its correctness the pivoting procedure is this. The aim of the
pivoting is to eliminate the primal infeasibility, i.e. the negative values of the variables,
with the potential exception of the objective function value, i.e. the elimination of the
negative terms from the first column. Instead of that basic variable $x_p$ a non-basic one will be
expressed from the equation such that the negative constant term becomes zero 
and the value of the new basic variable, i.e. the value of $x_k$, becomes positive. 
It is easy to see that
this requirement can be satisfied only if the new expressed variable, say $x_k$, has a negative
coefficient in the equation, i.e. $d_{pk}<0$. After the change of the basis the row of $x_p$ must
become a negative unit vector as $x_p$ became a non-basic variable, thus its expression is
\begin{eqnarray}\label{e59}
x_p=-(-x_p)\koz.
\end{eqnarray}
The transformation of the tableau consists of
the transformations of the columns such that the form (\ref{e59})
of the row of $x_p$ is generated. The position of the (-1) in the row is the crossing of the row of
$x_p$ and the column belonging to $x_k$ before pivoting. This column becomes the column of $x_p$.
There is another requirement claiming that the dual
feasibility must hold on. Let ${\bf d}_j$ be the column of the non-basic variable $x_j$ 
including ${\bf d}_0$ as the column of the constant terms. Then the formulae of the
column transformation are the followings where $j$ is either zero or the index of a non-basic 
variable different from $k$:
\begin{eqnarray}\label{e61}
{\bf d}^{new}_j={\bf d}^{old}_j-\frac{d^{old}_{pj}}{d^{old}_{pk}}{\bf d}^{old}_k
\end{eqnarray}
and
\begin{eqnarray*}%\label{e62}
{\bf d}^{new}_p=-\frac{1}{d^{old}_{pk}}{\bf d}^{old}_k\koz.
\end{eqnarray*}
To maintain dual feasibility means that after the change of the basis the relation 
$d^{new}_{0j}\geq 0$ must hold for all non-basic indices, i.e. for all $j\in{\cal I}^{new}_N$.
It follows from (\ref{e61}) that $k$ must be chosen such that
\begin{eqnarray}\label{e63}
k=\hbox{argmax}\left\{\frac{d^{old}_{0j}}{d^{old}_{pj}}\mid d^{old}_{pj}<0\right\} \koz.
\end{eqnarray} 
In the course of the branch method in the optimization of the relaxed subproblems dual
simplex method can save a lot of computation. On the other hand 
what is used in the description of the method, is 
only the effect of one pivoting on the value of the objective function. According to 
(\ref{e61}) the new value is
\begin{eqnarray*}%\label{e64}
d^{new}_{00}= d^{old}_{00}-\frac{d^{old}_{p0}}{d^{old}_{pk}}d^{old}_{0k} \koz.
\end{eqnarray*}
Notice that $d^{old}_{p0},\,d^{old}_{pk}\,<\,0$ and $d^{old}_{0k}\geq 0$. Hence the
objective function value decreases by the nonnegative value
\begin{eqnarray}\label{e65}
\frac{d^{old}_{p0}}{d^{old}_{pk}}d^{old}_{0k} \koz.
\end{eqnarray}

The formula (\ref{e65}) will be used if a new constraint is introduced at branching and
it cuts the previous optimal solution. As the new constraint has nothing to do with the
objective function, it will not destroy dual feasibility, but, of course, the optimal
solution of the relaxed problem of the branch becomes primal infeasible.

For example the inequality $x_1\leq 2$ is added to the relaxation (\ref{e50}) defining a new branch
then it is used in the equation form
\begin{eqnarray}\label{e66}
x_1 + x_5 = 2\koz,
\end{eqnarray}
where $x_5$ is nonnegative continuous variable. According to the simplex tableau
\[x_1\,=\,\frac{5}{2}+\frac{1}{6}(-x_3)+\frac{1}{6}(-x_4).\]
Hence
\begin{eqnarray}\label{e67}
x_5\,=\,-\frac{1}{2}-\frac{1}{6}(-x_3)-\frac{1}{6}(-x_4)\koz.
\end{eqnarray}
(\ref{e66}) is added to the problem in the form (\ref{e67}). Then the dual simplex tableau is
\begin{eqnarray*}
\begin{array}{l||r|rr}
\hbox{variable} & \hbox{constant} & -x_3 & -x_4\\ \hline x_0 & 13/2 & 7/30 & 13/30\\
\hline  x_1 & 5/2 & 1/6 & 1/6 \\ 
\hline x_2 & 3/2 & -1/10 & 1/10 \\
\hline x_3 & 0 & -1 & 0\\ \hline x_4 & 0 & 0 & -1\\ \hline
x_5 & -1/2 & -1/6 & -1/6\\ \hline
\end{array}
\end{eqnarray*}
Only $x_5$ has a negative value, thus the first pivoting must be done in its row. 
Rule (\ref{e63}) selects $x_3$ for entering the basis. Then after the first pivot step 
the value of the objective function decreases by
\begin{eqnarray*}
\frac{-\frac{1}{2}}{-\frac{1}{6}}\times\frac{7}{30}\,=\,\frac{7}{10}.
\end{eqnarray*}
If the optimal solution of the relaxed problem is not reached after the first pivoting
then further decrease is possible. But decrease of 0.7 is sure compared to the previous upper bound.

Another important property of the cuts is that if it has no negative coefficient in the form how
it is added to the simplex tableau then there is no negative pivot element, i.e. the relaxed
problem is infeasible, i.e. the branch is empty. For example the cut $x_1\geq 3$ leading to an
empty branch is added to the problem in the form
\[x_1\,-\,x_6\;=\;3\]
where $x_6$ is also a nonnegative variable. Substituting the value of $x_1$ again the equation
is transformed to
\[x_6=-\frac{1}{2}+\frac{1}{6}(-x_3)+\frac{1}{6}(-x_4) \koz.\]
Hence the simplex tableau
\begin{figure}[!t]
\begin{eqnarray*}
\begin{array}{l||r|rr}
\hbox{variable} & \hbox{constant} & -x_3 & -x_4\\ \hline x_0 & 13/2 & 7/30 & 13/30\\
\hline  x_1 & 5/2 & 1/6 & 1/6 \\ 
\hline x_2 & 3/2 & -1/10 & 1/10 \\
\hline x_3 & 0 & -1 & 0\\ \hline x_4 & 0 & 0 & -1\\ \hline
x_6 & -1/2 & 1/6 & 1/6\\ \hline
\end{array}
\end{eqnarray*}\label{figuretable1}
\end{figure}
is obtained. There is a negative value at the crossing point of the first column and the row of $x_6$.
But it is not possible to choose a pivot element in that row, as there is no negative element of the row.
It means that feasibility can not be achieved, i.e. that branch is infeasible and thus it is completely
fathomed.


\subsection{Fast bounds on lower and upper branches}\label{ss2}
The branching is always based on a variable which should be integer but in the current optimal solution of the
linear programming relaxation it has fractional value. If it has fractional value then its value is non-zero
thus it is basic variable. Assume that its index is $p$. Remember that ${\cal I}$, ${\cal I}_B$, 
and ${\cal I}_N$ are the index sets of the integer, basic, and non-basic variables, respectively. Hence
$p\in {\cal I}\cap{\cal I}_B$. According to the last simplex tableau $x_p$ is expressed by the non-basic
variables as follows:
\begin{eqnarray}\label{e68}
x_p\,=\,d_{p0}\,+\,\sum_{j\in{\cal I}_N}d_{pj}(-x_j) \koz.
\end{eqnarray}
As $d_{p0}$ has fractional value
\begin{eqnarray*}%\label{e69}
1\,>\,f_p\,=\,d_{p0}-\lfloor d_{p0}\rfloor > 0 \koz.
\end{eqnarray*}
The branch created by the inequality
\begin{eqnarray}\label{e70}
x_p\;\leq\;\lfloor d_{p0}\rfloor
\end{eqnarray}
is called {\em lower branch} and the inequality
\begin{eqnarray*}%\label{e71}
x_p\;\geq\;\lfloor d_{p0}\rfloor+1
\end{eqnarray*}
creates the {\em upper branch}.

Let ${\cal J}^{+}$ and ${\cal J}^{-}$ be the set of indices
of the nonbasic variables according to the signs of the coefficients in (\ref{e68}), i.e.  
\begin{eqnarray*}%\label{e73}
{\cal J}^{+}({\cal J}^{-})\,=\,\{j\mid j\in{\cal I}_N;\; d_{pj}>0\,(d_{pj}<0)\} \koz.
\end{eqnarray*}

First the lower branch is analyzed. It follows from (\ref{e68}) 
that the inequality (\ref{e70}) is equivalent to
\begin{eqnarray*}
x_p\,-\,\lfloor d_{p0}\rfloor\,=\,f_{p}\,+\,\sum_{j\in{\cal I}_N}d_{pj}(-x_j)\,\leq \koz 0.
\end{eqnarray*}
Thus
\begin{eqnarray}\label{e72}
s\,=\,-f_{p}\,+\,\sum_{j\in{\cal I}_N}(-d_{pj})(-x_j)
\end{eqnarray}
is a nonnegative variable and row (\ref{e72}) can be added to the dual simplex tableau.
It will contain the only negative element in the first column that is the optimization in the lower
branch starts by pivoting in this row. (\ref{e72}) can be reformulated according to the
signs of the coefficients as
\begin{eqnarray}\label{e74}
s\,=\,-f_{p}\,+\,\sum_{j\in{\cal J}^{+}}(-d_{pj})(-x_j)\,+\,\sum_{j\in{\cal J}^{-}}(-d_{pj})(-x_j) \koz.
\end{eqnarray}
The pivot element must be negative, thus it is one of $-d_{pj}$'s with $j\in{\cal J}^{+}$ \koz.
Hence the first decrease (\ref{e65}) of the objective function is
\begin{eqnarray}\label{e75}
P_{lp}\,=\,\min\left\{\frac{d_{0j}}{d_{pj}}f_{p}\mid j\in{\cal J}^{+}\right\} \koz.
\end{eqnarray}

In the upper branch the inequality (\ref{e70}) is equivalent to
\begin{eqnarray*}
x_p\,-\,\lfloor d_{p0}\rfloor\,=\,f_{p}\,+\,\sum_{j\in{\cal I}_N}d_{pj}(-x_j)\,\geq 1\koz.
\end{eqnarray*}
Again the nonnegative slack variable $s$ should be introduced. Then the row which can be added to the 
simplex tableau is
\begin{eqnarray}\label{e85}
s\,=\,(f_{p}-1)\,+\,\sum_{j\in{\cal J}^{+}}d_{pj}(-x_j)\,+\,\sum_{j\in{\cal J}^{-}}d_{pj}(-x_j) \koz.
\end{eqnarray}
Thus the pivot element must belong to one of the indices $j\in{\cal J}^{-}$ giving the value
\begin{eqnarray}\label{e76}
P_{up}\,=\,\min\left\{\frac{d_{0j}}{-d_{pj}}(1-f_{p})\mid j\in{\cal J}^{-}\right\} \koz.
\end{eqnarray}

Let $\hat{z}$ be the upper bound on the original branch obtained by linear programming.
Then the quantities $P_{lp}$ and $P_{up}$ define the upper bounds of the objective functions
$\hat{z}-P_{lp}$ and $\hat{z}-P_{up}$ on the lower and upper subbranches, respectively. They are not
substituting complete optimization in the subbranches. On the other hand they are easily computable
and can give some orientation to the selection of the next branch for further investigation
(see below).

The quantities $P_{lp}$ and $P_{up}$ can be improved, i.e. increased. The claim that the variable $s$
defined in (\ref{e74}) is nonnegative implies that
\begin{eqnarray}\label{e86}
-f_p\,\geq\,\sum_{j\in{\cal J}^{+}} d_{pj}(-x_j) \koz.
\end{eqnarray}
In a similar way the nonnegativity of variable $s$ in (\ref{e85}) implies that
\begin{eqnarray}\label{e87}
f_p\,-\,1\,\geq\,\sum_{j\in{\cal J}^{-}} (-d_{pj})(-x_j) \koz.
\end{eqnarray}
If (\ref{e87}) is multiplied by the positive number
\begin{eqnarray*}
\frac{f_p}{1-f_p}
\end{eqnarray*}
then it gets the form
\begin{eqnarray}\label{e88}
-f_p\,\geq\,\sum_{j\in{\cal J}^{-}} \frac{f_p}{1-f_p}(-d_{pj})(-x_j) \koz.
\end{eqnarray}
The inequalities (\ref{e86}) and (\ref{e88}) can be unified in the form:
\begin{eqnarray}\label{e89}
-f_p\,\geq\,\sum_{j\in{\cal J}^{+}} d_{pj}(-x_j)\,+\,\sum_{j\in{\cal J}^{-}} \frac{f_p}{1-f_p}(-d_{pj})(-x_j) \koz.
\end{eqnarray}
Notice that (\ref{e89}) {\em not} the sum of the two inequalities. The same negative number stands on the
left-hand side of both inequalities and is greater or equal than the right-hand side. Then both right-hand
sides must have negative value. Hence the left-hand side is greater than their sum.

The same technique is applied to the variable $x_p^{'}$ instead of $x_p$ with
\begin{eqnarray*}%\label{e90}
x_p^{'}\,=\,x_p\,+\,\sum_{j\in{\cal I}\cap{\cal I}_N}\mu_j x_j \koz,
\end{eqnarray*}
where $\mu_j$'s are integer values to be determined later. $x_p^{'}$ can be expressed by the non-basic variables as
\begin{eqnarray*}%\label{e91}
x_p^{'}\,=\,d_{p0}\,+\,\sum_{j\in{\cal I}\cap{\cal I}_N}(d_{pj}-\mu_j)(-x_j)\,+\,\sum_{j\in{\cal I}_N\setminus{\cal I}}d_{pj}(-x_j) \koz. 
\end{eqnarray*}
Obviously $x_p^{'}$ is an integer variable as well
and its current value if the non-basic variables are fixed to zero is equal to the current value of $d_{p0}$.
Thus it is possible to define the new branches according to the values of $x_p^{'}$. Then the inequality of type
(\ref{e89}) which is defined by $x_p^{'}$, has the form
\begin{eqnarray*}%\label{e92}
-f_p\geq\sum_{\small\begin{array}{c}j\in{\cal I}\cap{\cal I}_N\\ d_{pj}-\mu_j\geq 0\end{array}}(d_{pj}-\mu_j)(-x_j)+
\sum_{\small\begin{array}{c}j\in{\cal I}\cap{\cal I}_N\\ d_{pj}-\mu_j<0\end{array}}\frac{f_p}{1-f_p}(\mu_j-d_{pj})(-x_j)\\
%\label{e93}
+\;\sum_{\small\begin{array}{c}j\in{\cal I}_N\setminus{\cal I}\\ d_{pj}> 0\end{array}}d_{pj}(-x_j)+
\sum_{\small\begin{array}{c}j\in{\cal I}_N\setminus{\cal I}\\ d_{pj}<0\end{array}}\frac{f_p}{1-f_p}(-d_{pj})(-x_j) \koz.
\end{eqnarray*} 
The appropriate quantities $P^{'}_{lp}$ and $P^{'}_{up}$ are as follows:
$$%\label{e94}
P^{'}_{lp} = \min \{a,b\} \koz,
$$
where
$$
a = \min\left\{\frac{d_{0j}}{d_{pj}-\mu_j}f_{p}\mid j\in{\cal I}\cap{\cal I}_N, d_{pj}-\mu_j> 0\right\}
$$
and
$$
b = \min\left\{\frac{d_{0j}}{d_{pj}}f_{p}\mid j\in{\cal I}_N\setminus{\cal I},\,d_{pj} > 0\right\}\koz
$$
further
$$%\label{e94}
P^{'}_{up} = \min\{c,d\}\koz,
$$
where
$$ 
c = \min\left\{\frac{d_{0j}(1-f_p)^2}{(\mu_j-d_{pj})f_{p}}\mid j\in{\cal I}\cap{\cal I}_N, d_{pj}-\mu_j< 0\right\}\koz
$$
and
$$
d = \min\left\{-\frac{d_{0j}(1-f_{p})^2}{f_p d_{pj}}\mid j\in{\cal I}_N\setminus{\cal I},
\,d_{pj}<0\right\}\koz.
$$
The values of the integers must be selected in a way that the absolute values of the coefficients are 
as small as possible, because the inequality cuts the greatest possible part of the polyhedral set 
of the continuous relaxation in this way. (See Exercise \ref{ujgy1}.)
To do so the absolute value of $d_{pj}-\mu_j$ must be small. Depending on its sign it can be 
either $f_j,$ or $f_j-1,$ where $f_j$ is the fractional part of $d_{pj}$, 
i.e. $f_j=d_{pj}-\lfloor d_{pj}\rfloor$. 

Assume that $f_j>0$. If $d_{pj}+\mu_j=f_j$ then the term 
\begin{eqnarray}\label{e95}
\frac{d_{0j}f_p}{f_j}
\end{eqnarray}
is present among the terms of the minimum of the lower branch. 
If $d_{pj}>0$ then it obviously is at least as great as the term
\begin{eqnarray*}
\frac{d_{0j}f_p}{d_{pj}}\koz,
\end{eqnarray*}
which appears in $P_{lp}$, i.e. in the right-hand side of (\ref{e75}). If $d_{pj}<0$
then there is a term
\begin{eqnarray}\label{e96}
\frac{d_{0j}(f_p-1)}{d_{pj}}
\end{eqnarray}
is in the right-hand side of (\ref{e76}) \koz. 
$d_{oj}$ is a common multiplier in the terms (\ref{e95}) and (\ref{e96}), therefore it can be disregarded
when the terms are compared. Under the assumption that $f_j\leq f_p$ it will be shown that 
\begin{eqnarray*}
\frac{f_p}{f_j}\geq\frac{f_p-1}{d_{pj}} \koz.
\end{eqnarray*}
As $d_{pj}$ is supposed to be negative the statement is equivalent to
\begin{eqnarray*}
d_{pj}f_p\leq (f_p-1)f_j \koz.
\end{eqnarray*}
Hence the inequality
\begin{eqnarray*}
\left(\left\lfloor d_{pj}\right\rfloor+f_j\right)f_p\leq f_pf_j-f_j
\end{eqnarray*}
must hold. It can be reduced to
\begin{eqnarray*}
\left\lfloor d_{pj}\right\rfloor f_p\leq -f_j \koz.
\end{eqnarray*}
It is true as $\left\lfloor d_{pj}\right\rfloor\leq -1$ and
\begin{eqnarray*}
-1\leq \frac{-f_j}{f_p}<0 \koz.
\end{eqnarray*} 

If $d_{pj}+\mu_j=f_j-1$ then according to (\ref{e76}) and (\ref{e89}) the term 
\begin{eqnarray*}
\frac{d_{0j}(1-f_j)^2}{f_p (1-f_j)}
\end{eqnarray*}
is present among the terms of the minimum of the upper branch.
In a similar way it can be shown that if $f_j > f_p$ then it is always at least as great as the term
\begin{eqnarray*}
\frac{d_{0j}(f_j-1)}{d_{pj}}
\end{eqnarray*}
which is present in the original formula (\ref{e76}).

Thus the rule of the choice of the integers $\mu_j$'s is
\begin{eqnarray}\label{e97}
\mu_j\,=\,\left\{\begin{array}{ll}\lfloor d_{pj}\rfloor & \hbox{if }f_j\leq f_p \koz,\\
\lceil d_{pj}\rceil & \hbox{if }f_j> f_p \koz \end{array}
\right.
\end{eqnarray}


\subsection{Branching strategies}
The B\&B frame doesn't have any restriction in the selection 
of the unfathomed node for the next branching in row 7 of \textsc{Branch-and-Bound}.
First two extreme strategies are discussed with pros and cons. 
The same considerations have to be taken in almost all
applications of B\&B. The third method is a compromise between the two extreme ones. Finally methods
more specific to the integer programming are discussed. 

\subsubsection{The LIFO Rule}
LIFO means ``Last-In-First-Out'', i.e. one of the branches generated in the last iteration is selected. A general
advantage of the rule is that the size of the enumeration tree and the size of the list ${\cal L}$ remains as
small as possible. In the case of the integer programming problem the creation of the branches is 
based on the integer values of the variables. Thus the number of the branches is at most 
$g_j+1$ if the branching variable is $x_j$. In the LIFO strategy the number of leaves is
strictly less then the number of the created branches on each level with the exemption of the deepest level. Hence
at any moment the enumeration tree may not have more than
\begin{eqnarray*}
\sum_{j=1}^n g_j + 1
\end{eqnarray*}
leaves.

The drawback of the strategy is that the flexibility of the enumeration is lost. The flexibility is one of the 
the main advantage of B\&B in solving pure integer problems. 

If the algorithm skips from one branch to another branch far away from the first one then it is necessary to
reconstruct the second branch including not only the branching restrictions on the variables but any other
information which is necessary to the bounding procedure. In the particular algorithm the procedure 
determining the bound is linear programming, more precisely a simplex method. If a new restriction 
as a linear constraint is added to
the problem which cuts off the previous optimal solution, then the simplex tableau looses the primal 
feasibility but the dual feasibility still holds. Thus a dual simplex method can immediately start without
carrying out a first phase. (The purpose of the first phase which itself is a complete optimization, is
to find a primal or dual feasible basic solution depending for primal or dual simplex method, respectively.)
If the B\&B method skips to another branch then to get the new bound by the simplex method will require
the execution of the first phase, too.

A further consideration concerns to the construction of feasible solutions. Generally speaking if good
feasible solutions are known in the early phase of the algorithm then the whole procedure can be accelerated.
In the current algorithm branching has a "constructive nature". It means that the value of the branching variable
becomes more restricted therefore it either becomes integer in the further optimal solutions in the 
subbranches of the branch, or it will be restricted further on. Thus it 
can be expected that sooner or later a complete integer solution is constructed
which might be feasible or infeasible. On the other hand if the algorithm skips frequently in the phase when
no feasible solution is known then it is very likely that any construction will be finished only later, i.e.
the acceleration will not take place, because of the lack of feasible solution.

If a LIFO type step is to be done and the branching variable is $x_p$ then the lower branch should be
chosen in step 7 of the algorithm, if 
\[z_r-P_{lp}\,\geq\,z_r-P_{up},\;\;\;\hbox{i.e.}\;\;\;P_{lp}\,\leq\,P_{up} \koz.\]

\subsubsection{The maximal bound}
The other extreme strategy is that the branch having the maximal bound is selected in each iteration.
The idea is simple and clear: it is the most promising branch therefore it worth to explore it.

Unfortunately the idea is not completely true. The bounds of the higher level branches are not accurate enough.
This phenomenon has been discussed during the analysis of the numerical example
in the subsection \ref{ss3} in relation (\ref{e15}). Thus a somewhat smaller upper bound in a lower branch 
can indicate a more promising branch.

The maximal bound strategy can lead to a very wide enumeration tree which may cause memory problems.
Moreover the construction of feasible solutions will be slow and therefore the relatively few solutions
will be enumerated implicitly, i.e. the number of steps will be high, i.e. the method will be slow.


\subsubsection{Fast bounds and estimates}
If the optimal solution of the relaxed problem is non-integer then it can have several fractional
components. All of them must be changed to be integer to obtain the optimal integer programming solution of the
branch. The change of the value of each currently fractional variable as a certain cost. The cost of the individual 
changes are estimated and summed up. The cost means the loss in the value of the objective function.
An adjusted value of the bound of the branch is obtained if the sum of the estimated individual costs
is subtracted from the current bound. It is important to emphasize that the adjusted value is not an upper or lower 
bound of the optimal value of integer programming solution of the branch but it is only a realistic estimation. 

There are two ways to obtain the estimation. The first one uses the crude values of the fractionality. Let 
$f_j$ and $f_j^{0}$ be the fractional part of variable $x_j$ in the current branch and in the relaxed 
problem of the original problem, respectively. Further on let $z_r$, $z_0$, and $\hat{z}$ be the optimal value
of the relaxed problem in the current branch, in the original problem, and the value of the best feasible
integer solution found so far. Generally speaking the measure of the fractionality of a real number $\alpha$
is that how far is $\alpha$ to the closest integer, i.e. 
\[\min\{\alpha-\lfloor\alpha\rfloor,\,\lceil\alpha\rceil-\alpha\} \koz.\]
Hence the estimate is
\begin{eqnarray}\label{e77}
z_r\,-\,(z_0-\hat{z})\frac{\sum_{j\in{\cal I}}\min\{f_j,1-f_j\}}{\sum_{j\in{\cal I}}\min\{f_j^0,1-f_j^0\}} \koz.
\end{eqnarray}
(\ref{e77}) takes into account the average inaccuracy of the bounds.

The fast bounds defined in (\ref{e75}) and (\ref{e76}) can be used also for the same purpose. They concern to
the correction of the fractionality of a single variable in the current branch. Hence the estimate
\begin{eqnarray*}%\label{e78}
z_r\,-\,\sum_{j\in{\cal I}}\min\{P_{lj},P_{uj}\}
\end{eqnarray*}
is a natural choice.


\subsubsection{A Rule based on depth, bound, and estimates}
The constraints defining the branches are integer valued lower and upper bounds on the branching variables. 
Thus one can expect that these new constraints force the majority of the branching variables to be integer.
It means that the integrality of the optimal solution of the relaxed problem improves with the depth of
the branch.
Thus it is possible to connect the last two rules on the following way. The current bound is abandoned and
the algorithm selects the best bound is the improvement based on estimates is above a certain threshold.


\subsection{The selection of the branching variable}
In selecting the branching variable again both the fractional part of the non-integer variables and the
fast bounds have critical role. A further factor can be the information obtained from the user.

\subsubsection{Selection based on the fractional part}
The most significant change can be expected from that variable which is farthest from integers as the cuts
defining the two new branches cut the most. As the measure of fractionality is 
$\min\{f_j,1-f_j\}$ the rule suggest to choose the branching variable $x_p$ as
\[p\,=\,\hbox{argmax}\{\min\{f_j,1-f_j\}\mid j\in{\cal I}\} \koz\]

\subsubsection{Selection based on fast bounds}
Upper bounds are
\[z_r-P_{lp}\;\;\;\hbox{and}\;\;\;z_r-P_{up}\]
in the lower and upper branches of branch $r$ if the branching variable is $x_p$.

Here are five possible selection criteria:
\begin{eqnarray}\label{e79}
\max_{p:}\max\{z_r-P_{lp},\,z_r-P_{up}\}\\ \label{e80} \max_{p:}\min\{z_r-P_{lp},\,z_r-P_{up}\}\\ 
\label{e81} \min_{p:}\max\{z_r-P_{lp},\,z_r-P_{up}\}\\
\label{e82} \min_{p:}\min\{z_r-P_{lp},\,z_r-P_{up}\}\\ \label{e83} \max_{p:}\{\mid P_{lp}\,-\,P_{up}\mid\} \koz.
\end{eqnarray}
Which one can be offered for a B\&B algorithm?

Notice that 
\[\max\{z_r-P_{lp},\,z_r-P_{up}\}\]
is a correct upper bound of branch $r$  as it has been mentioned earlier. Thus (\ref{e79}) selects according to
the most inaccurate upper bound. It is obviously not good. (\ref{e81}) makes just the opposite it selects the
variable giving the most accurate bound. On the other hand 
\begin{eqnarray}\label{e84}
\min\{z_r-P_{lp},\,z_r-P_{up}\}
\end{eqnarray}
is the upper bound in the worse one of the two subbranches. The interest of the algorithm is that 
it will be fathomed without explicit investigation, i.e. the bound
of this subbranch will be less than the objective function value of an integer feasible solution.
Thus it is good if (\ref{e84}) is as small as possible. Hence (\ref{e82}) is a good strategy and (\ref{e80})
is not. Finally, (\ref{e83}) tries to separate the good and low quality feasible solutions. The conclusion is
that (\ref{e82}) and (\ref{e83}) are the two best ones and (\ref{e81}) is still applicable, but (\ref{e79})
and (\ref{e80}) must be avoided.

\subsubsection{Priority rule}
Assume that the numerical problem (\ref{e44})-(\ref{e48}) is the model of an industrial problem. Then the final
user is the manager and/or expert who must apply the decisions coded into the optimal solution. The expert may
know that which factors (decisions) are the most critical ones from the point of view of the managerial 
problem and the industrial system. The variables belonging to these factors may have a special importance.
Therefore it has sense if the user may define a priority order of variables. Then the first non-integer variable
of the order can be selected as branching variable.

\subsection{The numerical example is revisited}
The solution of the problem
$$\begin{array}{cccrrrrr}
\max & x_0 & = & 2x_1 & + & x_2\\ &&& 3x_1 & - & 5x_2 & \leq & 0\\
 &&& 3x_1 & + & 5x_2 & \leq & 15\\ &&&
\multicolumn{5}{c}{x_1,\,x_2\,\geq\,0}\\ &&&
\multicolumn{5}{c}{x_1,\,x_2\,\hbox{is integer} \koz.}
\end{array}
\eqno(\ref{e49})
$$
has been analyzed from geometric point of view in subsection \ref{ss4}. Now the above-mentioned methods will be
applied and the same course of solution will be obtained.

After introducing the slack variables $x_3$ and $x_4$ the (primal) simplex method gives the equivalent form (\ref{e51})
of the equations and the objective function:
$$\begin{array}{cccrrrrrrrrr}
\max & x_0 & = & 0x_1 & + & 0x_2 & - & \frac{7}{30}x_3 & - & \frac{13}{30}x_4 & + & 
\frac{13}{2}\\ \;\\ 
&&& x_1 & + & 0x_2 & + & \frac{1}{6}x_3 & + & \frac{1}{6}x_4 & = & \frac{5}{2}\\ \;\\
 &&& 0x_1 & + & x_2 & - & \frac{1}{10}x_3 & + & \frac{1}{10}x_4 & =  & \frac{3}{2}\\ &&&
\multicolumn{5}{c}{x_1,\,x_2\,x_3,\,x_4\,\geq\,0\koz.}
\end{array}
\eqno(\ref{e51})
$$ 
Hence it is clear that the solution $x_1=\frac{5}{2}$ and $x_2=\frac{3}{2}$. (\ref{e51}) gives the following optimal
{\em dual} simplex tableaux:
\begin{eqnarray*}
\begin{array}{rccc}
&& -x_3 & -x_4\\ x_0 & 13/2 & 7/30 & 13/30\\ x_1 & 5/2 & 1/6 & 1/6\\
x_2 & 3/2 & -1/10 & 1/10\\ x_3 & 0 & -1 & 0\\ x_4 & 0 & 0 & -1 
\end{array} \koz .
\end{eqnarray*}
The first two branches were defined by the inequalities $x_1\leq 2$ and $x_1\geq 3$. 
The second one is an empty branch.
The algebraic evidence of this fact is that there is no negative element in the row of $x_1$, thus it is not
possible to find a pivot element for the dual simplex method after introducing the cut. 
Now it will be shown in a detailed
way. Let $s$ be the appropriate slack variable, i.e. the cut introduced in the form
\[x_1\,-\,s\,=\,3,\;\;\;s\,\geq\,0 \koz.\]
The new variable $s$ must be expressed by the non-basic variables, i.e. by $x_3$ and $x_4$:
\[3\,=\,x_1\,-\,s\,=\,\frac{5}{2}\,-\,\frac{1}{6}x_3\,-\,\frac{1}{6}x_4\,-\,s \koz.\]
Hence
\[s\,=\,-\frac{1}{2}\,+\,\frac{1}{6}(-x_3)\,+\,\frac{1}{6}(-x_4) \koz.\]
When this row is added to the dual simplex tableaux, it is the only row having a negative constant term, but there is
no negative coefficient of any non-basic variable proving that the problem is infeasible. Notice that the sign of a
coefficient is an immediate consequence of the sign of the coefficient in the row of $x_1$, i.e. it is not necessary
to carry out the calculation of the row of $s$ and it is possible to conclude immediately that the branch is empty.

The fractional part $f_1$ equals $\frac{1}{2}$. Hence the fast bound (\ref{e75}) of the lower branch defined by $x_1\leq 2$ is
\begin{eqnarray*}
\frac{1}{2}\min\left\{\frac{\frac{7}{30}}{\frac{1}{6}},\,\frac{\frac{13}{30}}{\frac{1}{6}}\right\}\,=\,\frac{7}{10} \koz.
\end{eqnarray*}
It means that the fast upper bound in the branch is 13/2-7/10=5.8. The bound can be rounded down to 5 as the objective function
is integer valued.

Let $x_5$ be the slack variable of the cut $x_1\leq 2$, i.e. $x_1\,+\,x_5\,=\,2$. Hence
\begin{eqnarray*}
x_5\,=\,\frac{1}{2}\,-\,\left(-\frac{1}{6}\right)(-x_3)\,-\,\left(-\frac{1}{6}\right)(-x_4) \koz.
\end{eqnarray*}
If it is added to the simplex tableaux then the pivot element is $d_{53}$. After the first pivot step the tableaux becomes
optimal. It is 
\begin{eqnarray}\label{e98}
\begin{array}{rrrr}
&& -x_5 & -x_4\\ x_0 & 29/5 & 7/5  &  1/5 \\ x_1 &   2 & 1   & 0  \\
x_2 & 9/5 & -3/5  & 1/5 \\ x_3 & 3 & -6 & 1\\ x_4 & 0 & 0 & -1\\
x_5 & 0 & -1 & 0\\
\end{array} \koz.
\end{eqnarray}
Notice that the optimal value is 5.8, i.e. exactly the same what was provided by the fast bound. The reason is that
the fast bound gives the value of the objective function after the first pivot step. In the current case the first pivot
step immediately produced the optimal solution of the relaxed problem.

$x_2$ is the only variable having non-integer value in simplex tableaux. Thus the branching must be done according to $x_2$.
The two new cuts defining the branches are $x_2\leq 1$ and $x_2\geq 2$. There are both positive and negative coefficients
in the row of $x_2$, thus both the lower and upper branches exist. Moreover
\[P_{l2}\;=\;\frac{4}{5}\times\frac{1/5}{1/5}\,=\,\frac{4}{5},\;\;\;
P_{u2}\;=\;\frac{1}{5}\times\frac{7/5}{3/5}\,=\,\frac{7}{15} \koz.\]
Thus the continuous upper bound is higher on the upper branch, therefore it is selected first for further branching.

The constraint
\[x_2\,-\,x_6\,=\,2,\;\;\;x_6\,\geq\,0\]
are added to the problem. By using the current simplex tableaux the equation
\begin{eqnarray*}
x_6\,=\,-\frac{1}{5}\,-\,\frac{3}{5}(-x_5)\,+\,\frac{1}{5}(-x_4)
\end{eqnarray*}
is obtained. It becomes the last row of the simplex tableaux. In the first pivoting step $x_6$ enters the basis and $x_5$
leaves it. The first tableaux is immediately optimal and it is
\begin{eqnarray*}
\begin{array}{rccc}
&& -x_6 & -x_4\\ x_0 & 16/3 & 7/3  &  2/3 \\ x_1 & 5/3 & 5/3 & 1/3\\
x_2 & 2   & -1    & 0   \\ x_3 & 5 & -10&-1\\ x_4 & 0 & 0 & -1\\
x_5 &1/3&-5/3&-1/3\\ x_6 & 0 & -1 & 0
\end{array} \koz
\end{eqnarray*}
Here both $x_1$ and $x_5$ are integer variables having non-integer values. Thus branching is possible according to both of them.
Notice that the upper branch is empty in the case of $x_1$, while the lower branch of $x_5$ is empty as well.
$x_1$ is selected for branching as it is the variable of the original problem. Now
\begin{eqnarray*}
P_{l1}\,=\,\frac{2}{3}\min\left\{\frac{7/3}{5/3},\,\frac{2/3}{1/3}\right\}\,=\,\frac{14}{15} \koz.
\end{eqnarray*}
On the other hand the bound can be improved in accordance with (\ref{e97}) as $d_{16}>1$, 
i.e. the coefficient of $-x_6$ may be
$2/3$ instead of $5/3$. It means that the inequality
\begin{eqnarray*}
x_1+x_6\leq 1
\end{eqnarray*}
is claimed instead of
\begin{eqnarray*}
x_1\leq 1 \koz.
\end{eqnarray*}
It is transferred to the form
\begin{eqnarray*}
x_1+x_6+x_7 = 1 \koz.
\end{eqnarray*}
Hence
\begin{eqnarray*}
x_7 = -\frac{2}{3}-\frac{2}{3}(-x_6)-\frac{1}{3}(-x_4) \koz.
\end{eqnarray*}
The improved fast bound is obtained from
\begin{eqnarray*}
P_{l1}^{'}\,=\,\frac{2}{3}\min\left\{\frac{7}{2},\,2\right\}\,=\,\frac{4}{3} \koz.
\end{eqnarray*}
It means that the objective function can not be greater than 4.
After the first pivoting the simplex tableau becomes
\begin{eqnarray*}
\begin{array}{rcrr}
&& -x_6 & -x_7\\ x_0 & 4  & 1 & 2\\ x_1 & 1   & 1   & 1  \\
x_2 & 2   & -1    & 0   \\ x_3 & 7 & -8 &-3\\ x_4 & 2 & 2 & -3\\
x_5 &1  &-1  &-1  \\ x_6 & 0 & -1 & 0\\ x_7 & 0 & 0 & -1
\end{array} 
\end{eqnarray*}
giving the feasible solution $x_1=1$ and $x_2=2$ with objective function value 4.

There is only one unfathomed branch which is to be generated from tableaux (\ref{e98}) by the constraint $x_2\leq 1$.
Let $x_8$ be the slack variable. Then the equation
\begin{eqnarray*}
1=x_2+x_8=\frac{9}{5}-\frac{3}{5}(-x_5)+\frac{1}{5}(-x_4)+x_8
\end{eqnarray*}
gives the cut
\begin{eqnarray*}
x_8=-\frac{4}{5}+\frac{3}{5}(-x_5)-\frac{1}{5}(-x_4)
\end{eqnarray*}
to be added to the tableaux. After two pivoting steps the optimal solution is
\begin{eqnarray*}
\begin{array}{rrrr}
&& -x_3 & -x_6\\ x_0 & 13/3 & 2/3  & 13/3 \\ x_1 & 5/3 & 1/3 & 5/3\\
x_2 & 1   &  0    & 1   \\ x_3 & 5 & -1 & 0\\ x_4 & 5 & -1&-10\\
x_5 &1/3&-1/3&-5/3\\ x_6 & 0 &  0 & -1
\end{array} \koz
\end{eqnarray*}
Although the optimal solution is not integer, the branch is fathomed as the upper bound is under 5, i.e. the branch can not contain 
a feasible solution better than the current best known integer solution. Thus the method is finished.

\begin{gyak}
\ujgyak\label{ujgy1} 
Show that the rule of the choice of the integers $\mu_j$ (\ref{e97}) is not necessarily optimal from the
point of view of the object function. ({\em Hint.} Assume that variable $x_j$ enters into the basis
in the first pivoting.\gyakindex{pivoting} Compare the changes in the objective function value 
if its coefficient is $-f_j$ and $f_j-1$, respectively.)
\end{gyak}


\section{On the enumeration tree}\label{s2}
One critical point of B\&B is the storing of the enumeration tree. When a branch is fathomed then even some of
its ancestors can become completely fathomed provided that the current branch was the last unfathomed subbranch
of the ancestors. The ancestors are stored also otherwise it is not possible to restore the successor.
As B\&B uses the enumeration tree on a flexible way, it can be necessary to store a large amount of information
on branches. It can causes memory problems. On the other hand it would be too expensive 
from the point of view of calculations to check the ancestors 
every time if a branch becomes fathomed. This section gives some ideas how to make a trade-off.

The first thing is to decide is that which data are describing a branch. There are two options. 
The first one is that all necessary informations are stored for each branch. It includes 
all the branching defining constraints. In that case the same constraint is stored many times, 
because a branch on a higher level may have many subbranches. As matter of
fact the number of branches is very high in the case of large scale problems, thus the memory required by this
solution is very high.

The other option is that only those informations are stored which are necessary to the complete reconstruction of
the branch. These ones are
\begin{itemize}
\item the parent branch, i.e. the branch from which it was generated directly,
\item the bound of the objective function on the branch,
\item the index of the branching variable,
\item the branch defining constraint of the branching variable.
\end{itemize}
For technical reasons three other attributes are used as well:
\begin{itemize}
\item a Boolean variable showing if the branch has been decomposed into subbranches,
\item another Boolean variable showing if any unfathomed subbranch of the branch exists,
\item and a pointer to the next element in the list of branches.
\end{itemize}
Thus a branch can be described by a {\bf record} as follows:

\begin{alg}
\' \key{record}  Branch\\ 
\' \key{begin}\\ 
\' \> Parent \> \> \> \> \>: Branch;\\
\' \> Bound \> \> \> \> \>: \key{integer};\\  
\' \> Variable \> \> \> \> \>: \key{integer};\\
\' \> Value \> \> \> \> \>: \key{integer};\\ 
\' \> Decomposition \> \> \> \> \>: \key{Boolean};\\
\' \> Descendant \> \> \> \> \>: \key{Boolean};\\ 
\' \> suc \>  \> \> \> \>: Branch\\
\' \key{end};
\end{alg}

The value of the Parent attribute is {\bf none} if and only if the branch is the initial branch, i.e.
the complete problem. It is the root of the B\&B tree.
The reconstruction of the constraints defining the particular branch is the
simplest if it is supposed that the branches are defined by the fixing of a free variable. Assume that
Node is a variable of type Branch. At the beginning its value is the branch to be reconstructed.
Then the algorithm of the reconstruction is as follows.

\begin{alg}{Branch-Reconstruction}\inddef{\textsc{Branch-Reconstruction}}
1 \' \key{while} \= Node $\neq$ \key{none} \\ 
2 \'             \> \key{do} \= $x$[Node.Variable] $\leftarrow$ Node.Value;\\
3 \'             \>          \> $\ldots$\\ 
4 \'             \>          \> Node $\leftarrow$ Node.Parent;\\ 
5 \' \key{return} Node
\end{alg}

The value of a previously fixed variable is set to the appropriate value in row 2. Further operations are 
possible (row 4). Node becomes its own parent branch in row 5. If it is {\bf none} then the root is passed
and all fixings are done. 

Sometimes it is necessary to execute some operations on all elements of the list ${\cal L}$. The suc attribute
of the branches point to the next element of the list. The last element has no next element, therefore the value
of suc is {\bf none} in this case. The procedure of changing all elements is somewhat similar to the
\textsc{Branch Reconstruction} procedure. The head of the list ${\cal L}$ is Tree, i.e. the first element of the 
list is Tree.suc.

\begin{alg}{B\&B-List}\inddef{\textsc{B\&B-List}}
1 \' Node $\leftarrow$ Tree.suc\\ 
2 \' \key{while} \= Node$\neq$\key{none} \\ 
3 \'             \> $\ldots$\\ 
4 \'             \> Node $\leftarrow$ Node.suc\\ 
5 \' \key{return} Node
\end{alg}

The loop runs until there is no next element. The necessary operations are executed in row 4. 
The variable Node becomes the 
next element of the list in row 5. To insert a new branch into the list is easy. Assume that it is NewNode of
type Branch and it is to be inserted after Node which is in the list. Then the necessary two commands are: \\

NewNode.suc $\leftarrow$ Node.suc\\ 
\hspace*{15mm}Node.suc $\leftarrow$ NewNode \\

If the branches are not stored as objects but they are described in long arrays then the use of attribute suc is
superflous and instead of the procedure \textsc{B\&B List} a \key{for} loop can be applied.

The greatest technical problem of B\&B from computer science point of view is memory management. Because branches are
created in enormous large quantity the fathomed branches must be deleted from the list time to time and the memory
occupied by them must be freed. It is a kind of garbage collection. It can be done in three main steps. 
In the first one value {\bf false} is assigned to the attribute Descendant of all elements of the list. 
In the second main step an attribute Descendant is changed to {\bf true} if and only if 
the branch has unfathomed descendant(s). In the third step the unnecessary branches are deleted. 
It is assumed that there is a procedure Out which gets the branch
to be deleted as a parameter and deletes it and frees the part of the memory.

\begin{algN}{Garbage-Collection}\inddef{\textsc{Garbage-Collection}}
 1 \' Node $\leftarrow$ Tree.suc\\
 2 \' \key{while} \= Node $\neq$ \key{none} \\
 3 \'             \> Node.Descendant $\leftarrow$ \textsc{False}\\
 4 \'             \> Node $\leftarrow$ Node.suc\\
 5 \' Node $\leftarrow$ Tree.suc\\
 6 \' \key{while} \= Node $\neq$ \key{none}\\
 7 \'             \> \key{do} \key{if not} Node.Decomposition \key{ and} Node.Bound > $\hat{z}$\\
 8 \'  \> \key{ then} Pont $\leftarrow$ Node.Parent\\
 9 \'  \> \> \key{while} Pont $\neq$\key{ none do}\\
10 \'  \> \> \>   Pont.Descendant $\leftarrow$ \textsc{True}\\
11 \'  \> \> \> Pont $\leftarrow$ Pont.Parent \\
12 \'  \> Node $\leftarrow$ Node.suc \\
13 \' Node $\leftarrow$ Tree.suc\\
14 \' \key{ while} Node $\neq$\key{ none do}\\
15 \' \> Pont $\leftarrow$ Node.suc\\
16 \' \> \key{if} (\key{not} Node.Descendant \key{ and} Node.Decomposition) \key{ or} Node.Bound $\leq \hat{z}$\\
17 \' \> \key{then} Out(Node)\\
18 \' \>  Node $\leftarrow$ Pont\\
19 \' \key{return} ???
\end{algN}


\section{The use of information obtained from other sources}\label{s1}
The method can be sped up by using information provided by further algorithmic tools.

\subsection{Application of heuristic methods}
The aim of the application of heuristics methods is to obtain feasible solutions. From theoretical
point of view to decide if any feasible solution exists is NP-complete as well. On the other hand
heuristics can produce feasible solutions in the case of the majority of the numerical problems.
The methods to be applied depend on the nature of the problem in question, i.e. pure binary,
bounded integer, mixed integer problems may require different methods. For example for pure integer
problems local search and Lagrange multipliers can work well. Lagrange multipliers also provide
upper bound (in the case of maximization) of the optimal value. 

If a feasible solution is known then it is immediately possible to disregard branches based on their bounds.
See row 15 of algorithm \textsc{Branch and Bound}. There the branches having not good enough bounds are 
automatically eliminated. In the case of pure binary problem an explicit objective function constraint can give 
a lot of consequences as well.

\subsection{Preprocessing}\label{ss6}
Preprocessing means to obtain information on variables and
constraints based on algebraic constraints and integrality.

For example if the two constraints of problem (\ref{e49}) are summed up then the inequality
\begin{eqnarray*}
6x_1 \leq 15
\end{eqnarray*}
is obtained implying that $x_1\leq 2$.

Let 
\begin{eqnarray}\label{e99}
g_i(x)\leq b_i
\end{eqnarray}
be one of the constraints of problem (\ref{e17})-(\ref{e19}). 
Many tests can be based on the following two easy observations:
\begin{enumerate}
\item {\em If the maximal value of the left-hand side of (\ref{e99}) of $x\in{\cal X}$ is  not greater than the 
right-hand side of (\ref{e99}) then the constraint is redundant.
\item If the minimal value of the left-hand side of (\ref{e99}) if $x\in{\cal X}$ is  greater than the 
right-hand side of (\ref{e99}) then it is not possible to satisfy the constraint, i.e. the problem 
(\ref{e17})-(\ref{e19}) has no feasible solution.}
\end{enumerate}
If under some further restriction the second observation is true then the restriction in question can be
excluded. A typical example is that certain variables are supposed to have maximal/minimal possible value.
In this way it is possible to fix a variable or decrease its range.

Lagrange relaxation can be used to fix some variables, too. 
Assume that the optimal value of Problem (\ref{e26}) and  (\ref{e19}) is $\nu(L(\lambda\mid x_j=\delta))$
under the further condition that $x_j$ must take the value $\delta$. If $\hat{z}$ 
is the objective function value
of a known feasible solution and $\hat{z}>\nu(L(\lambda\mid x_j=\delta))$ 
then $x_j$ can not take value $\delta$.
Further methods are assuming that the LP relaxation
of the problem is solved and based on optimal dual prices try to fix the values of variables. 



\section{Branch and Cut}
\ki{Branch and Cut}\inddef{Branch and Cut} (B\&C) in the simplest case is a B\&B method 
such that the a certain kind of information is collected
and used during the whole course of the algorithm. The theoretical background is based on the notion of
{\em integer hull}\index{integer hull}

\begin{defi}\label{d4}
Let 
\begin{eqnarray*}
{\cal P}\,=\,\{{\bf x}\mid {\bf Ax}\leq{\bf b}\}
\end{eqnarray*}
be a polyhedral set where {\bf A} is an $m\times n$ matrix, {\bf x} and {\bf b} are $n$ and $m$ dimensional vectors.
All elements of {\bf A} and {\bf b} are rationals. The convex hull of the integer points of {\cal P} is called the
{\em integer hull} of ${\cal P}$, i.e. it is the set
\begin{eqnarray*}
\hbox{{\em conv}}({\cal P}\cap Z^n) \koz.
\end{eqnarray*}
\end{defi}

The integer hull of the polyhedral set of problem (\ref{e49}) is the convex hull of the points (0,0),
(0,3), (1,2), and (1,1) as it can be seen on Figure 24.2. Thus the description of the integer hull 
as a polyhedral set is the inequality system:
\begin{eqnarray*}
x_1\geq 0,\;\;\;\;x_1+x_2\leq 3,\;\;\;\;x_1\leq 1,\;\;\;\;x_1-x_2\leq 0 \koz.
\end{eqnarray*} 

Under the conditions of the definition the integer hull is a polyhedral set, too. It is a non-trivial statement
and in the case of irrational coefficients it can be not true. If the integer hull is known, i.e. a set of
linear inequalities defining exactly the integer hull polyhedral set is known, then the integer programming
problem can be reduced to a linear programming problem. 
Thus problem (\ref{e49}) is equivalent to the problem
\begin{eqnarray}\label{e100}
\begin{array}{cccrrrrr}
\max & x_0 & = & 2x_1 & + & x_2\\ &&& x_1 &&& \geq & 0\\
 &&& x_1 & + & x_2 & \leq & 3\\ &&& x_1 &&& \leq & 1\\ &&&
x_1 & - & x_2 & \leq & 0 \koz.
\end{array}
\end{eqnarray}

As the linear programming problem easier to solve
than the integer programming problem, one may think that it worth to carry out this reduction. It is not
completely true. First of all the number of the linear constraint can be extremely high. 
Thus generating all constraints of the integer hull can be more difficult than the solution of the
original problem. Further on the constraints 
determining the shape of the integer hull on the side opposite to the optimal solution are not contributing
to the finding of the optimal solution. For example the optimal solution of (\ref{e100}) will not change
if the first constraint is deleted and it is allowed both $x_1$ and $x_2$ may take negative values.

On the other hand the first general integer programming method is the cutting plane method of Gomory.
Its main tool is the cut which is based on the observation that
possible to determine linear inequalities such that they cut the 
non-integer optimal solution of the current LP relaxation, but they do not cut any integer feasible solution.
A systematic generation of cuts leads to a finite algorithm which finds an optimal solution and proves
its optimality if optimal solution exist, otherwise it proves the non-existence of the optimal solution.
From geometrical point of view
the result of the introducing of the cuts is that the shape of the polyhedral set of the last LP
relaxation is very similar to the integer hull {\em in the neighborhood of the optimal solution}.

There is the generalization of Gomory's cut called Chv\'atal (or Chv\'atal-Gomory) cut. If the two
inequalities of (\ref{e49}) are summed such that both have weight $\frac{1}{6}$ then the constraint
\begin{eqnarray*}
x_1 \leq 2.5
\end{eqnarray*}
is obtained. As $x_1$ must be integer the inequality
\begin{eqnarray}\label{e101}
x_1 \leq 2
\end{eqnarray}
follows immediately. It is not an algebraic consequence of the original constraints. To obtain it
the information of the integrality of the variables had to be used. But the method can be continued.
If (\ref{e101}) has weight $\frac{2}{5}$ and the second constraint of (\ref{e49}) has weight 
$\frac{1}{5}$ then
\begin{eqnarray*}
x_1 + x_2 \leq 3.8
\end{eqnarray*}
is obtained implying
\begin{eqnarray*}
x_1 + x_2 \leq 3 \koz.
\end{eqnarray*}
If the last inequality has weight $\frac{5}{8}$ and the first inequality of (\ref{e49}) has weight
$\frac{1}{8}$ then the result is
\begin{eqnarray*}
x_1 \leq \frac{15}{8}
\end{eqnarray*}
implying
\begin{eqnarray*}
x_1 \leq 1.
\end{eqnarray*}
Finally the integer hull is obtained. 
In general the idea is as follows. Assume that a polyhedral set is defined by the linear
inequality system
\begin{eqnarray}\label{e102}
{\bf Ax} \leq {\bf b} \koz.
\end{eqnarray}
Let ${\bf y}\geq{\b 0}$ be a vector such that ${\bf A}^T{\bf y}$ is an integer vector and ${\bf y}^T{\bf b}$ 
is a noninteger value. Then 
\begin{eqnarray*}
{\bf y}^T{\bf Ax}\;\leq\;\lfloor{\bf y}^T{\bf b}\rfloor
\end{eqnarray*}
is a valid cut, i.e. all integer points of the polyhedral set satisfy it.
As a matter of fact
it can be proven that a systematic application of the method creates a complete description of 
the integer hull after finite many steps.\index{Gomory cut}\index{Traveling Salesperson Problem}

The example shows that Gomory and Chv\'atal cuts can help to solve a problem. On the other hand they
can be incorporated in a B\&B frame easily. But in the very general case it is hopeless to generate
all effective cuts of this type. 

The situation is significantly different in the case of many
combinatorial problems. There are many theoretical results known on the type of the facet defining
constraints of special polyhedral sets. Here only one example is discussed. It is the Traveling 
Salesperson Problem (TSP). A salesman must visit some cities and at the end of the tour he must
return to his home city. The problem is to find a tour with minimal possible length. TSP has many
applications including cases when the "cities" are products or other objects and the ``distance''
among them doesn't satisfy the properties of the geometric distances, i.e. symmetry and triangle
inequality may be violated. 

The first exact mathematical formulation of the problem is the so-called Dantzig-Fulkerson-Johnson (DFJ) 
\nevindex{Dantzig, George Bernard (1914--2005)}\nevindex{Fulkerson, Delbert Ray}\nevindex{Johnson, S. M.}
model. DFJ is still the basis of the numerical solutions. Assume that the number of cities is
$n$. Let $d_{ij}$ the distance of the route from city $i$ to city $j$ $(1\leq i,j\leq n,\,i\neq j)$.
DFJ uses the variables $x_{ij}$ such that
\begin{eqnarray*}
x_{ij}\,=\,\left\{\begin{array}{ll}1 & \hbox{if the salesman travel from city }i\hbox{ to city }j\\
0 & \hbox{otherwise}\end{array}\right.
\end{eqnarray*}
The objective function is the minimization on the total travel length:
\begin{eqnarray}\label{e103}
\min\sum_{i=1}^n\sum_{i\neq j}d_{ij}x_{ij} \koz.
\end{eqnarray}
The set of the constraints consists of three parts. The meaning of the first part is that the
salesman must travel from each city to another city exactly once:
\begin{eqnarray}\label{e104}
\sum_{j=1,j\neq i}^n x_{ij}\,=\,1\;\;\;i=1,\ldots,n \koz.
\end{eqnarray}
The second part is very similar. It claims that the salesman must arrive to each city
from somewhere else again exactly once:
\begin{eqnarray}\label{e105}
\sum_{i=1,i\neq j}^n x_{ij}\,=\,1\;\;\;j=1,\ldots,n \koz.
\end{eqnarray}
Constraints (\ref{e104}) and (\ref{e105}) are the constraints of an assignment problem. Taking 
into account that the variables must be binary Problem (\ref{e103})-(\ref{e105}) is really an
assignment problem. They don't exclude solutions consisting of several smaller tours. For example
if $n=6$ and $x_{12}=x_{23}=x_{31}=1$ and $x_{45}=x_{56}=x_{64}=1$ then all other variables must be zero. 
The solution consists of two smaller tours. The first one visits only cities 1, 2, and 3, the second
one goes through the cities 4, 5, and 6. The small tours are called {\em subtours} in the language 
of the theory of TSP.
\index{assignment problem}\index{subtour}\index{subtour elimination constraints}

Thus further constraints are needed which excludes the subtours. They are called
{\em subtour elimination constraints}. There are two kinds of logic how the subtours can be excluded.
The first one claims that in any subset of the cities which has at least two elements but not the
complete set of the cities the number of travels must be less than the number of elements of the set.
The logic can be formalized as follows:
\begin{eqnarray}\label{e106}
\forall\,{\cal S}\subset\{1,2,\ldots,n\},\,1\leq|{\cal S}|\leq n-1:\;\;
\sum_{i\in{\cal S}}\sum_{j\in{\cal S}j\neq i} x_{ij}\,\leq\,|{\cal S}| \koz.
\end{eqnarray}
The other logic claims that the salesman must leave all such sets. Let 
$\bar{\cal S}=\{1,2,\ldots,n\}\setminus{\cal S}$. Then the subtour elimination constraints are the
inequalities
\begin{eqnarray}\label{e107}
\forall\,{\cal S}\subset\{1,2,\ldots,n\},\,1\leq|{\cal S}|\leq n-1:\;\;
\sum_{i\in{\cal S}}\sum_{j\in\bar{\cal S}} x_{ij}\,\geq\,1 \koz.
\end{eqnarray}
The numbers of the two types of constraints are equal and exponential. Although the constraints
(\ref{e104})--(\ref{e106}) or (\ref{e104}), (\ref{e105}), and (\ref{e107}) are satisfied by 
only binary vectors being characteristic vectors of complete tours but the polyhedral set of
the LP relaxation is strictly larger than the integer hull.

On the other hand
it is clear that it is not possible to claim all of the subtour elimination constraints in the
real practice. What can be done? It is possible to claim only the violated once. The difficulty is 
that the optimal solution of the LP relaxation is a fractional vector in most of the cases and
that subtour elimination constraint must be found which is violated by the fractional solution
provided that such constraint exists as the subtour elimination constraints are necessary to the
description of the integer hull but further constraints are needed, too. Thus it is possible that
there is no violated subtour elimination constraint but the optimal solution of the LP relaxation
is still fractional.

To find a violated subtour elimination constraint is equivalent to the finding of the absolute
minimal cut in the graph which has only the edges having positive weights in the optimal solution
of the relaxed problem. If the value of the absolute minimal cut is less than 1 in the directed case 
or less than 2 in the non-directed case then such a violated constraint exists. The reason can be
explained based on the second logic of the constraints. If the condition is satisfied then the
current solution doesn't leaves at least one of the two sets of the cut in enough number. There are
many effective methods to find the absolute minimal cut.\index{minimal cut}\index{absolute minimal cut}

A general frame of the numerical solution of the TSP is the following. In a B\&B frame the calculation 
of the lower bound is repeated until a new violated subtour elimination constraint is obtained,
that is the new inequality is
added to the relaxed problem and the LP optimization is carried out again. If all subtour elimination
constraints are satisfied and the optimal solution of the relaxed problem is still non-integer then
branching is made according to a fractional valued variable.

The frame is rather general. The violated constraint cuts the previous optimal solution and
reoptimization is needed. Gomory cuts do the same for the general integer programming problem. In the case of
other combinatorial problems special cuts may work if the description of the integer hull is known.
\index{Gomory cut}

Thus the general idea of B\&C is that a cut is generated until it can be found and the improvement in
the lower bound is great enough. Otherwise branching is made by a non-integer variable. If the cut
generation is made only at the root of the enumeration tree then the name of the method is
{\em Cut and Branch} (C\&B). If a cut is generated in a branch then it is locally valid in that branch and
in its successors. The cuts generated at the root are valid globally, i.e. in all branches. In some
cases, e.e. in binary optimization, it is possible to modify it such that it is valid in the original
problem, too.\index{Cut and Branch}

For practical reasons the type of the generated cut can be restricted. It is the case in TSP as the 
subtour elimination constraints can be found relatively easily.

\section{Branch and Price}
The \ki{Branch and Price method}\inddef{Branch and Price method} is the dual of B\&C in a certain sense. 
If a problem has very large number 
of variables then it is often possible not to work explicitely with all of them but generate only
those which may enter the basis of the LP relaxation. This is column generation and is based on the
current values of the dual variables called shadow prices. Similarly to B\&C the type of the
generated columns is restricted. If it is not possible to find a new column then branching is made.
\index{shadow price}

\begin{fld}
\ujfld{Continuous Knapsack Problem\felindex{Continuous Knapsack Problem}}
{Prove Theorem \ref{t1}. ({\em Hint.} Let ${\bf x}$ be a feasible solution such that
there are two indices, say $j$ and $k$, such that $1\leq j<k\leq n$ and $x_j<1$, and
$x_k>0$. Show that the solution can be improved.)}
\ujfld{TSP's relaxation}
{Decide if the Assignment Problem\felindex{Assignment Problem} can be a relaxation of the Traveling Salesperson
Problem\felindex{Traveling Salesperson Problem} in the sense of definition \ref{d2}. 
Explain your solution regardless that your answer is YES or NO.}
\ujfld{Infeasibility test\felindex{infeasibility test}} 
{Based on the the second observation of Subsection \ref{ss6} develop a test for the
infeasibility of a linear constraint of binary variables.}
\ujfld{Mandatory fixing\felindex{mandatory fixing test}} 
{Based on the previous problem develop a test for the
mandatory fixing of binary variables satisfying a linear constraint.}
\end{fld}


\begin{fejmegj}
The principle of
B\&B first appears in \cite{landdoig60}. It solves problems with bounded integer variables. The fast 
bounds were introduced in \cite{bealesmall65} and \cite{tomlin71}. A good summary of the bounds is
\cite{forrestetal74}. To the best knowledge of the author of this chapter the improvement of the
fast bounds appeared first in \cite{vizvari90}.

B\&B can be used as an approximation scheme, too. In that case a branch can be deleted even in the case
if its bound is not greater than the objective function value of the current best solution plus an allowed
error. \cite{ibaraki76} showed that there are classes such that the approximate method requires more
computation than to solve the problem optimally. B\&B is very suitable for parallel processing. 
This issue is discussed in \cite{burtonetal83}.

Based on the theoretical results of \cite{lovaszschrijver91} a very effective version of B\&C method
was developed for pure binary optimization problem by \cite{sheraliadams90} and independently
\cite{balasetal93}. Especially Egon Balas and his co-authors could achieve a significant progress.
Their method of lifting cuts means that a locally generated cut can be made globally valid by solving
a larger LP problem and modify the cut according to its optimal solution.

The first integer programming method to solve an IP problem with general, i.e. non-bounded,
integer variables is Ralph Gomory's cutting plane method \cite{gomory58}. 
In a certain sense it is still the only general method. Strong cuts of integer programming
problems are discussed in \cite{balasjeroslow80}. The surrogate constraint (\ref{e22}) has
been introduced by \cite{glover65}. The strength of the inequality depends on the choice of the multipliers
$\lambda_i$. A rule of thumb is that the optimal dual variables of the continuous problem
give a strong inequality provided that the original problem is linear.

The DFJ model of TSP appeared in \cite{dfj}. It was not only an excellent theoretical result, but is also an
enormous computational effort as the capacities and speed of that time computers were far above the
recent ones.
One important cut of the TSP polyhedral set is the
so-called comb inequality. The number of edges of a complete tour is restricted in a special subgraph.
The subgraph 
consists of a subset of cities called {\em hand} and odd number of further subsets of cities intersecting
the hand. They are called {\em teeth} and their number must be at least three. Numerical problems of TSP 
are exhaustively discussed in \cite{reinelt}.

A good summary of Branch and Price is \cite{Barnhartetal98}.
\end{fejmegj}

\bibliography{AlgofInf3-January16}
This bibliography is made by HBib\TeX. First key of the sorting is the name of 
the authors (first author, second author etc.), second key is the year of publication, 
third key is the title of the document.

Underlying shows that the electronic version of the bibliography on the homepage of the book 
contains a link to the corresponding address.
\bibliographystyle{algofinf}

\begin{printindex}
This index uses the following conventions. Numbers are alphabetised as if spelled out; for example, 
``2-3-4-tree" is indexed as if were ``two-three-four-tree". 
When an entry refers to a place other than the main text, the page number is followed by a tag: 
\textit{exe} for exercise, \textit{exa} for example, \textit{fig} for figure, \textit{pr} 
for problem and \textit{fn} for footnote.

The numbers of pages containing a definition are printed in \textit{italic} font, e.g. \\

time complexity, \underline{\textit{583}}.  
\end{printindex}

\begin{printnevindex}
This index uses the following conventions. If we know the full name of a cited person, then 
we print it. If the cited person is not living, and we know the correct data, then we print also the 
year of her/his birth and death.
\end{printnevindex}

\end{document}
