\section{Using Dip (Decomposition In Integer Programming)}\label{section:OSDip}

{\bf Important Note:}  This example uses COIN-OR projects that are not part of the OS distribution and
assumes you have downloaded the {\tt CoinAll }binary.

We follow the notation of Ralphs and Galati~\cite{ralphsgalatiMP}. The integer program of interest is:

\begin{eqnarray}
z_{IP} &=&  \min  \{c^{\top} x \, | \, A^{\prime} x \ge b^{\prime},  \,\, 
A^{\prime \prime} x \ge b^{\prime \prime}, \, \, x \in \mathbb{Z}^{n}  \}
\end{eqnarray}
The problem is divided into two constraint sets, $A^{\prime} x \ge b^{\prime}$
which we refer to as the {\it relaxed}, {\it coupling}, or {\it block constraints}, and the {\it core
constraints} $A^{\prime \prime} x \ge b^{\prime \prime}$.  We then define the
following polyhedron based on the relaxed constraints.
\begin{eqnarray}
{\cal P} &=&  {\rm conv} ( \{ x \in \mathbb{Z}^{n} \, | \, A^{\prime} x \ge
b^{\prime}
\})
\end{eqnarray}
 The LP relaxation of the original problem is:
\begin{eqnarray}
z_{LP} &=&  \min  \{c^{\top} x \, | \, A^{\prime} x \ge b^{\prime},  \,\, 
A^{\prime \prime} x \ge b^{\prime \prime}, \, \, x \in \mathbb{R}^{n} \}
\end{eqnarray}
We also make use of another, related problem $z_D$, defined by
\begin{eqnarray}
z_{D} &=&  \min \{c^{\top} x \, | \, A^{\prime} x \ge b^{\prime},  \,\, 
x \in {\cal P}, \, \, x \in \mathbb{R}^{n} \}.
\end{eqnarray}
Ideally,  the constraints $A^{\prime} x \ge b^{\prime}$
should be selected so that solving $Z_{D}$ is an easy {\it hard problem} and
provides better bounds than $Z_{LP}.$

A generic block-angular decomposition algorithm is now available. 
We employ an implementation that uses the Optimization Services (OS) project together with
another COIN-OR project, Decomposition in Integer Programming (Dip).
%It is 
%based on the Decomposition in Integer Programming (Dip) project jointly with the Optimization Services (OS) project. 
We call this the OS Dip solver.  It has the following features:

\begin{itemize}
\item[1.]  All subproblems are solved via an oracle; either the default oracle
contained in our distribution (see below) or one provided by the user.

\item[2.] The OS Dip Solver code is independent of the oracle used to optimize
the subproblems.

\item[3.] Variables are assigned to blocks using an OS option file; the block
definition and  assignment of variables to these blocks has no effect on the OS
Dip Solver code.

\item[4.] Different blocks can be assigned different solver oracles based on the
option values given in the OSoL file. 

\item[5.] There is a default oracle implemented (called OSDipBlockCoinSolver)
that currently uses Cbc.

\item[6.] Users can add their own oracles without altering the OS Dip Solver
code. This is done via polymorphic factories. The user creates a separate file containing
the oracle class. The user-provided Oracle class  inherits from the generic
OSDipBlockSolver class. The user need only: 1) add the object file name for the
new oracle to the Makefile, and 2) add the necessary line to
OSDipFactoryInitializer.h indicating that the new oracle is present. 

\end{itemize}

In particular, the  implementation of the OS Dip solver provides a virtual class
{\tt OSDipBlockSolver} with a pure virtual function {\tt solve()}.  The user is
expected to provide a class that inherits from {\tt OSDipBlockSolver} and
implements the method {\tt solve()}.  The {\tt solve()} method should optimize a
linear objective function over ${\cal P}.$ More details are provided in Section
\ref{section:osdipsolver}. The implementation is such  that the user only has to
provide a class with a solve method. The user does not have to edit or alter 
any of the OS Dip Solver code.
By using polymorphic factories the actual solver details are hidden from the OS
Solver.  A default solver, {\tt OSDipBlockCoinSolver}, is provided. This default
solver takes no advantage of special structure and simply calls the COIN-OR solver {\tt
Cbc}.
 

\subsection{Building and Testing the OS-Dip Example}\label{section:build}

Currently, the Decomposition in Integer Programming ({\bf Dip}) package is not a
dependency of the Optimization Services ({\bf OS}) package -- {\bf Dip} is not
included in the {\bf OS} Externals file. In order to run the OS Dip solver it is
necessary to download both the {\bf OS} and {\bf  Dip} projects. Download order is irrelevant. 
In the discussion that follows we assume that for both 
{\bf OS} and {\bf Dip} the user has successfully completed a {\tt
configure}, {\tt make}, and {\tt make install}. We also assume
that the user is working with the trunk version of both {\bf OS} and {\bf Dip.}


