glpk05.tex

著名的大规模线性规划求解器源码GLPK.C语言版本,可以修剪.内有详细帮助文档.

%* glpk05.tex *%

\chapter{Branch-and-Cut API Routines}

\section{Introduction}

\subsection{Using the callback routine}

The GLPK MIP solver based on the branch-and-cut method allows the
application program to control the solution process. This is attained
by means of the user-defined callback routine, which is called by the
solver at various points of the branch-and-cut algorithm.

The callback routine passed to the MIP solver should be written by the
user and has the following specification:\footnote{The name
{\tt foo\_bar} used here is a placeholder for the callback routine
name.}

\begin{verbatim}
   void foo_bar(glp_tree *tree, void *info);
\end{verbatim}

\noindent
where \verb|tree| is a pointer to the data structure \verb|glp_tree|,
which should be used on subsequent calls to branch-and-cut interface
routines, and \verb|info| is a transit pointer passed to the routine
\verb|glp_intopt|, which may be used by the application program to pass
some external data to the callback routine.

The callback routine is passed to the MIP solver through the control
parameter structure \verb|glp_iocp| (see Chapter ``Basic API Routines'',
Section ``Mixed integer programming routines'', Subsection ``Solve MIP
problem with the branch-and-cut method'') as follows:

\newpage

\begin{verbatim}
   glp_prob *mip;
   glp_iocp parm;
   . . .
   glp_init_iocp(&parm);
   . . .
   parm.cb_func = foo_bar;
   parm.cb_info = ... ;
   ret = glp_intopt(mip, &parm);
   . . .
\end{verbatim}

To determine why it is being called by the MIP solver the callback
routine should use the routine \verb|glp_ios_reason| (described in this
section below), which returns a code indicating the reason for calling.
Depending on the reason the callback routine may perform necessary
actions to control the solution process.

The reason codes, which correspond to various point of the
branch-and-cut algorithm implemented in the MIP solver, are described
in Subsection ``Reasons for calling the callback routine'' below.

To ignore calls for reasons, which are not processed by the callback
routine, it should just return to the MIP solver doing nothing. For
example:

\begin{verbatim}
void foo_bar(glp_tree *tree, void *info)
{     . . .
      switch (glp_ios_reason(tree))
      {  case GLP_IBRANCH:
            . . .
            break;
         case GLP_ISELECT:
            . . .
            break;
         default:
            /* ignore call for other reasons */
            break;
      }
      return;
}
\end{verbatim}

