# source:trunk/Vol/doc/volDoc.tex@126

Last change on this file since 126 was 126, checked in by barahon, 13 years ago

x

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