The OS Dip solver C++ code is contained in {\tt TemplateApplication/osDip}.
 The {\tt configure}  will create a {\tt Makefile}  in the {\tt
 TemplateApplication/osDip} folder. The {\tt Makefile} must be edited to reflect
 the location of the {\bf Dip} project. The {\tt Makefile} contains the
 line

\begin{verbatim}
DIPPATH = /Users/kmartin/coin/dip-trunk/vpath-debug/
\end{verbatim}

This setting assumes that there is a {\bf lib} directory:

\begin{verbatim}
/Users/kmartin/coin/dip-trunk/vpath-debug/lib
\end{verbatim}
with the {\bf Dip} library that results from {\tt make install} and an {\tt
include} directory
\begin{verbatim}
/Users/kmartin/coin/dip-trunk/vpath/include
\end{verbatim}
with the {\bf Dip} header files generated by {\tt make install}.  The user
should adjust
\begin{verbatim}
/Users/kmartin/coin/dip-trunk/vpath/
\end{verbatim}
to a path containing the {\bf Dip} {\tt lib} and {\tt include} directories. 
After building the executable by executing the {\tt make} command,
 run the {\tt osdip} application using the command:

\begin{verbatim}
./osdip --param osdip.parm
\end{verbatim}

This should produce the following output.


\begin{verbatim}
FINISH SOLVE
Status= 0 BestLB= 16.00000   BestUB= 16.00000   Nodes= 1      
SetupCPU= 0.01 SolveCPU= 0.10 TotalCPU= 0.11 SetupReal= 0.08 
SetupReal= 0.12 TotalReal= 0.16
Optimal Solution
-------------------------
Quality = 16.00
0      1.00
1      1.00
12     1.00
13     1.00
14     1.00
15     1.00
17     1.00

\end{verbatim}

If you see this output,  things are working properly. 
%If this doesn't work, I almost certainly did something stupid and forget to fix it.  

The file
{\tt osdip.parm} is a parameter file. The use of the parameter file is 
explained in Section \ref{section:parameterfile}.


\subsection{The OS Dip Solver -- Code Description and
Key Classes}\label{section:osdipsolver}

The OS Dip Solver uses {\bf Dip} to implement a Dantzig-Wofe decomposition
algorithm for block-angular integer programs. Here are some key classes.




\vskip 8pt
\noindent {\bf OSDipBlockSolver:}  This is a virtual class with a pure virtual
function: 

\begin{verbatim}
void solve(double *cost, std::vector<IndexValuePair*> *solIndexValPair,
double *optVal)
\end{verbatim}



\vskip 8pt
\noindent {\bf OSDipBlockSolverFactory:}  This is also virtual class with a pure
virtual function: 

\begin{verbatim}
OSDipBlockSolver* create()
\end{verbatim}

This class also has the static method

\begin{verbatim}
OSDipBlockSolver* createOSDipBlockSolver(const string &solverName)
\end{verbatim}

and a map

\begin{verbatim}
std::map<std::string, OSDipBlockSolverFactory*> factories;
\end{verbatim}


\vskip 8pt
\noindent {\bf Factory:}  This class inherits from the class {\bf
OSDipBlockSolverFactory}. Every sover class that inherits from the  {\bf
OSDipBlockSolver} class should have a {\bf Factory} class member and since
this {\bf Factory} class member inherits from the {\bf
OSDipBlockSolverFactory} class it should implement a {\tt create()} method that
creates an object in the class inheriting from {\bf
OSDipBlockSolver}.

\vskip 8pt
\noindent {\bf OSDipFactoryInitializer:}  This class initializes the static map

\begin{verbatim}
OSDipBlockSolverFactory::factories
\end{verbatim}
in the {\bf OSDipBlockSolverFactory} class. 

\vskip 8pt
\noindent {\bf OSDipApp:}  This class inherits from the {\bf Dip} class {\tt
DecompApp}. In {\bf OSDipApp} we implement methods for creating the core
(coupling) constraints, i.e., the constraints $A^{\prime \prime} x \ge
b^{\prime \prime}$.  This is done by implementing the  {\tt createModels()}
method. Regardless of the problem, none of the relaxed or block constraints in $A^{\prime } x \ge
b^{\prime}$ are created. These are treated implicitly in the solver class that
inherits from the class {\bf OSDipBlockSolver.}  This class also implements a
method that defines the variables that appear only in the blocks ({\bf
createModelMasterOnlys2}), and a method for generating an initial master (the
method {\bf generateInitVars()  }). 

