\documentclass[11pt]{article}
\usepackage{graphics,graphicx}
%\usepackage[dvips]{graphics,graphicx}
\DeclareGraphicsExtensions{.ps,.jpg,.eps,.pdf,.png}
\usepackage{boxedminipage,amsmath,amsfonts}
\usepackage{url}
\usepackage{./own}
%\usepackage{secdot}
%\usepackage{natbib}
\usepackage{verbatim}
%\usepackage{moreverb}
\usepackage{enumerate}
\usepackage{makeidx}
\bibliographystyle{plain}
\makeindex
     
       
%%%%%
% some other macros
\newcommand{\figurepath}{./figures}
\newcommand{\bibpath}{/Users/kmartin/Documents/files/misc}
\newcommand{\figfiletype}{pdf}

%Brad Bell Macros


% Define the hangref environment used for the References list:
\newenvironment{hangref}
  {\begin{list}{}{\setlength{\itemsep}{4pt}
  \setlength{\parsep}{0pt}\setlength{\leftmargin}{+\parindent}
  \setlength{\itemindent}{-\parindent}}}{\end{list}}

% Set the page margins to 1 inch all around:
\marginparwidth 0pt\marginparsep 0pt \topskip 0pt\headsep
0pt\headheight 0pt \oddsidemargin 0pt\evensidemargin 0pt
\textwidth 6.5in \topmargin 0pt\textheight 9.0in
\newtheorem{theorem}{Theorem}

   
%%%%Added by Leo%%%%
\newcounter{Fig}
\renewcommand{\theFig}{\arabic{Fig}}
\newcommand{\Fig}[2]{\refstepcounter{Fig} \label{#1}
                     {\small\bf Figure \theFig.} {\small\sl #2 \par}}

\setcounter{topnumber}{3}
\renewcommand{\topfraction}{.9}
\setcounter{bottomnumber}{3}
\renewcommand{\bottomfraction}{.9}
\setcounter{totalnumber}{4}
\renewcommand{\textfraction}{.1}
\setlength{\floatsep}{.25in}
\setlength{\intextsep}{.25in}

\setlength{\fboxrule}{2\fboxrule} \setlength{\fboxsep}{3\fboxsep}






\newcommand{\FigureFolder}{figures}




\begin{document}



\title{The OS Dip Solver:\\
A Generic Block-Angluar Decomposition Implementation}
\vskip 2in
\author{Horand Gassmann, Jun Ma,  Kipp Martin}
\maketitle

\begin{abstract}
In this document we describe how to use the Decomposition in Integer Programming
(Dip) project with the Optimization Services (OS) project. In particular,  we
describe the OS Dip solver which is  a generic block-angluar
decomposition algorithm. The OS Dip solver allows users to provide their own
algorithm to solve the subproblems.  The code for this example is contained 
in the folder {\tt ApplicationTemplates/osDip.}




\end{abstract}


\newpage
%\tableofcontents
%\listoffigures
%\listoftables
\hyphenation{com-plex-Type}


 

%\noindent\hrulefill
\newpage

\section{Introduction and Motivation}

We follow the notation of Galati and Ralphs. 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 relaxed, coupling, or block constraints and the 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 origianl 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}
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}.$
\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}


A generic block-angular decomposition algorithm is now available. 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 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 OSDipBockCoinSolver)
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 COIN-OR {bf
Cbc.}
 

\section{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, life is good and things are working. 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:paramaterfile}.


\section{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 memember and since
this {\bf Factory} class member inherits from the {\bf
OSDipBlockSolverFactory} class it should implement a {\tt create()} method that
creates an optject 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 {\bf
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 implemnts 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 appropriated 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 black angular decomposition algorithm.



\vskip 8pt
There is also  {\bf OSDip\_Main.cpp:} which has 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 Alps solver for which the {\tt solve()}
method is called. 


\section{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}.
 
 \section{Simple Plant/Lockbox Location Example}


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

\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}
  \]
  







\section{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 corresspond 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*}
 

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

Here we describe how to use the OSoption stuff and OSInstance.  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 variable 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 and 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. 


\section{The Dip Parameter File}\label{section:paramaterfile}

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 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
paramater values. In the OS Dip implementation there is a class {\bf OSDipParam}
that has a data memmbers key paramaters 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 {\bf GetSetting()} method to return the relevant
paramater 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}.


   


\section{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}



\section{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}



\section{Setting Options}

Kipp -- put in information on how to set options for the {\tt AlpsDecompModel}


Some options to get output

\begin{verbatim}
Turn up the log levels to see when that happens:
[DECOMP]
LogDebugLevel    = 3
LogLevel         = 3
LogDumpModel     = 2
LogLpLevel       = 1
\end{verbatim}


\begin{verbatim}
Yes - it is also used to solve the master problem as an IP. That is, it periodically changes the variables in the master problem (lambda) to integers and solves the master as an integer program. This is a heuristic to try and get incumbent solutions for the entire problem. This, in my thesis, is called Price-and-Branch.
\end{verbatim}
\end{document}

configure - using command line or configure file

for example on lehigh machines that have cplex, my config file is:



# COIN config.site file for common autotools settings
#enable_debug=yes

