source: trunk/Vol/doc/volDoc.tex @ 79

Last change on this file since 79 was 79, checked in by barahon, 14 years ago

new doc

File size: 22.7 KB
Line 
1\documentclass{article}
2
3\setlength{\evensidemargin}{.25in}
4\setlength{\oddsidemargin}{.25in}
5\setlength{\textwidth}{6.0in}
6%\setlength{\parindent}{0.25in}
7\setlength{\topmargin}{-0in}
8\setlength{\textheight}{8.0in}
9%\newtheorem{theorem}{Theorem}
10%\newtheorem{proposition}{Proposition}
11%\newtheorem{lemma}{Lemma}
12%\newtheorem{corollary}{Corollary}
13
14%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
15\begin{document}
16\bibliographystyle{siam}
17
18\title{\bf An implementation of the Volume Algorithm}
19\author{Francisco Barahona and Laszlo Ladanyi}
20\date{June 7, 2006}
21\maketitle
22
23%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
24\section{Introduction}
25
26Here we describe an implementation of the Volume algorithm (VA) originally
27presented in \cite{BA1}. The following sub-directories of
28{\tt COIN} contain the relevant pieces. The directory {\tt COIN/Vol}
29contains the core of the algorithm. The directory {\tt COIN/Examples/VolUfl}
30contains the necessary files for solving uncapacitated facility location
31problems. The directory {\tt COIN/Examples/Volume-LP} contains code for
32dealing with combinatorial linear programs. The directory
33{\tt COIN/Examples/VolLp} also contains code for combinatorial linear
34programs, this implementation relies on other parts of {\tt COIN}, while
35the implementation in {\tt COIN/Examples/Volume-LP} is self-contained.
36In {\tt COIN/Osi/OsiVol} there is code to call the VA through {\tt OSI}.
37%The directory {\tt COIN/Clp/Samples} contains sample code for using
38%the VA followed by {\tt Clp}.
39The directory {\tt COIN/Examples/MaxCut}
40contains code for doing Branch-and-Cut based on the VA, this is
41applied to the Max-Cut problem.
42
43Now we give the details of each directory. We hope to receive reports about bugs and/or
44successful experiences.
45
46
47\section{{\tt COIN/Vol}}
48This directory contains the core of the algorithm, most users should not need
49to modify any of the files here. The files are {\tt INSTALL}, {\tt Makefile}
50and {\tt VolVolume.cpp}. The file {\tt INSTALL} contains information on how
51to compile and build the code, on Linux it is enough to type ``{\tt make}''.
52The algorithm is in {\tt VolVolume.cpp} and the header file is
53{\tt VolVolume.hpp} in the directory {\tt COIN/Vol/include}.
54
55
56
57\section{{\tt COIN/Examples/VolUfl}}
58We focus here on the {\it uncapacitated facility location
59problem} (UFLP) as an example of implementation, see \cite{BC} for some of the theoretical
60issues. The files here are {\tt INSTALL}, {\tt Makefile}, {\tt Makefile.ufl},
61{\tt ufl.cpp}, {\tt ufl.hpp}, {\tt ufl.par} and {\tt data.gz}.
62The file {\tt INSTALL} contains information on how to compile and build.
63
64As a first step, a new user should be able to run the code ``as is''.
65This can also be used as a framework for Lagrangian relaxation. The user would
66have to modify the files {\tt ufl.hpp}, {\tt ufl.cpp}, {\tt ufl.par}, and {\tt
67data}, to produce an implementation for a different problem.
68
69
70Now we present the linear program used in \cite{BC}. This is
71
72\pagebreak[4]
73\begin{eqnarray}
74\min \sum c_{ij} x_{ij} & + & \sum f_i y_\label{fp1} \\
75\sum_i x_{ij} & = & 1, \hbox{ for all } j,  \label{fp2} \\
76x_{ij} & \leq & y_i, \hbox{ for all } i, j, \label{fp3} \\
77x_{ij} & \ge  & 0, \hbox{ for all } i, j,   \label{fp4} \\ 
78y_i    & \le  & 1, \hbox{ for all } i.      \label{fp5}
79\end{eqnarray}
80
81Here the variables $y$ correspond to the locations, and the variables $x$
82represent connections between customers and locations. Let $u_j$ be a set of
83Lagrange multipliers for equations (\ref{fp2}). When we dualize equations
84(\ref{fp2}), we obtain the {\it lagrangian problem}
85\begin{eqnarray*}
86L(u) & = & \min \sum \bar c_{ij} x_{ij} + \sum \bar f_i y_i + \sum u_j, \\
87x_{ij} & \le & y_i, \hbox{ for all } i, j, \\
88x_{ij} & \ge & 0, \hbox{ for all } i, j, \\
89y_i    & \le & 1, \hbox{ for all } i.
90\end{eqnarray*}
91
92\noindent Where the {\it reduced costs} $\bar c_{ij}=c_{ij}-u_j$, and
93$\bar f_i = f_i$. We apply the VA to maximize $L(\cdot)$ and to produce a
94primal vector $(\bar x, \bar y)$ that is an approximate solution of
95(\ref{fp1})-(\ref{fp5}). Using this primal information we run a heuristic
96that gives an integer solution.
97
98In what follows we describe the different files in this directory.
99
100
101%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
102\subsection{{\tt ufl.par}}
103
104This file contains a set of parameters that control the algorithm and contain
105some information about the data. Each line has the format
106
107{\tt keyword=value}
108
109\noindent where {\tt keyword} should start in the first column. If we add any
110other character in the first column, the line is ignored or considered as a
111comment. The file looks as below
112
113\bigskip
114\begin{verbatim}
115fdata=data
116*dualfile=dual.txt
117dual_savefile=dual.txt
118int_savefile=int_sol.txt
119h_iter=100
120
121printflag=3
122printinvl=5
123heurinvl=10
124
125greentestinvl=1
126yellowtestinvl=4
127redtestinvl=10
128
129lambdainit=0.1
130alphainit=0.1
131alphamin=0.0001
132alphafactor=0.5
133alphaint=50
134
135maxsgriters=2000
136primal_abs_precision=0.02
137gap_abs_precision=0.
138gap_rel_precision=0.01
139granularity=0.
140\end{verbatim}
141
142The first group of parameters are specific to the UFLP and the user should
143define them. {\tt fdata} is the name of the file containing the data. {\tt
144dualfile} is the name of a file containing an initial dual vector. If we add
145an extra character at the beginning ({\tt *dualfile}) this line is ignored,
146this means that no initial dual vector is given. {\tt dual\_savefile} is the
147name of a file where we save the final dual vector. If this line is missing,
148then the dual vector is not saved. {\tt int\_savefile} is the name of a file
149to save the best integer solution found by the heuristic procedure, if this
150line is missing, then this vector is not saved. {\tt h\_iter} is the number of
151times that the heuristic is run after the VA has finished.
152
153The remaining parameters are specific to the VA. {\tt printflag} controls the
154level of output, it should be an integer between 0 and 5. {\tt printinvl=k}
155means that we print algorithm information every {\tt k} iterations. {\tt
156heurinvl=k} means that the primal heuristic is run every {\tt k} iterations.
157{\tt greentestinvl=k} means that after {\tt k} consecutive green iterations
158the value of $\lambda$ is multiplied by 2. {\tt yellowtestinvl=k} means that
159after {\tt k} consecutive yellow iterations the value of $\lambda$ is
160multiplied by 1.1. {\tt redtestinvl=k} means that after {\tt k} consecutive
161red iterations the value of $\lambda$ is multiplied by 0.67. {\tt lambdainit}
162is the initial value of $\lambda$. {\tt alphainit} is the initial value of
163$\alpha$. {\tt alphafactor=f} and {\tt alphaint=k} mean that every {\tt k}
164iterations we check if the objective function has increased by at least 1\%,
165if not we multiply $\alpha$ by {\tt f}.
166
167There are three termination criteria. First {\tt maxsgriter} is the maximum
168number of iterations. The second terminating criterion is as follows. {\tt
169primal\_abs\_precision} is the maximum primal violation to consider a primal
170vector ``near-feasible''. Let {\tt gap\_rel\_precision=$g$}, let $z$ be the
171value of the current dual solution, and $p$ be the value of a current
172near-feasible primal solution. If $|z| > 0.0001$ and
173$$
174        { | z - p | \over | z | } < g,
175$$
176then the algorithms stops. Let {\tt gap\_abs\_precision=$f$}, if $|z| \le
1770.0001$ and $| z - p | < f$ then we stop. Finally, let {\tt granularity=$k$},
178and let $U$ be the value of the best heuristic integer solution found. Then if
179$ U - z < k$ we stop.
180
181%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
182\subsection{{\tt data}}
183
184The file {\tt data} has the following format. On the first line we have the
185number of possible locations and the number of customers. On the next lines,
186the cost of opening each location appears, one cost per line. Then each of the
187remaining lines is like
188
189$
190i \quad j \quad d_{ij},
191$
192
193\noindent where $i$ refers to a location, $j$ refers to a customer, and
194$d_{ij}$ is the cost of serving customer $j$ from location $i$. The indices
195$i$ and $j$ start from 1. If a pair $i,j$ is missing then the cost $d_{ij}$ is
196set to $10^7$.
197
198
199%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
200\subsection{{\tt ufl.hpp}}
201
202This file contains C++ classes specific to the UFLP.
203
204First we have a class of parameters specific to the UFLP. The description
205of these parameters appears in the preceding section.
206
207\begin{verbatim}
208class UFL_parms {
209public:
210   string fdata;         // file with the data
211   string dualfile;      // file with an initial dual solution
212   string dual_savefile; // file to save final dual solution
213   string int_savefile;  // file to save primal integer solution
214   int h_iter;           // number of times that the primal heuristic will be
215                         // run after termination of the volume algorithm
216   
217   UFL_parms(const char* filename);
218   ~UFL_parms() {}
219};
220\end{verbatim}
221
222Before the next class we should mention the classes {\tt VOL\_dvector} and
223{\tt VOL\_ivector} defined in {\tt VolVolume.hpp}. The pseudo-code below
224illustrates their use.
225
226\begin{verbatim}
227int n=100;
228VOL_dvector x(n);  // a double vector with n entries
229x=0.;              // sets to 0. all entries of x
230VOL_dvector y;     // a double vector, it size remains to be set
231y.allocate(n);     // size is set
232y=x;               // copy each entry of x into y
233VOL_dvector z(y);  // a double vector of the same size as y,
234                   // all entries of y are copied into z
235x[0]=-1;           // first entry of x is set to -1
236y[0]=x[0];         // copy first entry of x into first entry of y
237\end{verbatim}
238
239The class {\tt VOL\_ivector} is used for vectors of {\tt int}. One can do the
240same operations as for {\tt VOL\_dvector}.
241
242Then we have a class containing the data for the UFLP.
243
244\begin{verbatim}
245class UFL_data { // original data for uncapacitated facility location
246public:
247   VOL_dvector fcost; // cost for opening facilities
248   VOL_dvector dist;  // cost for connecting a customer to a facility
249   VOL_dvector fix;   // vector saying if some variables should be fixed
250                      // if fix=-1 nothing is fixed
251   int ncust, nloc;   // number of customers, number of locations
252   VOL_ivector ix;    // best integer feasible solution so far
253   double      icost; // value of best integer feasible solution
254public:
255   UFL_data() : icost(DBL_MAX) {}
256   ~UFL\_data() {} 
257};
258\end{verbatim}
259
260Then we have
261
262\begin{verbatim}
263class UFL_hook : public VOL_user_hooks {
264public:
265   // for all hooks: return value of -1 means that volume should quit
266   // compute reduced costs
267   int compute_rc(void * user_data,
268                  const VOL_dvector& u, VOL_dvector& rc);
269   // solve lagrangian problem
270   int solve_subproblem(void * user_data,
271                        const VOL_dvector& u, const VOL_dvector& rc,
272                        double& lcost, VOL_dvector& x, VOL_dvector&v,
273                        double& pcost);
274   // primal heuristic
275   // return DBL_MAX in heur_val if feas sol wasn't/was found
276   int heuristics(void * user_data, const VOL_problem& p,
277                  const VOL_dvector& x, double& heur_val);
278};
279\end{verbatim}
280
281Here the function {\tt compute\_rc} is used to compute reduced costs. In the
282function {\tt solve\_subproblem} we solve the lagrangian problem. In {\tt
283heuristics} we run a heuristic to produce a primal integer solution.
284
285Finally in this file we have {\tt UFL\_parms::UFL\_parms(const char
286*filename)}, where we read the values for the members of {\tt UFL\_parms}.
287
288
289%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
290\subsection{{\tt ufl.cpp}}
291
292This file contains several functions that we describe below.
293
294First we have {\tt int main(int argc, char* argv[])}. In here we initialize
295the classes described in {\tt ufl.hpp}, and read the data. Then {\tt
296volp.psize()} is set to the number of primal variables, and {\tt volp.dsize()}
297is set to the number of dual variables. Then we check if a dual solution is
298provided and if so we read it.
299
300For the UFLP all relaxed constraints are equations, so the dual variables are
301unrestricted. In this case we do not have to set bounds for the dual
302variables. If we have inequalities of the type $ax \ge b$, then we have to set
303the lower bounds of their dual variables equal to 0. If we had constraints of
304the type type $ax \le b$, then we have to set the upper bounds of their
305variables equal to 0. This would be done as in the pseudo-code below.
306
307\begin{verbatim}
308// first the lower bounds to -inf, upper bounds to inf
309volp.dual_lb.allocate(volp.dsize);
310volp.dual_lb = -1e31;
311volp.dual_ub.allocate(volp.dsize);
312volp.dual_ub = 1e31;
313// now go through the relaxed constraints and change the lb of the ax >= b
314// constrains to 0, and change the ub of the ax <= b constrains to 0.
315for (i = 0; i < volp.dsize; ++i) {
316   if ("constraint i is '<=' ") {
317      volp.dual_ub[i] = 0;
318   }
319   if ("constraint i is '>=' ") {
320      volp.dual_lb[i] = 0;
321   }
322}
323\end{verbatim}
324
325The function {\tt volp.solve} invokes the VA. After completion we compute the
326violation of the fractional primal solution obtained. This vector is {\tt
327psol}. Then we check if the user provided the name of a file to save the dual
328solution. If so, we save it. Then we run the primal heuristic using {\tt psol}
329as an input. Notice that this heuristic has also been run periodically during
330the execution of the VA. Then if the user has provided the name of a file to
331save the integer heuristic solution, we do it. Finally the values of the
332solutions and some statistics are printed.
333
334The next function is {\tt void UFL\_read\_data(const char* fname, UFL\_data\&
335data)}, where we read the data. {\tt data.nloc} is the number of locations,
336{\tt data.ncust} is the number of customers. {\tt data.fcost} is a vector
337containing the cost of opening each location. {\tt data.dist} is a vector
338containing the cost of serving customers from facilities. All entries are
339initialized to $10^7$ and then particular entries are being set with the
340statement
341
342{\tt dist[(i-1)*ncust + j-1]=cost;}
343
344\noindent where {\tt i} is the index of a location and {\tt j} is the index
345of a customer. Here the indices start from 1. Finally we have a vector {\tt
346data.fix} associated with the locations. A particular entry is set to 0 if the
347location should be closed, it is set to 1 if it should be open, and it is set
348to -1 if this variable is free. Initially all entries are set to -1.
349
350In the function
351
352{\tt double solve\_it(void * user\_data, const double* rdist,
353VOL\_ivector\& sol)}
354
355\noindent we solve the lagrangian problem.
356We receive the data and reduced costs as input and return a primal vector. The
357solution is in the vector {\tt sol}. Its first {\tt n} entries correspond to
358the locations, then all remaining entries correspond to connections between
359locations and customers.
360
361In the function
362
363{\tt int UFL\_hook::compute\_rc(void * user\_data, const VOL\_dvector\& u,
364VOL\_dvector\& rc)}
365
366\noindent we compute the reduced costs. They will be used to solve the
367lagrangian problem.
368
369In the function
370
371\begin{verbatim}
372   int
373   UFL_hook::solve_subproblem(void *user_data,
374                              const VOL_dvector& u, const VOL_dvector& rc,
375                              double& lcost, VOL_dvector& x,
376                              VOL_dvector& v, double& pcost)
377\end{verbatim}
378
379\noindent we compute the lagrangian value, we call {\tt solve\_it}, we compute
380the objective value and the vector $v$ defined as follows. If $\hat x$ is the
381primal solution given by {\tt solve\_it}, and $Ax \sim b$ is the set of
382relaxed constraints, then the difference $v$ is $$v = b - A \hat x.$$
383
384The last function in this file is
385\begin{verbatim}
386   int
387   UFL_hook::heuristics(void * user_data, const VOL_problem& p,
388                        const VOL_dvector& x, double& icost)
389\end{verbatim}
390
391\noindent where we run the following simple heuristic.
392Given a fractional solution $(\bar x, \bar y)$, let $\bar y_i$ be the variable
393associated with location $i$. We pick a random number $r \in [ 0, 1 ]$ and if
394$r < \bar y_i$ facility $i$ is open, and closed otherwise. We repeat this for
395every facility, then given the set of open facilities we find a minimum cost
396assignment of customers. This function is invoked periodically in the VA and
397by the main program after the VA has finished.
398
399%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
400
401\section{{\tt COIN/Examples/Volume-LP}}
402
403Here we focus on {\it Combinatorial Linear Programs},
404these are linear programs where the matrix has 0, 1, -1 coefficients
405and the variables are bounded between 0 and 1. The VA has been very
406effective at producing fast approximate solutions to these LPs, see
407\cite{BA2}.
408As a first step, a new user should be able to run our code ``as is''.
409The input should be an MPS file.
410
411
412Initially this directory contains the files: {\tt README, Makefile,
413lp.hpp, lp.cpp, lp.par,} \goodbreak
414{\tt data.mps.gz, lpc.h, lpc.cpp,
415reader.h, reader.cpp}. On a Unix system one
416should type ``{\tt make}'', ``{\tt gunzip data.mps.gz}'' and ``{\tt volume-lp}''
417to run the code. Then the code will run and produce the files {\tt primal.txt}
418and {\tt dual.txt} that contain approximate solutions to both the primal
419and the dual problem.
420
421\smallskip
422
423We assume that we have an LP like
424\begin{eqnarray}
425&\min c x  \label{fp1x} \\
426&Ax \sim b \label{fp2x} \\
427&l \leq x \le u. \label{fp3x} 
428\end{eqnarray}
429
430Let $\pi$ be a set of
431Lagrange multipliers for constraints (\ref{fp2x}). When we dualize
432them we obtain the {\it lagrangian problem}
433
434\begin{eqnarray*}
435L(u) & = & \min (c-\pi A) x + \pi b, \\
436&&l \leq x \le u.
437\end{eqnarray*}
438
439We apply the VA to maximize $L(\cdot)$ and to produce a
440dual vector $\bar \pi$, and
441primal vector $\bar x$ that is an approximate solution of
442(\ref{fp1x})-(\ref{fp3x}).
443
444In what follows we describe the files {\tt lp.par} and
445{\tt data.mps}.
446
447
448%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
449\subsection{{\tt lp.par}}
450
451This file contains a set of parameters that control the algorithm and contain
452information about the data. Each line has the format
453
454{\tt keyword=value}
455
456\noindent where {\tt keyword} should start in the first column. If we add any
457other character in the first column, the line is ignored or considered as a
458comment. The file looks as below
459
460\bigskip
461\begin{verbatim}
462fdata=data.mps
463*dualfile=dual.txt
464dual_savefile=dual.txt
465primal_savefile=primal.txt
466h_iter=0
467var_ub=1.0
468
469
470printflag=3
471printinvl=20
472heurinvl=100000000
473
474greentestinvl=2
475yellowtestinvl=2
476redtestinvl=10
477
478lambdainit=0.1
479alphainit=0.01
480alphamin=0.0001
481alphafactor=0.5
482alphaint=80
483
484maxsgriters=2000
485primal_abs_precision=0.02
486gap_abs_precision=0.
487gap_rel_precision=0.01
488granularity=0.
489
490\end{verbatim}
491
492The first group of parameters are specific to LP and the user should
493define them. {\tt fdata} is the name of the file containing the data. {\tt
494dualfile} is the name of a file containing an initial dual vector. If we add
495an extra character at the beginning ({\tt *dualfile}) this line is ignored,
496this means that no initial dual vector is given. {\tt dual\_savefile} is the
497name of a file where we save the final dual vector. If this line is missing,
498then the dual vector is not saved. {\tt primal\_savefile} is the name of a file
499to save the primal solution, if this
500line is missing, then this vector is not saved. {\tt h\_iter} is the number of
501times that the heuristic is run after the VA has finished. We did not include
502a heuristic in this implementation. {\tt var\_ub} is an upper bound
503for all primal variables, for 0-1 problems we set {\tt var\_ub=1}.
504
505The remaining parameters are specific to the VA. {\tt printflag} controls the
506level of output, it should be an integer between 0 and 5. {\tt printinvl=k}
507means that we print algorithm information every {\tt k} iterations. {\tt
508heurinvl=k} means that the primal heuristic is run every {\tt k} iterations.
509{\tt greentestinvl=k} means that after {\tt k} consecutive green iterations
510the value of $\lambda$ is multiplied by 2. {\tt yellowtestinvl=k} means that
511after {\tt k} consecutive yellow iterations the value of $\lambda$ is
512multiplied by 1.1. {\tt redtestinvl=k} means that after {\tt k} consecutive
513red iterations the value of $\lambda$ is multiplied by 0.67. {\tt lambdainit}
514is the initial value of $\lambda$. {\tt alphainit} is the initial value of
515$\alpha$. {\tt alphafactor=f} and {\tt alphaint=k} mean that every {\tt k}
516iterations we check if the objective function has increased by at least 1\%,
517if not we multiply $\alpha$ by {\tt f}.
518
519There are three termination criteria. First {\tt maxsgriter} is the maximum
520number of iterations. The second terminating criterion is as follows. {\tt
521primal\_abs\_precision} is the maximum primal violation to consider a primal
522vector ``near-feasible''. Let {\tt gap\_rel\_precision=$g$}, let $z$ be the
523value of the current dual solution, and $p$ be the value of a current
524near-feasible primal solution. If $|z| > 0.0001$ and
525$$
526        { | z - p | \over | z | } < g,
527$$
528then the algorithms stops. Let {\tt gap\_abs\_precision=$f$}, if $|z| \le
5290.0001$ and $| z - p | < f$ then we stop. Finally, let {\tt granularity=$k$},
530and let $U$ be the value of the best heuristic integer solution found. Then if
531$ U - z < k$ we stop. We did not include any heuristic in this
532implementation.
533
534\subsection{{\tt data.mps}}
535
536This is an MPS file that is read with code in {\tt reader.cpp}.
537If a different type of input has to be used, one should change
538the code in {\tt reader.cpp}.
539
540\section{{\tt COIN/Examples/VolLp}}
541
542This code treats linear programs in a similar way as it is done in
543{\tt COIN/Examples/Volume-LP}, the main difference is that this
544code uses other components of {\tt COIN-OR} while the code in \goodbreak
545{\tt COIN/Examples/Volume-LP} is self contained.
546The files here are {\tt INSTALL, Makefile, \goodbreak
547Makefile.vollp, vollp.cpp}.
548The {\tt INSTALL} contains instructions on how to compile and build
549the code. The input should be an MPS file.
550
551\section{{\tt COIN/Osi/OsiVol}}
552
553In this directory there is the file {\tt OsiVolSolverInterface.cpp}
554that allows the user to call the VA through {\tt OSI}. This is also
555intended to deal with combinatorial linear programs. The code below
556reads an MPS file and calls the VA through OSI.
557
558\begin{verbatim}
559#include "OsiVolSolverInterface.hpp"
560
561#include <iostream>
562
563int main(int argc, char *argv[])
564{
565   
566    OsiVolSolverInterface osilp;
567   
568    osilp.readMps("file","mps");
569   
570    osilp.initialSolve();
571
572    const int numCols=osilp.getNumCols();
573    const double *x=osilp.getColSolution();
574    for (int j=0; j<numCols; ++j){
575        std::cout << j << " " << x[j] << "\n";
576    }
577   
578    return 0;
579} 
580\end{verbatim}
581
582%\section{{\tt COIN/Clp/Samples}}
583%
584%This directory contains the code {\tt useVolume.cpp}. This code reads
585%an MPS file, calls the VA and then using the dual solution produced
586%by the VA calls dual simplex.
587
588\section{{\tt COIN/Examples/MaxCut}}
589
590This directory contains code for doing Branch-and-Cut based on the
591VA as in \cite{BL}. The code is specialized to the Max-Cut problem.
592
593
594\bibliography{volDoc}
595
596\end{document}
597
598
Note: See TracBrowser for help on using the repository browser.