Since the constraints $A^{\prime } x \ge
b^{\prime}$ are treated explicitly by the Dip solver the {\tt solveRelaxed()}
method must be implemented. In our implementation we have the {\bf OSDipApp} class data
member
\begin{verbatim}
std::vector<OSDipBlockSolver* > m_osDipBlockSolver;
\end{verbatim}
when the {\tt solveRelaxed()} method is called for block {\tt whichBlock} in
turn we make the call
\begin{verbatim}
m_osDipBlockSolver[whichBlock]->solve(cost, &solIndexValPair, &varRedCost);
\end{verbatim}
and the appropriate solver in class {\bf OSDipBlockSolver} is called. Finally,
the {\bf OSDipApp} class also  initiates the reading of the OS option and
instance files. How these files are used is discussed in Section \ref{section:defineinstance}. 
Based on option input
data this class also creates the appropriate solver object for each block, i.e.,
it populates the {\tt  m\_osDipBlockSolver} vector.

\vskip 8pt
\noindent {\bf OSDipInterface:} This class is used  as an interface between the
{\bf OSDipApp} class and classes in the {\bf OS} library. This provides a number
of get methods to provide information to {\bf OSDipApp} such as the coefficients
in the $A^{\prime \prime}$ matrix, objective function coefficients, number of
blocks etc. The {\bf OSDipInterface} class reads the input OSiL and OSoL files
and creates in-memory data structures based on these files. 


  
\vskip 8pt
\noindent {\bf OSDipBlockCoinSolver:}  This class inherits from the {\bf
OSDipBlockSolver} class. It is meant to illustrate how to create a solver class.
This class solves each block by calling {\bf Cbc}.  Use of this class provides a
generic block angular decomposition algorithm.



\vskip 8pt
There is also  {\bf OSDip\_Main.cpp:} which contains the {\tt main()} routine and is
the entry point for the executable. It first creates a new price-branch-and-cut
decomposition algorithm and then an {\tt Alps} solver for which the {\tt solve()}
method is called. 


\subsection{User Requirements}\label{section:userreq}


The {\bf OSDipBlockCoinSolver} class provides a solve method for optimizing a
linear objective function over ${\cal P}$ given a linear objective function.
However, this takes no advantage of the special structure available in the
blocks. Therefore, the user may wish to implement his or her own solver class.
In this case the user is required to do the following:
 
 \begin{itemize}
   
   \item[1.] implement a class that inherits from the {\bf OSDipBlockSolver}
   class and implements the solve method,
   
   \item[2.] implement a class {\bf Factory} that inherits from the class {\bf
OSDipBlockSolverFactory} and implements the {\tt create()} method,

	\item[3.] edit the file {\bf OSDipFactoryInitializer.h} and add a line:
	
	\begin{verbatim}
	OSDipBlockSolverFactory::factories["MyBlockSolver"] = new
	MyBlockSolver::Factory;
	\end{verbatim}
   
   \item[4.] alter the Makefile to include the new source code.
 \end{itemize}
 
 \vskip 8pt
 
 {\bf Important -- Directory Structure:} In order to keep things clean, there is
 a directory {\bf solvers} in the {\bf osDip} folder. We suggest using the {\bf
 solvers} directory for all of the solvers that inherit from {\bf
 OSDipBlockSolver}.
 
 \subsection{Simple Plant/Lockbox Location Example}


 The problem is to minimize
the sum of the cost of capital due to float  and the cost of operating the lock boxes.  

\noindent {\bf Parameters:}
\begin{itemize}
\item[]  $m -$ number of customers to be assigned a lock box

\item[]  $n -$ number of potential lock box sites

\item[]  $c_{ij} -$ annual cost of capital associated with serving customer $j$ from lock box $i$ 

\item[]  $f_{i} -$  annual fixed cost of operating a lock box at location $i$
\end{itemize}

\noindent {\bf Variables:}
\begin{itemize}

\item[]  $x_{ij} - $ a binary variable which is equal to 1 if customer $j$ is assigned to lock box $i$
and 0 if not

\item[]  $y_{i} - $ a binary variable which is equal to 1 if the lock box at location $i$ is opened and 0 if
not

\end{itemize}
The   integer linear program  for the lock box location problem is
$$
\eqnarrayx{
  & \min  &\sum_{i = 1}^{n} \sum_{j = 1}^{m} c_{ij} x_{ij}& + &\sum_{i = 1}^{n} f_{i} y_{i} &&&&&
\eq{eq:lockobj} \cr
(LB) &&x_{ij} - y_{i} &\le& 0, & i = 1, \ldots, n, & j = 1, \ldots, m
&&&\eq{eq:locksetup} \cr  &{\rm s.t.} & \sum_{i = 1}^{n} x_{ij} &=& 1, & j = 1, \ldots, m &&&&\eq{eq:lockdemand} \cr
&& x_{ij}, \, \, y_{i} &\in& \{ 0, 1 \}, & i = 1, \ldots, n, & j = 1, \ldots, m. &&&\eq{eq:lockbinary}
\cr
}
$$

