%===========================================================================%
%                                                                           %
% This file is part of the documentation for the SYMPHONY MILP Solver.      %
%                                                                           %
% SYMPHONY was jointly developed by Ted Ralphs (ted@lehigh.edu) and         %
% Laci Ladanyi (ladanyi@us.ibm.com).                                        %
%                                                                           %
% (c) Copyright 2000-2011 Ted Ralphs. All Rights Reserved.                  %
%                                                                           %
% SYMPHONY is licensed under the Eclipse Public License. Please see         %
% accompanying file for terms.                                              %
%                                                                           %
%===========================================================================%

\section{Navigating the Source Code}

To develop an application with SYMPHONY, you need to first understand how the
source files are organized. Note that in this chapter, all path names are
given Unix-style. When you unpack the \BB\ source distribution, you will
notice at the root level a number of files associated with the automatic
configuration system, as well as a number of subdirectories, each of which
corresponds to a library used by SYMPHONY for some specific functionality. The
files associated with SYMPHONY itself are located in the \code{SYMPHONY}
subdirectory. Within the SYMPHONY subdirectory are a number of other
subdirectories, including one called \code{src} containing the source files
for SYMPHONY itself. 

Also in the main \code{SYMPHONY/} subdirectory, there is a subdirectory called
\code{Applications/} (see Sections~\ref{build_appl_unix} and
\ref{build_appl_msvc}) for instructions on building the applications). The
\code{Applications/} subdirectory contains the source code for a number of
sample applications developed with SYMPHONY, as well as function stubs for
developing a custom application using SYMPHONY's callbacks. The subdirectory
\code{SYMPHONY/Applications/USER} contains the files needed for implementing
the callbacks and is a template for developing an application. In this
directory and its subdirectories, which mirror the subdirectories of SYMPHONY
itself, each file contains function stubs that can be filled in to create a
new custom application. There is a separate subdirectory for each
module---master (\code{Master/}), tree management (\code{TreeManager/}), cut
generation (\code{CutGen/}), cut management (\code{CutPool/}), and node
processing (\code{LP/}). Within each subdirectory, there is a file, initially
called \code{USER/*/user\_*.c}, where \code{*} is the name of the module. The
primary thing that you, as the user, need to understand to build a custom
application is how to fill in these stubs. That is what the second part of
this chapter is about. Before describing that, however, we will discuss how to
build your application. 

%Within the \code{src} subdirectory, the files are
%organized along the lines of the modules. There is a separate subdirectory for
%each module---master (\code{Master/}), tree management (\code{TreeManager/}),
%cut generation (\code{CutGen/}), cut management (\code{CutPool/}), and node
%processing (\code{LP/}). In addition, there are directories called
%\code{DrawGraph/} and \code{Common/} that also contain source files. The
%\code{DrawGraph/} directory provides an interface from \BB\ to the
%\emph{Interactive Graph Drawing} software package developed by Marta Es\"o.
%This is an excellent utility for graphical display and debugging. The
%\code{Common/} directory contains source code for functions used by multiple
%modules.

%Within each module's directory, there is a primary source file containing the
%function \code{main()} (named \code{*.c} where \code{*} is the module name), a
%source file containing functions related to inter-process communication (named
%\code{*\_proccomm.c}) and a file containing general subroutines used by the
%module (named \code{*\_func.c}). The master is the exception and is organized
%slightly differently. The LP process source code is further subdivided due to
%the sheer number of functions.

%In the main \code{SYMPHONY/} subdirectory (at the same level as the
%\code{src/} subdirectory), there is also a subdirectory called \code{include/}
%that contains the header files. Corresponding to each module, there are three
%header files, one containing internal data structures and function prototypes
%associated with the module (named \code{sym\_*.h} where * is the module name),
%one containing the data structures for storing the parameters (these are also
%used by the master process), and the third containing the function prototypes
%for the user callbacks (name \code{sym\_*\_u.h}). By looking at the header
%files, you should get a general idea of how things are laid out.

%FIXME: Check this
\section{Building an Application}
\label{building_custom_app}

Note that the template application can be built and will work without
modifying any of the source files. In this case, SYMPHONY will behave
according to default settings. 

\subsection{Unix}

First, download, configure, and compile SYMPHONY as described in Section
\ref{build_appl_unix}. This will generate the required library and makefiles
for each application. After this, typing \code{make} in the
\code{SYMPHONY/Applications/USER/} subdirectory should successfully build the
executable. For more information, including the parallel configuration
instructions, see the \code{SYMPHONY/Applications/USER/INSTALL} file.

\subsection{Microsoft Visual C++}

First, download \code{SYMPHONY-\VER} and unpack the archive if it is
required. You now have three options. You can either compile on the
command-line using the automated DEVENV build system or NMAKE utility or you
can use the provided project and solution files. For all of the following
options, first go to the \code{SYMPHONY\bs Applications\bs USER\bs
MSVisualStudio \bs v8} directory.

\subsubsection{Using the MSDEV Utility}
\begin{itemize}
\item Open a command line terminal and type
{\color{Brown}
\begin{verbatim}
 devenv user.sln /Build "Win32|Release"
\end{verbatim}
} 
This will create both the release version of the USER application, including
the executable \code{user} and the SYMPHONY library needed for linking with
applications.

\item To test the executable, type 
{\color{Brown}
\begin{verbatim}
 Debug\user.exe -F ..\..\sample.user
\end{verbatim}
}
\item If USER source files are modified, type 
{\color{Brown}
\begin{verbatim}
 devenv user.sln /make all /rebuild
\end{verbatim}
}
in order to clean and rebuild everything.
\end{itemize} 

\subsubsection{Using the MSVC++ IDE}

\begin{itemize}
\item Open the solution file \code{user.sln}.

\item 
The configuration steps are exactly the same with the MSVC++ section of 
\code{SYMPHONY}. The only 
difference is that, you have the \code{user} project instead of the
\code{symphony} project. Go through the related steps of section 
\ref{getting_started_windows} to see how to get USER executable. 

\item
Once you have the proper settings, choose \code{Build
user.exe} from the \code{Build} menu. This should successfully 
build the executable.

\item
To test the executable, right click on the \code{user} project, go to the
\code{Debug} tab and set the program arguments to 
\code{-F ..\bs ..\bs sample.mps}. Note that command-line switches are 
Unix-style.

\item
Now choose \code{Execute} from the build menu and you have a working branch
and bound solver! After successful compilation, you can fill in the user
callback functions as describe in Section \ref{SYMPHONY-development}.
\end{itemize}

\section{Writing the Callbacks}

For each module, all callback functions are invoked from so-called
\emph{wrapper functions} that provide the interface and also performs a
default action if the user chooses not to override it. Although SYMPHONY is
written in C, the wrapper functions provide a C++-style interface in which the
user can either accept the default action or override it. Each wrapper
function is named \code{*\_u()} , where \code{*} is the name of the
corresponding callback function, and is defined in a file called
\code{*\_wrapper.c}. The wrapper function first collects the necessary data
and hands it to the user by calling the user function. Based on the return
value from the user, the wrapper then performs any necessary post-processing.
All callback functions have default options, so that SYMPHONY now acts as a
generic MILP solver out of the box.

In Section \ref{API}, the callback functions are described in
detail.  The name of every callback function starts with \code{user\_}.
There are three kinds of arguments:
\begin{description}
\item[\rm IN:] An argument containing information that the user might need
to perform the function.
\item[\rm OUT:] A pointer to an argument in which the user should
return a result (requested data, decision, etc.) of the function. 
\item[\rm INOUT:] An argument which contains information the user might need,
but also for which the user can change the value.
\end{description}
The return values for most function are as follows:
\begin{description}
\item[Return values:] \hfill

\begin{tabular}{lp{310pt}} 

\code{USER\_ERROR} & Error in the user function. Printing an error message is
the user's responsibility. Depending on the work the user function was
supposed to do, the error might be ignored (and some default option used), or
the process aborts. \\

\code{USER\_SUCCESS} & The user function was implemented and executed correctly. \\

\code{USER\_DEFAULT} & This option means that the user function was not
implemented and that SYMPHONY should either execute a default subroutine (the
default is one of the built-in options---\BB\ decides which one to use based on
initial parameter settings and the execution of the algorithm) or else do
nothing, if execution of the subroutine is optional. \\

\code{built\_in\_option1 } & \\
\code{built\_in\_option2 } ... & The specified built-in option will be used.\\
\end{tabular}

\item[Notes:] \hfill
\begin{itemize}
\vspace{-3ex}

\item Sometimes an output is optional. This is always noted in the
function descriptions.

\item If an array has to be returned (i.e., the argument is \code{type
  **array}), then (unless otherwise noted) the user has to allocate space for
  the array itself and set \code{*array} to be the array allocated. If an
  output array is optional and the user is not returning any values in that
  array, then the user {\em must not} set \code{*array} because this is how
  \BB\ decides which optional arrays are filled up.

\item Some built-in options are implemented so that the user can invoke them
directly from the callback function. This might be useful if, for example,
the user wants to use different built-in options at different stages
of the algorithm.
\end{itemize}

\end{description}

\section{Data Structures}

The user can define her own data structure for each module to maintain problem
data and any other information the user needs access to in order to implement
functions to customize the solver. A pointer to this data structure is
maintained by \BB\ and is passed to the user as an argument to each user
function. The pointer must be initially passed using the
\ptt{sym\_set\_user\_data()} command. Since \BB\ knows nothing about this data
structure, it is up to the user to allocate it and maintain it. The user must
also implement a function to free it. The functions for freeing the user data
structures in each module are called \code{user\_free\_*}, where \code{*} is
the module. These functions are called by SYMPHONY at the time when other data
structures for the modules are being freed and the module is being closed. By
default, for sequential computation, there is one common user data structure
for all modules and the pointer to that data structure is passed to all user
functions, regardless of the module. This setup should work fine for most
sequential applications. In parallel, however, pointers cannot be shared
between modules and data must be explicitly passed. In this case, it is
sometimes more efficient to maintain in each module only the data necessary to
perform the functions of that module.

\section{Parallel Implementation}

\subsection{Distributed-memory Architectures}
\label{communication}

While the implementation of \BB\ strives to shield the user from having to
know anything about communications protocols or the specifics of inter-process
communication, it may be necessary for the user to pass information from one
module to another in order to implement a parallel application. For instance,
the user may want to pass data describing the problem instance to the LP
process after reading them in from a file in the master process. For the
purpose of passing user data from the master process to other processes, a
customization function called
\code{user\_send\_*\_data()} is provided in the master module, along with a
corresponding function called \code{user\_receive\_*\_data()} in the module
\code{*}. These two functions work in tandem to transport the user's data
from the maser, where it can be read in from a file, to the proper module for
processing. There are also a number of other tandem pairs of \emph{send} and
\emph{receive} functions that are used to transport user data from place to
place.

All data are sent in the form of arrays of either type \code{char}, \code{int},
or \code{double}, or as strings. To send an array, the user has simply to
invoke the function \code{send\_XXX\_array(XXX *array, int length)} where
\code{XXX} is one of the previously listed types. To receive that array,
there is a corresponding function called \code{receive\_?\_array(?  *array, int
length)}. When receiving an array, the user must first allocate the
appropriate amount of memory. In cases where variable length arrays need to be
passed, the user must first pass the length of the array (as a separate array
of length one) and then the array itself. In the receive function, this allows
the length to be received first so that the proper amount of space can be
allocated before receiving the array itself. Note that data must be received
in exactly the same order as it was passed, as data is read linearly into and
out of the message buffer. The easiest way to ensure this is done properly is
to simply copy the send statements into the receive function and change the
function names. It may then be necessary to add some allocation statements in
between the receive function calls.

\subsection{Shared-memory Architectures}
\label{shared}

In the shared memory configuration, it is not necessary to use
message passing to move information from one module to another since
memory is globally accessible. In the few cases where the user would
ordinarily have to pass information using message passing, it is
easiest and most efficient to simply copy the information to the new
location. This copying gets done in the {\em send} function and hence
the {\em receive} function is never actually called. This means that
the user must perform all necessary initialization, etc. in the send
function. This makes it a little confusing to write source code which
will work for all configurations. However, the confusion should be
minimized by looking at the sample applications, especially the VRP solver,
which works in all configurations, sequential, distributed parallel, and
shared parallel. 

%\subsection{Unix Operating Systems}

%Once the callback functions are filled in, all that remains is to compile the
%application. The distribution comes with two makefiles that facilitate this
%process. The primary makefile resides in the {\tt SYMPHONY-\VER/} directory.
%The user makefile resides in the user's subdirectory, initially called
%\code{SYMPHONY-\VER/SYMPHONY/Applications/USER/}. This subdirectory can be
%moved, as well as renamed. There are a number of variables that must be set in
%the primary make file. To modify the makefiles appropriately, see the
%instructions in Section \ref{getting_started_unix}.

%\subsection{Microsoft Windows}

%First, follow the instructions for compiling SYMPHONY in Section
%\ref{getting_started_windows} to ensure you have the proper settings. Once the
%stub files in the {\tt SYMPHONY-\VER\bs SYMPHONY\bs Applications \bs USER}
%hierarchy are filled in, you should be able to compile the new application and
%run it successfully.

\section{Debugging Your Application}

Much of this section applies to Unix operating systems. However, it may
also be useful for Windows users.

\subsection{The First Rule}

\BB\ has many built-in options to make debugging easier. The most
important one, however, is the following rule. {\bf It is easier to
debug the fully sequential version than the fully distributed
version}. Debugging parallel code is not terrible, but it is more
difficult to understand what is going on when you have to look at the
interaction of several different modules running as separate
processes. This means multiple debugging windows which have to be
closed and restarted each time the application is re-run. For this
reason, it is highly recommended to develop code that can be compiled
serially even if you eventually intend to run in a fully distributed
environment. This does make the coding marginally more complex, but
believe me, it's worth the effort. The vast majority of your code will
be the same for either case. Make sure to use the configuration flag to
\code{--enable-debug} while configuring (see Section \ref{configuring}). 

\subsection{Debugging with PVM}
\label{debugging-PVM}
If you wish to venture into debugging your distributed application, then you
simply need to set the parameter \code{*\_debug}, where * is the name of the
module you wish to debug, to ``1'' in the parameter file. This will tell PVM
to spawn the particular process or processes in question under a debugger.
What PVM actually does in this case is to launch the script
\code{\$PVM\_ROOT/lib/debugger}. You will undoubtedly want to modify this
script to launch your preferred debugger in the manner you deem fit. If you
have trouble with this, please send e-mail to the list serve (see Section
\ref{resources}).

It's a little tricky to debug interacting parallel processes. The main
difficulty is in that the order of operations is difficult to control. Random
interactions can occur when processes run in parallel due to varying system
loads, process priorities, etc. Therefore, it may not always be possible to
duplicate errors. To force runs that you should be able to reproduce, make
sure the parameter \ptt{no\_cut\_timeout} appears in the parameter file or
start \BB\ with the \code{-a} option. This will keep the cut generator from
timing out, a major source of randomness. Furthermore, run with only one
active node allowed at a time (set \ptt{ max\_active\_nodes} to ``1''). This
will keep the tree search from becoming random. These two steps should allow
runs to be reproduced. You still have to be careful, but this should make
things easier.

%\subsection{Using \code{Purify} and \code{Quantify}}

%The makefile is already set up for compiling applications using {\tt
%purify} and {\tt quantify}. Simply set the paths to the executables
%and type ``{\tt make pall}'' or ``{\tt p*}'' where * is the module you
%want to purify. The executable name is the same as described in
%Section \ref{distributed-build}, but with a ``p'' in front of it. To tell PVM
%to launch the purified version of the executables, you must set the
%parameters {\tt *\_exe} in the parameter file to the purified
%executable names. See Section \ref{tm_params} for information on
%setting parameters in the parameter file.

\subsection{Checking the Validity of Cuts and Tracing the Optimal Path}
\label{debugging}

Sometimes the only evidence of a bug is the fact that the optimal solution to
a particular problem is never found. This is usually caused by either (1)
adding an invalid cut, or (2) performing an invalid branching. There are two
options available for discovering such errors. The first is for checking the
validity of added cuts. This checking must, of course, be done by the user,
but \BB\ can facilitate such checking. To do this, the user must fill in the
function \hyperref{{\tt user\_check\_validity\_of\_cut()}} {\ptt{
user\_check\_validity\_of\_cut()} (see Section
}{)}{user_check_validity_of_cut}. THIS function is called every time a cut is
passed from the cut generator to the LP and can function as an independent
verifier. To do this, the user must pass (through her own data structures) a
known feasible solution. Then for each cut passed into the function, the user
can check whether the cut is satisfied by the feasible solution. If not, then
there is a problem! Of course, the problem could also be with the checking
routine. To enable this functionality, the user must configure SYMPHONY with
the flag \code{--enable-cut-check} (see Section \ref{configuring}). 

Tracing the optimal path can alert the user when the subproblem which admits a
particular known feasible solution (at least according to the branching
restrictions that have been imposed so far) is pruned. This could be due to an
invalid branching. Note that this option currently only works for branching on
binary variables. To use this facility, the user must fill in the function
\hyperref{{\tt user\_send\_feas\_sol()}} {\ptt {user\_send\_feas\_sol()} (see
Section }{)}{user_send_feas_sol}. All that is required is to pass out an array
of user indices that are in the feasible solution that you want to trace. Each
time the subproblem which admits this feasible solution is branched on, the
branch that continues to admit the solution is marked. When one of these
marked subproblems is pruned, the user is notified. To enable this
functionality, the user must configure SYMPHONY with the flag
\code{--enable-trace-path} (see Section \ref{configuring}). 


\subsection{Using the Interactive Graph Drawing Software}
\label{IGD}
The Interactive Graph Drawing (IGD) software package is included with
\BB\ and \BB\ facilitates its use through interfaces with the
package. The package, which is a Tcl/Tk application, is extremely
useful for developing and debugging applications involving graph-based
problems. Given display coordinates for each node in the graph, IGD
can display support graphs corresponding to fractional solutions with or
without edge weights and node labels and weights, as well as other
information. Furthermore, the user can interactively modify the graph
by, for instance, moving the nodes apart to ``disentangle'' the
edges. The user can also interactively enter violated cuts through the
IGD interface.

To use IGD, you must have installed PVM since the drawing window runs
as a separate application and communicates with the user's routines
through message passing. To compile the graph drawing application,
type \code{make dg} in the \BB\ root directory. The user
routines in the file \code{user\_dg.c} can be filled in, but it is not
necessary to fill anything in for basic applications. 

After compiling \code{dg}, the user must write some subroutines that
communicate with \code{dg} and cause the graph to be drawn.
Regrettably, this is currently a little more complicated than it needs
to be and is not well documented. However, by looking at the sample
application, it should be possible to see how it is done. To
enable graph drawing, put the line {\ptt {do\_draw\_graph 1} into the
parameter file or use the \code{-d} command line option. It can be difficult to
get IGD to work. If you are interested in using it and cannot get it to work,
feel free to contact me.

\subsection{Other Debugging Techniques}

Another useful built-in function is \code{write\_mps()}, which will write the
current LP relaxation to a file in MPS format. This file can then be read into
the LP solver interactively or examined by hand for errors.  Many times, CPLEX
gives much more explicit error messages interactively than through the
callable library. The form of the function is
{\color{Brown}
\begin{verbatim}
void write_mps(LPdata *lp_data, char *fname)
\end{verbatim}
} where \code{fname} is the name of the file to be written. If \BB\ is forced
to abandon solution of an LP because the LP solver returns an error code, the
current LP relaxation is automatically written to the file
\code{matrix.[bc\_index].[iter\_num].mps} where \code{bc\_index} is the index
of the current subproblem and \code{iter\_num} is the current iteration
number. The \code{write\_mps()} function can be called using breakpoint code
to examine the status of the matrix at any point during execution.

Logging is another useful feature. Logging the state of the search tree can
help isolate some problems more easily. See Section \ref{tm_params}
for the appropriate parameter settings to use logging.

\section{Case Study: Implementing a Matching Solver}

This section was contributed by Michael Trick a few years ago and is a
walkthrough of the steps for developing a very simple application using
SYMPHONY. Rather than presenting the code in its final version, we will go
through the steps that a user would go through. Note that some of the code is
lifted from the vehicle routing application. This code is designed to be a
sequential code. The MATCH application discussed here is part of the SYMPHONY
distribution and the source code can be found in the
\code{SYMPHONY/Applications/MATCH} directory.

The goal is to create a minimum matching on a complete graph. Initially, we
will just formulate this as an integer program with one variable for each
possible pair that can be matched. Then we will include a set of constraints
that can be added by cut generation.

We begin with the template code in the \code{USER} subdirectory included with
SYMPHONY. This gives stubs for each user callback routine. First, I need to
define a data structure for describing an instance of the matching problem. We
use the template structure \code{USER\_PROBLEM} in the file
\code{include/user.h} for this purpose.  To describe an instance, we just
need the number of nodes and the cost matrix. In addition, we also need a way
of assigning an index to each possible assignment. Here is the data
structure: 
{\color{Brown}
\begin{verbatim}
typedef struct USER_PROBLEM{
   int              numnodes;
   int              cost[MAXNODES][MAXNODES];
   int              match1[MAXNODES*(MAXNODES-1)/2];
   int              match2[MAXNODES*(MAXNODES-1)/2]; 
   int              index[MAXNODES][MAXNODES];
}user_problem;
\end{verbatim}
}
The fields \code{match1}, \code{match2}, and
\code{index} will be used later in the code in order to map variables to the
corresponding assignment and vice versa. 

Next, we need to read in the problem instance. We could implement this
function within the \code{user\_io()} callback function (see the file
\code{user\_master.c}). However, in order to show how it can be done
explicitly, we will define our own function \code{match\_read\_data()} in
\code{user\_main.c} to fill in the user data structure and then use
\code{sym\_set\_user\_data()} to pass this structure to SYMPHONY. The
template code already provides basic command-line options for the user. The
``-F'' flag is used to specify the location of a data file, from which we will
read in the data. The datafile contains first the number of nodes in the graph
(\code{nnodes}) followed by the pairwise cost matrix (nnode by nnode). We
read the file in with the \code{match\_read\_data()} routine in
\code{user\_main.c}:

%FIXME: Here, we don't need to pass in the user data structure...just return
%it. We also don't need to pass in the sym_enviroment 

{\color{Brown}
\begin{verbatim}
int match_read_data(user_problem *prob, char *infile)
{
   int i, j;
   FILE *f = NULL;

   if ((f = fopen(infile, "r")) == NULL){
      printf("main(): user file %s can't be opened\n", infile);
      return(ERROR__USER); 
   }

   /* Read in the costs */
   fscanf(f,"%d",&(prob->numnodes));
   for (i = 0; i < prob->numnodes; i++)
      for (j = 0; j < prob->numnodes; j++)
         fscanf(f, "%d", &(prob->cost[i][j]));
   
   return (FUNCTION_TERMINATED_NORMALLY);
}
\end{verbatim}
}   

