# Changeset 126

Ignore:
Timestamp:
Apr 19, 2007 2:46:44 PM (13 years ago)
Message:

x

File:
1 edited

### Legend:

Unmodified
 r79 \title{\bf An implementation of the Volume Algorithm} \author{Francisco Barahona and Laszlo Ladanyi} \date{June 7, 2006} \date{April 19, 2007} \maketitle Here we describe an implementation of the Volume algorithm (VA) originally presented in \cite{BA1}. The following sub-directories of {\tt COIN} contain the relevant pieces. The directory {\tt COIN/Vol} contains the core of the algorithm. The directory {\tt COIN/Examples/VolUfl} {\tt coin-Vol} contain the relevant pieces. The directory {\tt coin-Vol/Vol/src} contains the core of the algorithm. The directory {\tt coin-Vol/Vol/examples/VolUfl} contains the necessary files for solving uncapacitated facility location problems. The directory {\tt COIN/Examples/Volume-LP} contains code for problems. The directory \break {\tt coin-Vol/Vol/examples/Volume-LP} contains code for dealing with combinatorial linear programs. The directory {\tt COIN/Examples/VolLp} also contains code for combinatorial linear {\tt coin-Vol/Vol/examples/VolLp} also contains code for combinatorial linear programs, this implementation relies on other parts of {\tt COIN}, while the implementation in {\tt COIN/Examples/Volume-LP} is self-contained. the implementation in \break {\tt coin-Vol/Vol/examples/Volume-LP} is self-contained. In {\tt COIN/Osi/OsiVol} there is code to call the VA through {\tt OSI}. %The directory {\tt COIN/Clp/Samples} contains sample code for using %the VA followed by {\tt Clp}. The directory {\tt COIN/Examples/MaxCut} contains code for doing Branch-and-Cut based on the VA, this is applied to the Max-Cut problem. %The directory {\tt COIN/Examples/MaxCut} %contains code for doing Branch-and-Cut based on the VA, this is %applied to the Max-Cut problem. Now we give the details of each directory. We hope to receive reports about bugs and/or \section{{\tt COIN/Vol}} This directory contains the core of the algorithm, most users should not need to modify any of the files here. The files are {\tt INSTALL}, {\tt Makefile} and {\tt VolVolume.cpp}. The file {\tt INSTALL} contains information on how to compile and build the code, on Linux it is enough to type {\tt make}''. \section{{\tt coin-Vol}} Most users should not need to modify any of the files here. The file {\tt INSTALL} contains information on how to compile and build the code. \section{{\tt coin-Vol/Vol/src}} The algorithm is in {\tt VolVolume.cpp} and the header file is {\tt VolVolume.hpp} in the directory {\tt COIN/Vol/include}. \section{{\tt COIN/Examples/VolUfl}} {\tt VolVolume.hpp}. \section{{\tt coin-Vol/Vol/Examples/VolUfl}} We focus here on the {\it uncapacitated facility location problem} (UFLP) as an example of implementation, see \cite{BC} for some of the theoretical issues. The files here are {\tt INSTALL}, {\tt Makefile}, {\tt Makefile.ufl}, issues. The files here are {\tt INSTALL}, {\tt Makefile}, {\tt Makefile.in}, {\tt ufl.cpp}, {\tt ufl.hpp}, {\tt ufl.par} and {\tt data.gz}. The file {\tt INSTALL} contains information on how to compile and build. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{{\tt COIN/Examples/Volume-LP}} \section{{\tt coin-Vol/Vol/examples/Volume-LP}} Here we focus on {\it Combinatorial Linear Programs}, Initially this directory contains the files: {\tt README, Makefile, lp.hpp, lp.cpp, lp.par,} \goodbreak Initially this directory contains the files: {\tt README, Makefile, Makefile.in lp.hpp, lp.cpp, lp.par,} %\goodbreak {\tt data.mps.gz, lpc.h, lpc.cpp, reader.h, reader.cpp}. On a Unix system one should type {\tt make}'', {\tt gunzip data.mps.gz}'' and {\tt volume-lp}'' should type {\tt make}'' and {\tt volume-lp}'' to run the code. Then the code will run and produce the files {\tt primal.txt} and {\tt dual.txt} that contain approximate solutions to both the primal the code in {\tt reader.cpp}. \section{{\tt COIN/Examples/VolLp}} \section{{\tt coin-Vol/Vol/examples/VolLp}} This code treats linear programs in a similar way as it is done in {\tt COIN/Examples/Volume-LP}, the main difference is that this {\tt coin-Vol/Vol/examples/Volume-LP}, the main difference is that this code uses other components of {\tt COIN-OR} while the code in \goodbreak {\tt COIN/Examples/Volume-LP} is self contained. The files here are {\tt INSTALL, Makefile, \goodbreak {\tt coin-Vol/Vol/examples/Volume-LP} is self contained. The files here are {\tt INSTALL, Makefile, Makefile.in %\goodbreak Makefile.vollp, vollp.cpp}. The {\tt INSTALL} contains instructions on how to compile and build %by the VA calls dual simplex. \section{{\tt COIN/Examples/MaxCut}} This directory contains code for doing Branch-and-Cut based on the VA as in \cite{BL}. The code is specialized to the Max-Cut problem. %\section{{\tt COIN/Examples/MaxCut}} %This directory contains code for doing Branch-and-Cut based on the %VA as in \cite{BL}. The code is specialized to the Max-Cut problem.