The objective (\ref{eq:lockobj}) is to minimize the sum of the cost of capital plus the fixed cost of
operating the lock boxes.   Constraints (\ref{eq:locksetup})  are forcing 
constraints and require that a lock box be open if a customer is served by that
lock box. For now, we consider these the $A^{\prime} x \ge b^{\prime}$
constraints.  The requirement that every customer be assigned a lock box is
modeled by constraints (\ref{eq:lockdemand}).  For now, we consider these the
$A^{\prime \prime} x \ge b^{\prime \prime}$ constraints.

\vskip 12pt
{\bf Location Example 1:} A three plant, five customer model.

\vskip 8pt

\begin{table}[ht]
\centering
\vskip 8pt
\begin{tabular}{|cc|c|c|} \hline
       &    & CUSTOMER &         \\
      &     &\begin{tabular}{ccccc}
             1&2&3&4&5 \end{tabular} & FIXED COSTS  \\ \hline
     &   1   &\begin{tabular}{ccccc}
             2&3&4&5&7 \end{tabular} &   2  \\
 PLANT & 2   &\begin{tabular}{ccccc}
             4  &  3  &  1  &  2  &  6 \end{tabular} &  3  \\    
       & 3   &\begin{tabular}{ccccc}
            5   &  4  &  2  &  1  &  3 \end{tabular} &  3  \\   \hline
\end{tabular}  
\caption{Data for a 3 plant, 5 customer problem} 
\label{table:spl3by5data}  
\end{table}  
  

\vskip 10pt
\begin{eqnarray*}
\min  && 2x_{11} +3 x_{12} + 4x_{13} + 5x_{14}+ 7x_{15} + 2 y_{1} + \\
&& 4x_{21} +3 x_{22} + x_{23} + 2x_{24}+  6x_{25} + 3y_{2}+ \\
&& 5x_{31} +4 x_{32} + 2 x_{33} + x_{34}+  3x_{35} +   3y_{3} \\
\end{eqnarray*}


\begin{eqnarray*}
\begin{array}{lll}
x_{11}\leq y_{1}\leq 1 & &  \\
x_{12}\leq y_{1}\leq 1 & & \\
x_{13}\leq y_{1}\leq 1 & & \\
x_{14}\leq y_{1}\leq 1 & & \\
x_{15}\leq y_{1}\leq 1 & & \\
x_{21}\leq y_{2}\leq 1 & & \\
x_{22}\leq y_{2}\leq 1 & &   \\
x_{23}\leq y_{2}\leq 1 & & \\
x_{24}\leq y_{2}\leq 1 & & \\
x_{25}\leq y_{2}\leq 1 & & \\
x_{31}\leq y_{3}\leq 1 & & \\
x_{32}\leq y_{3}\leq 1 & &\\
x_{33}\leq y_{3}\leq 1 & &\\ 
x_{33}\leq y_{3}\leq 1 & &\\ 
x_{33}\leq y_{3}\leq 1 & &\\ 
\end{array}
 A^{\prime }x \ge b^{\prime} \,\, {\rm constraints} \\
x_{ij},y_{i}\ge 0 , \,\, i = 1, \ldots, n, \, \, j = 1, \ldots, m.   
\end{eqnarray*}

 
\[
\begin{array}{llll}
{\rm s.t.} &x_{11}+x_{21}+x_{31}  = 1 & & \\
&x_{12}+x_{22}+x_{32} = 1 & &   \\
&x_{13}+x_{23}+x_{33} = 1 & &  \\
&x_{14}+x_{24}+x_{34} = 1 & &  \\
&x_{15}+x_{25}+x_{35} = 1 & &  
\end{array}   A^{\prime \prime}   x \ge b^{\prime \prime} \,\, {\rm
constraints}
\]
  
  


                      


\vskip 12pt

{\bf Location Example 2 (SPL2):} A three plant, three customer model.

\vskip 8pt


\begin{table}[ht]
\centering
\begin{tabular}{|cc|c|c|} \hline
       &    & CUSTOMER &         \\
      &     &\begin{tabular}{ccc}
             1&2&3 
             \end{tabular} & FIXED COSTS  \\ \hline
     &   1   &\begin{tabular}{ccc}
             2&1&1 
             \end{tabular} &   1  \\
 PLANT & 2   &\begin{tabular}{ccc}
             1  &  2  &  1   
             \end{tabular} &  1  \\    
       & 3   &\begin{tabular}{ccc}
            1   &  1  &  2   
            \end{tabular} &  1  \\   \hline