We can now construct the integer program itself. This is done by specifying
the constraint matrix and the rim vectors in sparse format. We will have a
variable for each possible assignment $(i,j)$ with $i<j$. We have a constraint
for each node $i$, so it can only me matched to one other node.

We define the IP in our other helper function \code{match\_load\_problem()}
in \code{user\_main.c}. In the first part of this routine, we will build a
description of the IP, and then in the second part, we will load this
representation to SYMPHONY through
\code{sym\_explicit\_load\_problem()}. Note that we could instead create a
description of each subproblem dynamically using the
\code{user\_create\_subproblem()} callback (see \code{user\_lp.c}), but
this is more complicated and unnecessary here.

{\color{Brown}
\begin{verbatim}
int match_load_problem(sym_environment *env, user_problem *prob){
   
   int i, j, index, n, m, nz, *matbeg, *matind;
   double *matval, *lb, *ub, *obj, *rhs, *rngval;
   char *sense, *is_int;
   
   /* set up the inital LP data */
   n = prob->numnodes*(prob->numnodes-1)/2;
   m = 2 * prob->numnodes;
   nz = 2 * n;

   /* Allocate the arrays */
   matbeg  = (int *) malloc((n + 1) * ISIZE);
   matind  = (int *) malloc((nz) * ISIZE);
   matval  = (double *) malloc((nz) * DSIZE);
   obj     = (double *) malloc(n * DSIZE);
   lb      = (double *) calloc(n, DSIZE);
   ub      = (double *) malloc(n * DSIZE);
   rhs     = (double *) malloc(m * DSIZE);
   sense   = (char *) malloc(m * CSIZE);
   rngval  = (double *) calloc(m, DSIZE);
   is_int  = (char *) malloc(n * CSIZE);
   
   /* Fill out the appropriate data structures -- each column has
      exactly two entries */
   index = 0;
   for (i = 0; i < prob->numnodes; i++) {
      for (j = i+1; j < prob->numnodes; j++) {
         prob->match1[index] = i; /*The first component of assignment 'index'*/
         prob->match2[index] = j; /*The second component of assignment 'index'*/
         /* So we can recover the index later */
         prob->index[i][j] = prob->index[j][i] = index;
         obj[index] = prob->cost[i][j]; /* Cost of assignment (i, j) */
         is_int[index] = TRUE;
         matbeg[index] = 2*index;
         matval[2*index] = 1;
         matval[2*index+1] = 1;
         matind[2*index] = i;
         matind[2*index+1] = j;
         ub[index] = 1.0;
         index++;
      }
   }
   matbeg[n] = 2 * n;
   
   /* set the initial right hand side */
   for (i = 0; i < m; i++) {
      rhs[i] = 1;
      sense[i] = 'E';
   }
   
   /* Load the problem to SYMPHONY */   
   sym_explicit_load_problem(env, n, m, matbeg, matind, matval, lb, ub, 
                             is_int, obj, 0, sense, rhs, rngval, true);
			     
   return (FUNCTION_TERMINATED_NORMALLY);

}
\end{verbatim}
}