To control the solution process as well as to obtain necessary
information the callback routine may use the branch-and-cut API
routines described in this chapter. Names of all these routines begin
with `\verb|glp_ios_|'.

\subsection{Branch-and-cut algorithm}

This section gives a schematic description of the branch-and-cut
algorithm as it is implemented in the GLPK MIP solver.

\medskip

{\it 1. Initialization}

Set $L:=\{P_0\}$, where $L$ is the {\it active list} (i.e. the list of
active subproblems), $P_0$ is the original MIP problem to be solved.

Set $\overline{z}:=+\infty$ (in case of minimization) or
$\overline{z}:=-\infty$ (in case of maximization), where $\overline{z}$
is {\it incumbent value}, i.e. an upper (minimization) or lower
(maximization) global bound for $z^*$, the optimal objective value for
$P^0$.

\medskip

{\it 2. Subproblem selection}

If $L=\emptyset$ then GO TO 9.

Select $P\in L$, i.e. make active subproblem $P$ current.

\medskip

{\it 3. Solving LP relaxation}

Solve $P_{LP}$, which is LP relaxation of $P$.

If $P_{LP}$ has no primal feasible solution then GO TO 8.

Let $z_{LP}^*$ be the optimal objective value for $P_{LP}$.

If $z_{LP}^*\geq\overline{z}$ (in case of minimization) or
$z_{LP}^*\leq\overline{z}$ (in case of maximization) then GO TO 8.

\medskip

{\it 4. Adding ``lazy'' constraints}

Let $x_{LP}^*$ be the optimal solution to $P_{LP}$.

If there are ``lazy'' constraints (i.e. essential constraints not
included in the original MIP problem $P_0$), which are violated at the
optimal point $x_{LP}^*$, add them to $P$, and GO TO 3.

\medskip

{\it 5. Check for integrality}

Let $x_j$ be a variable, which is required to be integer, and let
$x_j^*\in x_{LP}^*$ be its value in the optimal solution to $P_{LP}$.

If $x_j^*$ is integral for all integer variables, then a better integer
feasible solution is found. Store its components, set
$\overline{z}:=z_{LP}^*$, and GO TO 8.

\medskip

{\it 6. Adding cutting planes}

If there are cutting planes (i.e. valid constraints for $P$), which are
violated at the optimal point $x_{LP}^*$, add them to $P$, and GO TO 3.

\medskip

{\it 7. Branching}

Select {\it branching variable} $x_j$, i.e. a variable, which is
required to be integer, and whose value $x_j^*\in x_{LP}^*$ is
fractional in the optimal solution to $P_{LP}$.

Create new subproblem $P_D$ (so called {\it down branch}), which is
identical to the current subproblem $P$ with exception that the upper
bound of $x_j$ is replaced by $\lfloor x_j^*\rfloor$. (For example,
if $x_j^*=3.14$, the new upper bound of $x_j$ in the down branch will
be $\lfloor 3.14\rfloor=3$.)

Create new subproblem $P_U$ (so called {\it up branch}), which is
identical to the current subproblem $P$ with exception that the lower
bound of $x_j$ is replaced by $\lceil x_j^*\rceil$. (For example, if
$x_j^*=3.14$, the new lower bound of $x_j$ in the up branch will be
$\lceil 3.14\rceil=4$.)

Set $L:=L\backslash\{P\}\cup\{P_D,P_U\}$, i.e. remove the current
subproblem $P$ from the active list and add two new subproblems $P_D$
and $P_U$ to the active list. Then GO TO 2.

\medskip

{\it 8. Pruning}

Remove from the active list $L$ all subproblems (including the current
one), whose local bound $\widetilde{z}$ is not better than the global
bound $\overline{z}$, i.e. set $L:=L\backslash\{P\}$ for all $P$, where
$\widetilde{z}\geq\overline{z}$ (in case of minimization) or
$\widetilde{z}\leq\overline{z}$ (in case of maximization), and then
GO TO 2.

The local bound $\widetilde{z}$ for subproblem $P$ is an lower
(minimization) or upper (maximization) bound for integer optimal
solution to {\it this} subproblem (not to the original problem). This
bound is local in the sense that only subproblems in the subtree rooted
at node $P$ cannot have better integer feasible solutions. Note that
the local bound is not necessarily the optimal objective value to LP
relaxation $P_{LP}$.

\medskip

{\it 9. Termination}

If $\overline{z}=+\infty$ (in case of minimization) or
$\overline{z}=-\infty$ (in case of maximization), the original problem
$P_0$ has no integer feasible solution. Otherwise, the last integer
feasible solution stored on step 5 is the integer optimal solution to
the original problem $P_0$. STOP.

\subsection{The search tree}

On the branching step of the branch-and-cut algorithm the current
subproblem is divided into two\footnote{In more general cases the
current subproblem may be divided into more than two subproblems.
However, currently such feature is not used in GLPK.} new subproblems,
so the set of all subproblems can be represented in the form of a rooted
tree, which is called the {\it search} or {\it branch-and-bound} tree.
An example of the search tree is shown on Fig.~1. Each node of the
search tree corresponds to a subproblem, so the terms `node' and
`subproblem' may be used synonymously.

\newpage

\setlength{\unitlength}{1mm}

\begin{figure}[t]
\begin{center}
\begin{picture}(120,105)(0,-35)
\put(65,65){\circle{10}\circle{8}}\put(63.5,64){$A$}
\put(30,45){\circle{10}\circle{8}}\put(28.5,44){$B$}
\put(80,45){\circle{10}\circle{8}}\put(78.5,44){$C$}
\put(115,45){\circle{10}}\put(112.5,43.5){\huge$\times$}
\put(20,25){\circle{10}}\put(17.5,23.5){\huge$\times$}
\put(40,25){\circle{10}}\put(38.5,24){$D$}
\put(60,25){\circle{10}\circle{8}}\put(58.5,24){$E$}
\put(95,25){\circle{10}\circle{8}}\put(93.5,24){$F$}
\put(115,25){\circle{10}}\put(113.5,24){$G$}
\put(5,5){\circle{10}}\put(2.5,3.5){\huge$\times$}
\put(20,5){\circle{10}}\put(17.5,3.5){\huge$\times$}
\put(35,5){\circle{10}}\put(32.5,3.5){\huge$\times$}
\put(45,0){\framebox(10,10){$H$}}
\put(70,5){\circle{10}}\put(69,4){$I$}
\put(85,5){\circle{10}}\put(82.5,3.5){\huge$\times$}
\put(105,5){\circle{10}}\put(103.5,4){$J$}
\qbezier(5,10)(12.5,15)(20,20)
\qbezier(20,10)(20,15)(20,20)
\qbezier(35,10)(27.5,15)(20,20)
\qbezier(50,10)(55,15)(60,20)
\qbezier(70,10)(65,15)(60,20)
\qbezier(85,10)(90,15)(95,20)
\qbezier(105,10)(100,15)(95,20)
\qbezier(20,30)(25,35)(30,40)
\qbezier(40,30)(35,35)(30,40)
\qbezier(60,30)(70,35)(80,40)
\qbezier(95,30)(87.5,35)(80,40)
\qbezier(115,30)(97.5,35)(80,40)
\qbezier(30,50)(47.5,55)(65,60)
\qbezier(80,50)(72.5,55)(65,60)
\qbezier(115,50)(90,55)(65,60)
\put(15,-20){\framebox(10,10){}}
\put(28,-16){Current}
\put(20,-30){\circle{10}}
\put(28,-31){Active}
\put(80,-15){\circle{10}\circle{8}}
\put(88,-16){Non-active}
\put(80,-30){\circle{10}}\put(77.5,-31.5){\huge$\times$}
\put(88,-31){Fathomed}
\end{picture}

\bigskip

Fig. 1. An example of the search tree
\end{center}
\end{figure}

In GLPK each node may have one of the following four statuses:

$\bullet$ {\it current node} is the active node currently being
processed;

$\bullet$ {\it active node} is a leaf node, which still has to be
processed;

$\bullet$ {\it non-active node} is a node, which has been processed,
but not fathomed;

$\bullet$ {\it fathomed node} is a node, which has been processed and
fathomed.

In the data structure representing the search tree GLPK keeps only
current, active, and non-active nodes. Once a node has been fathomed,
it is removed from the tree data structure.

Being created each node of the search tree is assigned a distinct
positive integer called the {\it subproblem reference number}, which
may be used by the application program to specify a particular node of
the tree. The root node corresponding to the original problem to be
solved is always assigned the reference number 1.

\subsection{Current subproblem}

The current subproblem is a MIP problem corresponding to the current
node of the search tree. It is represented as the GLPK problem object
(\verb|glp_prob|) that allows the application program using API routines
to access its content in the standard way. If the MIP presolver is not
used, it is the original problem object passed to the routine
\verb|glp_intopt|; otherwise, it is an internal problem object built by
the MIP presolver.

Note that the problem object is used by the MIP solver itself during
the solution process for various purposes (to solve LP relaxations, to
perfom branching, etc.), and even if the MIP presolver is not used, the
current content of the problem object may differ from its original
content. For example, it may have additional rows, bounds of some rows
and columns may be changed, etc. In particular, LP segment of the
problem object corresponds to LP relaxation of the current subproblem.
However, on exit from the MIP solver the content of the problem object
is restored to its original state.

To obtain information from the problem object the application program
may use any API routines, which do not change the object. Using API
routines, which change the problem object, is restricted to stipulated
cases.

\subsection{The cut pool}

The {\it cut pool} is a set of cutting plane constraints maintained by
the MIP solver. It is used by the GLPK cut generation routines and may
be used by the application program in the same way, i.e. rather than
to add cutting plane constraints directly to the problem object the
application program may store them to the cut pool. In the latter case
the solver looks through the cut pool, selects efficient constraints,
and adds them to the problem object.

\subsection{Reasons for calling the callback routine}

The callback routine may be called by the MIP solver for the following
reasons.

\subsubsection*{Request for subproblem selection}

The callback routine is called with the reason code \verb|GLP_ISELECT|
if the current subproblem has been fathomed and therefore there is no
current subproblem.

In response the callback routine may select some subproblem from the
active list and pass its reference number to the solver using the
routine \verb|glp_ios_select_node|, in which case the solver continues
the search from the specified active subproblem. If no selection is made
by the callback routine, the solver uses a backtracking technique
specified by the control parameter \verb|bt_tech|.

To explore the active list (i.e. active nodes of the branch-and-bound
tree) the callback routine may use the routines \verb|glp_ios_next_node|
and \verb|glp_ios_prev_node|.

\subsubsection*{Request for preprocessing}

The callback routine is called with the reason code \verb|GLP_IPREPRO|
if the current subproblem has just been selected from the active list
and its LP relaxation is not solved yet.

In response the callback routine may perform some preprocessing of the
current subproblem like tightening bounds of some variables or removing
bounds of some redundant constraints.

\subsubsection*{Request for row generation}

The callback routine is called with the reason code \verb|GLP_IROWGEN|
if LP relaxation of the current subproblem has just been solved to
optimality and its objective value is better than the best known integer
feasible solution.

In response the callback routine may add one or more ``lazy''
constraints (rows), which are violated by the current optimal solution
of LP relaxation, using API routines \verb|glp_add_rows|,
\verb|glp_set_row_name|, \verb|glp_set_row_bnds|, and
\verb|glp_set_mat_row|, in which case the solver will perform
re-optimization of LP relaxation. If there are no violated constraints,