\end{tabular} 
\caption{Data for a three plant, three customer problem} 
\label{table:spl3by3data}   
\end{table}  

  
\vskip 8pt
\begin{eqnarray*}
\min  && 2x_{11} + x_{12} + x_{13}  +  y_{1} + \\
&& x_{21} +2 x_{22} + x_{23} +       y_{2}+ \\
&& x_{31} + x_{32} + 1 x_{33} +  +       y_{3} \\
\end{eqnarray*}


  
\begin{eqnarray*}
\begin{array}{lll}
x_{11}\leq y_{1}\leq 1 & &  \\
x_{12}\leq y_{1}\leq 1 & & \\
x_{13}\leq y_{1}\leq 1 & & \\
x_{21}\leq y_{2}\leq 1 & & \\
x_{22}\leq y_{2}\leq 1 & &   \\
x_{23}\leq y_{2}\leq 1 & & \\
x_{31}\leq y_{3}\leq 1 & & \\
x_{32}\leq y_{3}\leq 1 & &\\
x_{33}\leq y_{3}\leq 1 & &\\ 
\end{array}
A^{\prime}   x \ge b^{\prime} \,\, {\rm
constraints} \\
x_{ij},y_{i}\ge 0 , \,\, i = 1, \ldots, n, \, \, j = 1, \ldots, m.   
\end{eqnarray*}

\[
\begin{array}{llll}
{\rm s.t.} &x_{11}+x_{21}+x_{31} = 1 & & \\
&x_{12}+x_{22}+x_{32} = 1 & &   \\
&x_{13}+x_{23}+x_{33} = 1 & &
\end{array}  A^{\prime \prime}   x \ge b^{\prime \prime} \,\, {\rm
constraints}
  \]
  







\subsection{Generalized Assignment Problem Example}\label{section:genass}

A problem that plays a prominent role in
vehicle routing is the {\it generalized assignment problem.}    The problem is to assign each of $n$
tasks to $m$ servers without exceeding the resource capacity of the servers.

\noindent{\bf Parameters:}
\begin{itemize}
\item[]  $n -$ number of required tasks
\item[]  $m -$   number of servers
\item[]  $f_{ij} -$ cost of assigning task $i$ to server $j$
\item[]  $b_{j} -$  units of resource available to server $j$
\item[]  $a_{ij} -$ units of server $j$ resource required to perform task $i$
\end{itemize}

\noindent{\bf Variables:}
\begin{itemize}
\item[]  $x_{ij} -$ a binary variable which is equal to 1 if task $i$ is assigned to server $j$
and 0 if not
\end{itemize}
The integer linear program for the generalized assignment problem  is 
$$
\eqnarrayx{
&  \min &\sum_{i = 1}^{n} \sum_{j = 1}^{m} f_{ij} x_{ij} &&&&&&& \eq{eq:gapobj} \cr
(GAP) &{\rm s.t.}& \sum_{j = 1}^{m} x_{ij} &=& 1, & i = 1, \ldots, n  &&&& \eq{eq:gapassign} \cr
&& \sum_{i = 1}^{n} a_{ij} x_{ij} &\le& b_{j}, &j = 1, \ldots, m  &&&&\eq{eq:gapcapacity}  \cr
&& x_{ij} &\in& \{ 0, 1 \}, & i = 1, \ldots, n, & j = 1, \ldots, m.  &&&
\eq{eq:gapbinary}  \cr
}
$$

The objective function (\ref{eq:gapobj}) is to minimize the total assignment cost.  Constraint
(\ref{eq:gapassign}) requires that each task is assigned a server.  These
constraints correspond to the $A^{\prime \prime} x \ge b^{\prime \prime}$
constraints.   The requirement that the server capacity not be exceeded is given
in (\ref{eq:gapcapacity}). These correspond to the $A^{\prime} x \ge
b^{\prime}$ constraints that are used to define ${\cal P}$. The test problem
used in the file {\tt genAssign.osil} is:


 
\begin{eqnarray*}
{\rm min} \quad 2 x_{11} + 11 x_{12} + 7 x_{21} + 7 x_{22} && \\
+ 20 x_{31} + 2 x_{32} + 5 x_{41} + 5x_{42} && \\
x_{11} + x_{12}  &=&    1  \\
x_{21} + x_{22}  &=&    1 \\
x_{31} + x_{32} &=&    1 \\
x_{41} + x_{42} &=&    1 \\
3 x_{11} + 6 x_{21} + 5 x_{31} + 7 x_{41} &\le&   13 \\
2 x_{12} + 4 x_{22} + 10 x_{32} + 4 x_{42} &\le&   10
\end{eqnarray*}
 