Now, we are ready to gather everything in the \code{main()} routine in 
\code{user\_main()}. This will involve to create a SYMPHONY environment and 
a user data structure, read in the data, create the corresponding IP, 
load it to the environment and ask SYMPHONY to solve it 
(\code{CALL\_FUNCTION} is just a macro to take care of the return values):  

{\color{Brown}
\begin{verbatim}
int main(int argc, char **argv)
{
   int termcode;
   char * infile;

   /* Create a SYMPHONY environment */
   sym_environment *env = sym_open_environment();

   /* Create the data structure for storing the problem instance.*/
   user_problem *prob = (user_problem *)calloc(1, sizeof(user_problem));
   
   CALL_FUNCTION( sym_set_user_data(env, (void *)prob) );
   CALL_FUNCTION( sym_parse_command_line(env, argc, argv) );
   CALL_FUNCTION( sym_get_str_param(env, "infile_name", &infile));
   CALL_FUNCTION( match_read_data(prob, infile) );
   CALL_FUNCTION( match_load_problem(env, prob) );
   CALL_FUNCTION( sym_solve(env) );
   CALL_FUNCTION( sym_close_environment(env) );
   return(0);
}
\end{verbatim}
}

OK, that's it. That defines an integer program, and if you compile and
optimize it, the rest of the system will come together to solve this problem.
Here is a data file to use:
{\color{Brown}
\begin{verbatim}
6
0 1 1 3 3 3
1 0 1 3 3 3
1 1 0 3 3 3
3 3 3 0 1 1
3 3 3 1 0 1
3 3 3 1 1 0
\end{verbatim}
}