#use CPLEX
with_lp_solver=cplex
with_ip_solver=cplex

#location of CPLEX
with_cplex_incdir="/usr/local/cplex/include/ilcplex"
with_cplex_lib="-L/usr/local/cplex/lib/x86-64_debian4.0_4.1/static_pic -lcplex -lpthread"



%%%%%%%%%%%%%%%%%%%%%

Matt sept 7


CC'ing DIP list.


I ran the GAP example for  VERSION1. Got it to run with no problem. Very useful. I was hoping you could clarify the folloiwng.

1) It looks like the only place where the blocks get defined are in 235-238:

for(i = 0; i < nMachines; i++){
modelName = "KP" + UtilIntToStr(i);
setModelRelax(NULL, modelName, i);
}

It looks like you are NOT creating a DecompConstraintSet for each block and you
are NOT specifying the variables that go into the blocks. Is this correct? You
simply tell the master how many blocks there are with setModelRelax().


That is correct. There is no "explicit" polyhedron in this example. It is
implicitly defined by the oracle (solveRelaxed).






2) In the solveRelaxed() method, I assume that the redCostX array contains a
reduced cost FOR EVERY variable. Is this true? I guess it must be since I have
not told the master which variables are in which block.  Of course I see the line

const double   * redCostXB   = redCostX + getOffsetI(whichBlock);

which implies maybe redCostX is only the variables for whichBlock? But then I
have not specified the variables in whichBlock. I am confused here and this seems
like a key point.


redCostX is, in fact, for every variable. You will also notice in the arguments
the "whichBlock" that tells you which block you are suppose to solve in that
call. The redCostXB defines the starting point for the reduced costs for block
`whichBlock`. It uses the user-defined 'getOffsetI' function. Since this is a
user-defined oracle, they are responsible for keeping track of which variables
correspond to which blocks. The framework doesn't really need to know that -
since the polyhedron is defined implicitly.




3) This question is related to 2). What if I define "master only" variables.  Do
the "master only" variables reduced cost get included in redCostX in
solveRelaxed()? If you are not telling the master which variables go into which
block, then I guess the concept of "master only" variables is not really needed
or is moot. Correct? Just pass all variable to solveRelaxed(). In my case I do
have variables that appear only in the master. Should I declare these?


Yes, master-only would be included in redCostX and as a user you would want to
ignore them. Each master-only is considered its own block and is dealt with
internally. I guess I should add an example that shows implicit polyhdreon and
master-only variables? Is that the case you have? If so, I can work on that soon.
Yes, you should delcare them and explicitly state them as master-only.






4) This is related to 3). If indeed, redCostX is the vector of all variables then
I suppose I could easily do what I wrote you about earlier this  summer, namely
solve the blocks in parallel. That is I could take redCostX and in my own code,
in parallel solve a problem for each block and then when each solveRelaxed() is
called in turn, give it the solution from my parallel solve. Does this make
sense?


Not yet. Two issues there. (1) the logic by default is to loop over all blocks
and call the solveRelaxed for each value of whichBlock. So, if you solved all in
parallel, you'd get too many. You, could, of course, just solve the "first one"
for all and then skip the rest. But, that is an ugly hack. (2) The argument
convexDual is the dual associated with the convexity constraint for `whichBlock`.
To do what you want, you really need all the duals for the convexity constraint.
Again, you could "get this" by grabbing the full dual vector from the master LP
and parsing it yourself - but that gets tricky when you add in cut and branch
constraints to the master -- the accounting is tricky.

The better approach is for me to provide you an API for doing what you want. I
have not got around to that yet: https://projects.coin-or.org/Dip/ticket/30




% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



Master-only variables need to be dealt with special. Because of the design of
DIP, it relies on a mapping between the compact and extended space. If there are
no master-only vars, this is clearly just x=sum{b} sum{s} lambda^b_s s, where s
is a vector in projected space of x (for each block).

With master-only vars, this only works if you "put these vars" in another block
(or blocks). Experience shows that putting them all in one block and treating it
like another subproblem performs poorly. Since they are unconstrained in the
subproblems, they are all independent and the most efficient thing to do is to
treat each as its own block -- with really only 2 choices - set it at its UB or
LB. All of this can be done efficiently if I know which ones are master-only
vars.

Yes, the user defines all the vars in the core. But, without knowing which are in
the blocks, I don't know which are "master-only".


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


But for each block, convexDual affects the value of the reduced cost, but it has
no effect on which column I choose. The convexDual does not affect the subproblem
solution, only the solution value. Therefore, in the first call to solveRelaxed
(whichBlock = 1) I can use redCostX for all the variables and simultaneously find
the best column for each subproblem. Then when the other subproblems are called
(whichBlock >1) I simply take the column from the first call (do not solve again)
and return it. The convexDual did not affect that solution. Hope I  am making
sense here.



Yep. You are correct, convexDual does not effect the pricing. It only effects the
"check" for negative RC (if you choose to do that as a user - you don't need to
actually) and, the constructor for a DecompVar. The latter could be redesigned so
the user doesn't need to provide it and the internal adjusts it for you. Either
one, a change (or addition) in the API would make this cleaner. I will think
about this and get back to you.