\subsection{Defining the Problem Instance and Blocks}\label{section:defineinstance}

Here we describe how to use the OSOption and OSInstance formats.  We illustrate
with a simple plant location problem. Refer back to the example in Table
\ref{table:spl3by5data} for a three-plant, five-customer problem. We treat the
fixed charge constraints as the block constraints, i.e., we treat constraint set
(\ref{eq:locksetup}) as the set $A^{\prime} x \ge b^{\prime}$ constraints. These
constraints naturally break into a block for each plant, i.e., there is a block
of constraints:
\begin{eqnarray}
x_{ij} \le y_{i}
\end{eqnarray}
In order to use the OS Dip solver it is necessary to: 1) define the set of
variables in each block and 2) define the set of constraints that constitute the
core or coupling constraints. This information is communicated to the OS Dip
solver using Optimization Services option Language (OSoL). The OSoL input file
for the example in  Table \ref{table:spl3by5data} appears in Figures
\ref{figure:parinc-osil} and \ref{figure:parinc-osil2}.  See lines 32-55. There
is an {\tt <other>} option with {\tt name="variableBlockSet"} for each block.
Each block then lists the variables in the block. For example, the first block
consists of the variables indexed by 0, 1, 2, 3, 4, and 15. These correspond to
variables $x_{11},$  $x_{12},$  $x_{13},$  $x_{13},$ $x_{14},$ and  $y_{1}.$
Likewise the second block corresponds to the variable for the second plant and
the third block corresponds to variables for the third plant.


  

{\small
\begin{figure}[hp]
   \small {\obeyspaces\let =\
\makebox[0in][t]{\fbox{\tt\begin{tabular}{@{}l@{}}
1   <?xml version="1.0" encoding="UTF-8"?>\\
2   <osol>\\
3      <general>\\
4         <instanceName>spl1 -- setup constraints are the blocks</instanceName>\\
5      </general>\\
6      <optimization>\\
7         <variables numberOfOtherVariableOptions="6">\\
8            <other name="initialCol" solver="Dip" numberOfVar="6" value="0">\\
9               <var idx="0" value="1"/>\\
10              <var idx="1" value="1"/>\\
11              <var idx="2" value="1"/>\\
12              <var idx="3" value="1"/>\\
13              <var idx="4" value="1"/>\\
14              <var idx="15" value="1"/>\\
15           </other>\\
16           <other name="initialCol" solver="Dip" numberOfVar="6" value="1">\\
17              <var idx="5" value="1"/>\\
18              <var idx="6" value="1"/>\\
19              <var idx="7" value="1"/>\\
20              <var idx="8" value="1"/>\\
21              <var idx="9" value="1"/>\\
22              <var idx="16" value="1"/>\\
23           </other>\\
24           <other name="initialCol" solver="Dip" numberOfVar="6" value="2">\\
25              <var idx="10" value="1"/>\\
26              <var idx="11" value="1"/>\\
27              <var idx="12" value="1"/>\\
28              <var idx="13" value="1"/>\\
29              <var idx="14" value="1"/>\\
30              <var idx="17" value="1"/>\\
31           </other>\\
32           <other name="variableBlockSet" solver="Dip" numberOfVar="6" value="MySolver1">\\
33              <var idx="0"/>\\
34              <var idx="1"/>\\
35              <var idx="2"/>\\
36              <var idx="3"/>\\
37              <var idx="4"/>\\
38              <var idx="15"/>\\
39           </other>\\
40           <other name="variableBlockSet" solver="Dip" numberOfVar="6" value="MySolver2">\\
41              <var idx="5"/>\\
42              <var idx="6"/>\\
43              <var idx="7"/>\\
44              <var idx="8"/>\\
45              <var idx="9"/>\\
46              <var idx="16"/>\\
47           </other>\\
\end{tabular} }}} \medskip
\caption{A sample OSoL file -- SPL1.osol}\label{figure:parinc-osil}
\end{figure}
} %end small


It is also necessary to convey which constraints constitute the core
constraints. This is done in lines 58-64. The core constraints are indexed by
15, 16, 17, 18, 19. These constitute the demand constraints given in Equation
(\ref{eq:lockdemand}). 


Notice also that in lines 32, 40, and 48 there is an attribute {\tt value} in
the {\tt <other>} variable element with the attribute {\tt name} equal to {\tt
variableBlockSet}.  The attribute {\tt value} should be the name of the solver
factory that should be assigned to solve that block. For example, if the
optimization problem that results from solving a linear objective over the
constraints defining the first block is solved using {\tt MySolver1} then this
must correspond to a 