The optimal value is 5. To display the solution, we need to be able to map
back from variables to the nodes. That was the use of the \code{node1} and
\code{node2} parts of the \code{USER\_PROBLEM}. We can now use
\code{user\_display\_solution()} in \code{user\_master.c} to print 
out the solution:

{\color{Brown}
\begin{verbatim}
int user_display_solution(void *user, double lpetol, int varnum, int *indices,
                          double *values, double objval)
{
   /* This gives you access to the user data structure. */
   user_problem *prob = (user_problem *) user;
   int index;
 
   for (index = 0; index < varnum; index++){
      if (values[index] > lpetol) {
          printf("%2d matched with %2d at cost %6d\n",
                prob->node1[indices[index]],
                prob->node2[indices[index]],
                prob->cost[prob->node1[indices[index]]]
                [prob->node2[indices[index]]]);
      }	   
   }
   
   return(USER_SUCCESS);
}
\end{verbatim}
}

We will now update the code to include a crude cut generator. Of course, We
could go for a Gomory-Hu type odd-set separation (ala Gr\"otschel and Padberg)
but for the moment, let's just check for sets of size three with more than
value 1 among them (such a set defines a cut that requires at least one edge
out of any odd set). We can do this by brute force checking of triples, as
follows:

{\color{Brown}
\begin{verbatim}
int user_find_cuts(void *user, int varnum, int iter_num, int level,
                   int index, double objval, int *indices, double *values,
                   double ub, double etol, int *num_cuts, int *alloc_cuts, 
                   cut_data ***cuts)
{
   user_problem *prob = (user_problem *) user;
   double edge_val[200][200]; /* Matrix of edge values */
   int i, j, k, cutind[3];
   double cutval[3];
   
   int cutnum = 0;

   /* Allocate the edge_val matrix to zero (we could also just calloc it) */
   memset((char *)edge_val, 0, 200*200*ISIZE);
   
   for (i = 0; i < varnum; i++) {
      edge_val[prob->node1[indices[i]]][prob->node2[indices[i]]] = values[i];
   }
   
   for (i = 0; i < prob->nnodes; i++){
      for (j = i+1; j < prob->nnodes; j++){
         for (k = j+1; k < prob->nnodes; k++) {
            if (edge_val[i][j]+edge_val[j][k]+edge_val[i][k] > 1.0 + etol) {
               /* Found violated triangle cut */
               /* Form the cut as a sparse vector */
               cutind[0] = prob->index[i][j];
               cutind[1] = prob->index[j][k];
               cutind[2] = prob->index[i][k];
               cutval[0] = cutval[1] = cutval[2] = 1.0;
               cg_add_explicit_cut(3, cutind, cutval, 1.0, 0, 'L',
                                   TRUE, num_cuts, alloc_cuts, cuts);
               cutnum++;
            }
         }
      }
   }

   return(USER_SUCCESS);
}

\end{verbatim}
}

Note the call of \code{cg\_add\_explicit\_cut()}, which tells SYMPHONY about
any cuts found. If we now solve the matching problem on the sample data set,
the number of nodes in the branch and bound tree should just be 1 (rather than
3 without cut generation).