\begin{verbatim}
OSDipBlockSolverFactory::factories["MySolver1"] = new
MySolver1::Factory;
\end{verbatim}  

in the file {\bf OSDipFactoryInitializer.h}.  In the test file, {\tt spl1.osol}
for the first block we set the solver to a specialized solver for the simple
plant location problem ({\tt OSDipBlockSplSolver}) and for the other two blocks
we use the generic solver ({\tt OSDipBlockCoinSolver}).




{\small
\begin{figure}[hp]
   \small {\obeyspaces\let =\
\makebox[0in][t]{\fbox{\tt\begin{tabular}{@{}l@{}}
48           <other name="variableBlockSet" solver="Dip" numberOfVar="6" value="MySolver3">\\
49              <var idx="10"/>\\
50              <var idx="11"/>\\
51              <var idx="12"/>\\
52              <var idx="13"/>\\
53              <var idx="14"/>\\
54              <var idx="17"/>\\
55           </other>\\
56        </variables>\\
57        <constraints numberOfOtherConstraintOptions="1">\\
58           <other name="constraintSet" solver="Dip" numberOfCon="5" type="Core">\\
59              <con idx="15"/>\\
60              <con idx="16"/>\\
61              <con idx="17"/>\\
62              <con idx="18"/>\\
63              <con idx="19"/>\\
64           </other>\\
65        </constraints>\\
66     </optimization>\\
67  </osol>\\
\end{tabular} }}} \medskip
\caption{A sample OSoL file -- SPL1.osol (Continued)}\label{figure:parinc-osil2}
\end{figure}
} %end small
 
One can use the OSoL file to specify a set of starting columns for the initial
restricted master. In Figure \ref{figure:parinc-osil} see lines 8-31.  In an OS
option file (OSoL) there is {\tt <variables>} element that has {\tt <other>}
children. Initial columns are specified using the {\tt <other>} elements. This
is done by using  the {\tt name} attribute and setting its value to {\tt
initialCol}. Then the children of the tag contain index-value pairs that specify
the column. For example, the first initial column corresponds to setting:

\begin{eqnarray*}
x_{11} = 1, \quad  x_{12} = 1, \quad  x_{13} = 1, \quad  x_{14} = 1, \quad
x_{15} = 1, \quad y_{1} = 1
\end{eqnarray*}


Finally note that in all of this discussion we know to apply the options to {\bf
Dip} because the attribute {\tt solver} always had value {\tt Dip}. It is
critical to set this attribute in all of the option tags. 


\subsection{The Dip Parameter File}\label{section:parameterfile}

The {\bf Dip} solver has a utility class {\bf UtilParameters},  for parsing
a parameter file. The {\bf UtilParameters} class constructor takes a parameter
file as an argument. In the case of the OS Dip solver the name of the parameter
file is {\bf osdip.parm} and the parameter file is read in at the command line with
the command

\begin{verbatim}
./osdip -param osdip.parm
\end{verbatim}

The {\bf UtilParameters} class has a method {\bf GetSetting()} for reading the
parameter values. In the OS Dip implementation there is a class {\bf OSDipParam}
that has as data members key parameters such as the name of the input OSiL file
and input OSoL file. The {\bf OSDipParam} class has a method
{\bf getSettings()} that takes as an argument a pointer to an object in the {\bf
UtilParameters} and uses the {\bf GetSetting()} method to return the relevant
parameter values. For example:

\begin{verbatim}
OSiLFile = utilParam.GetSetting("OSiLFile", "", common); 
OSoLFile = utilParam.GetSetting("OSoLFile", "", common);
\end{verbatim}

In the current {\bf osdip.parm} file we have:

\begin{verbatim}

#first simple plant location problem
OSiLFile = spl1.osil
#setup constraints as blocks
OSoLFile = spl1.osol
#assignment constraints as blocks
#OSoLFile = spl1-b.osol

#second simple plant location problem
#OSiLFile = spl2.osil
#setup constraints as blocks
#OSoLFile = spl2.osol
#assignment constraints as blocks
#OSoLFile = spl2-b.osol

#third simple plant location problem -- block matrix data not used
#OSiLFile = spl3.osil
#setup constraints as blocks
#OSoLFile = spl3.osol

#generalized assignment problem
#OSiLFile = genAssign.osil
#OSoLFile = genAssign.osol

#Martin textbook example
#OSiLFile = smallIPBook.osil
#OSoLFile = smallIPBook.osol
\end{verbatim}
 
By commenting and uncommenting you can run one of four problems that are in the
{\bf data} directory. The first example, {\bf spl1.osil}, corresponds to the
simple plant location model given in Table \ref{table:spl3by5data}. Using the
option file {\bf spl1.osol} treats the setup forcing constraints
\ref{eq:locksetup} as the $A^{\prime} x \ge b^{\prime}$ constraints. Using the
option file {\bf spl1-b.osol} treats the demand constraints
\ref{eq:lockdemand} as the $A^{\prime} x \ge b^{\prime}$ constraints. Likewise
for the problem {\bf spl2.osil} which correponds to the simple plant location
data given in Table \ref{table:spl3by3data}.

In both examples {\bf spl1.osil} and {\bf spl2.osil} the $A^{\prime} x \ge
b^{\prime}$ constraints are explicitly represented in the OSiL file. However,
this is not necessary. The solver Factory {\bf OSDipBlockSlpSolver} is a special
oracle that only needs the objective function coefficients and pegs variables
based on the sign of the objective function coefficients. The {\bf spl3.osil} is
the example given in Table \ref{table:spl3by5data} but without the setup forcing
constraints. Each block uses the {\bf OSDipBlockSlpSolver} oracle. 

The {\bf genAssign.osil} file corresponds to the generalized assignment problem
given in Section \ref{section:genass}.  The option file {\bf genAssign.osol} 
treats the capacity constraints \ref{eq:gapcapacity} as the $A^{\prime} x \ge
b^{\prime}$ constraints. 

The last problem defined in the file {\bf smallIPBook.osil} is based on Example
16.3 on page 567 in {\it Large Scale Linear and Integer Optimization}.  The
option file treats the constraints
$$
4x_{1} + 9 x_{2} \le 18, \quad -2x_{1} + 4 x_{2} \le 4
$$
as the $A^{\prime} x \ge b^{\prime}$ constraints.

The user should also be aware of the parameter {\tt solverFactory}. This
parameter is the name of the default solver Factory. If a solver is not named
for a block in the OSoL file this value is used. We have set the value of this
string to be {\tt OSDipBlockCoinSolver}.


   


\subsection{Issues to Fix}

\begin{itemize}
  \item Enhance solveRelaxed to allow parallel processing of blocks. See ticket
  30.
  \item Does not work when there are 0 integer variables. See ticket 31.
  
  \item Be able to set options in C++ code. See ticket 41.  It would be nice to
  be able to read all the options from a generic options file. It seems like
  right now options for the {\bf DecompAlgo } class cannot be set inside C++.
  
  \item Problem with Alps  bounds at node 0. See ticket 43
  
  \item Figure out how to use BranchEnforceInMaster or BranchEnforceInSubProb so
  I don't get the large bonds on the variables. See ticket 47.
\end{itemize}



\subsection{Miscellaneous Issues}
 
 If you want to terminate at the root node and just get the dual value under the {\tt ALPS } option put:
 
\begin{verbatim}
[ALPS]
nodeLimit = 1
\end{verbatim}

More from Matt:



\begin{verbatim}
Kipp - the example you sent finds the optimal solution after a few passes of pricing and therefore never calls the cut generator. By default, the PC solver, in the root node starts with pricing, and does not stop until it prices out (or finds optimal, or within gap limits).

If it prices out and has not yet found optimal, then it will proceed to cuts.

This is parameter driven.


You'll see in the log file (LogDebugLevel = 3),
PRICE_AND_CUT  LimitRoundCutIters       2147483647
PRICE_AND_CUT  LimitRoundPriceIters     2147483647

This is the number of Price/Cut iterations to take before switching off (i.e., MAXINT).

To force it to cut before pricing out, change this parameter in the parm file. For example, if you change to :

[DECOMP]
LimitRoundPriceIters = 1
LimitRoundCutIters   = 1

It will then go into your generateCuts after one pricing iteration.

\vskip 12pt

If there is an integer solution at the root node, it may be the case that we are still not optimal. A perfect example is where you want to add tour-breaking constraints. There could be an integer solution, but you still violate a tour-breaking constraint. Here is what Matt says:
``By default, DIP assumes, that if problem is LP feasible to the linear system and IP feasible, then it is feasible. In the case where the user knows something that DIP does not (e.g., that the linear system does not define the entire valid constraint system, as in TSP), then they must provide a derivation of this function APPisUserFeasible. Then, DIP will check LP feasible, IP feasible and lastly, APPisUserFeasible before declaring a point a feasible solution.''

For an example of using this see, \url{https://projects.coin-or.org/Dip/browser/trunk/Dip/examples/TSP/TSP_DecompApp.cpp}.

\end{verbatim}
