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 | |
---|
26 | Here we describe an implementation of the Volume algorithm (VA) originally |
---|
27 | presented in \cite{BA1}. The following sub-directories of |
---|
28 | {\tt COIN} contain the relevant pieces. The directory {\tt COIN/Vol} |
---|
29 | contains the core of the algorithm. The directory {\tt COIN/Examples/VolUfl} |
---|
30 | contains the necessary files for solving uncapacitated facility location |
---|
31 | problems. The directory {\tt COIN/Examples/Volume-LP} contains code for |
---|
32 | dealing with combinatorial linear programs. The directory |
---|
33 | {\tt COIN/Examples/VolLp} also contains code for combinatorial linear |
---|
34 | programs, this implementation relies on other parts of {\tt COIN}, while |
---|
35 | the implementation in {\tt COIN/Examples/Volume-LP} is self-contained. |
---|
36 | In {\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 | |
---|
43 | Now we give the details of each directory. We hope to receive reports about bugs and/or |
---|
44 | successful experiences. |
---|
45 | |
---|
46 | |
---|
47 | \section{{\tt COIN/Vol}} |
---|
48 | This directory contains the core of the algorithm, most users should not need |
---|
49 | to modify any of the files here. The files are {\tt INSTALL}, {\tt Makefile} |
---|
50 | and {\tt VolVolume.cpp}. The file {\tt INSTALL} contains information on how |
---|
51 | to compile and build the code, on Linux it is enough to type ``{\tt make}''. |
---|
52 | The 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}} |
---|
58 | We focus here on the {\it uncapacitated facility location |
---|
59 | problem} (UFLP) as an example of implementation, see \cite{BC} for some of the theoretical |
---|
60 | issues. 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}. |
---|
62 | The file {\tt INSTALL} contains information on how to compile and build. |
---|
63 | |
---|
64 | As a first step, a new user should be able to run the code ``as is''. |
---|
65 | This can also be used as a framework for Lagrangian relaxation. The user would |
---|
66 | have to modify the files {\tt ufl.hpp}, {\tt ufl.cpp}, {\tt ufl.par}, and {\tt |
---|
67 | data}, to produce an implementation for a different problem. |
---|
68 | |
---|
69 | |
---|
70 | Now 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_i \label{fp1} \\ |
---|
75 | \sum_i x_{ij} & = & 1, \hbox{ for all } j, \label{fp2} \\ |
---|
76 | x_{ij} & \leq & y_i, \hbox{ for all } i, j, \label{fp3} \\ |
---|
77 | x_{ij} & \ge & 0, \hbox{ for all } i, j, \label{fp4} \\ |
---|
78 | y_i & \le & 1, \hbox{ for all } i. \label{fp5} |
---|
79 | \end{eqnarray} |
---|
80 | |
---|
81 | Here the variables $y$ correspond to the locations, and the variables $x$ |
---|
82 | represent connections between customers and locations. Let $u_j$ be a set of |
---|
83 | Lagrange multipliers for equations (\ref{fp2}). When we dualize equations |
---|
84 | (\ref{fp2}), we obtain the {\it lagrangian problem} |
---|
85 | \begin{eqnarray*} |
---|
86 | L(u) & = & \min \sum \bar c_{ij} x_{ij} + \sum \bar f_i y_i + \sum u_j, \\ |
---|
87 | x_{ij} & \le & y_i, \hbox{ for all } i, j, \\ |
---|
88 | x_{ij} & \ge & 0, \hbox{ for all } i, j, \\ |
---|
89 | y_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 |
---|
94 | primal vector $(\bar x, \bar y)$ that is an approximate solution of |
---|
95 | (\ref{fp1})-(\ref{fp5}). Using this primal information we run a heuristic |
---|
96 | that gives an integer solution. |
---|
97 | |
---|
98 | In what follows we describe the different files in this directory. |
---|
99 | |
---|
100 | |
---|
101 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
102 | \subsection{{\tt ufl.par}} |
---|
103 | |
---|
104 | This file contains a set of parameters that control the algorithm and contain |
---|
105 | some 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 |
---|
110 | other character in the first column, the line is ignored or considered as a |
---|
111 | comment. The file looks as below |
---|
112 | |
---|
113 | \bigskip |
---|
114 | \begin{verbatim} |
---|
115 | fdata=data |
---|
116 | *dualfile=dual.txt |
---|
117 | dual_savefile=dual.txt |
---|
118 | int_savefile=int_sol.txt |
---|
119 | h_iter=100 |
---|
120 | |
---|
121 | printflag=3 |
---|
122 | printinvl=5 |
---|
123 | heurinvl=10 |
---|
124 | |
---|
125 | greentestinvl=1 |
---|
126 | yellowtestinvl=4 |
---|
127 | redtestinvl=10 |
---|
128 | |
---|
129 | lambdainit=0.1 |
---|
130 | alphainit=0.1 |
---|
131 | alphamin=0.0001 |
---|
132 | alphafactor=0.5 |
---|
133 | alphaint=50 |
---|
134 | |
---|
135 | maxsgriters=2000 |
---|
136 | primal_abs_precision=0.02 |
---|
137 | gap_abs_precision=0. |
---|
138 | gap_rel_precision=0.01 |
---|
139 | granularity=0. |
---|
140 | \end{verbatim} |
---|
141 | |
---|
142 | The first group of parameters are specific to the UFLP and the user should |
---|
143 | define them. {\tt fdata} is the name of the file containing the data. {\tt |
---|
144 | dualfile} is the name of a file containing an initial dual vector. If we add |
---|
145 | an extra character at the beginning ({\tt *dualfile}) this line is ignored, |
---|
146 | this means that no initial dual vector is given. {\tt dual\_savefile} is the |
---|
147 | name of a file where we save the final dual vector. If this line is missing, |
---|
148 | then the dual vector is not saved. {\tt int\_savefile} is the name of a file |
---|
149 | to save the best integer solution found by the heuristic procedure, if this |
---|
150 | line is missing, then this vector is not saved. {\tt h\_iter} is the number of |
---|
151 | times that the heuristic is run after the VA has finished. |
---|
152 | |
---|
153 | The remaining parameters are specific to the VA. {\tt printflag} controls the |
---|
154 | level of output, it should be an integer between 0 and 5. {\tt printinvl=k} |
---|
155 | means that we print algorithm information every {\tt k} iterations. {\tt |
---|
156 | heurinvl=k} means that the primal heuristic is run every {\tt k} iterations. |
---|
157 | {\tt greentestinvl=k} means that after {\tt k} consecutive green iterations |
---|
158 | the value of $\lambda$ is multiplied by 2. {\tt yellowtestinvl=k} means that |
---|
159 | after {\tt k} consecutive yellow iterations the value of $\lambda$ is |
---|
160 | multiplied by 1.1. {\tt redtestinvl=k} means that after {\tt k} consecutive |
---|
161 | red iterations the value of $\lambda$ is multiplied by 0.67. {\tt lambdainit} |
---|
162 | is 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} |
---|
164 | iterations we check if the objective function has increased by at least 1\%, |
---|
165 | if not we multiply $\alpha$ by {\tt f}. |
---|
166 | |
---|
167 | There are three termination criteria. First {\tt maxsgriter} is the maximum |
---|
168 | number of iterations. The second terminating criterion is as follows. {\tt |
---|
169 | primal\_abs\_precision} is the maximum primal violation to consider a primal |
---|
170 | vector ``near-feasible''. Let {\tt gap\_rel\_precision=$g$}, let $z$ be the |
---|
171 | value of the current dual solution, and $p$ be the value of a current |
---|
172 | near-feasible primal solution. If $|z| > 0.0001$ and |
---|
173 | $$ |
---|
174 | { | z - p | \over | z | } < g, |
---|
175 | $$ |
---|
176 | then the algorithms stops. Let {\tt gap\_abs\_precision=$f$}, if $|z| \le |
---|
177 | 0.0001$ and $| z - p | < f$ then we stop. Finally, let {\tt granularity=$k$}, |
---|
178 | and 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 | |
---|
184 | The file {\tt data} has the following format. On the first line we have the |
---|
185 | number of possible locations and the number of customers. On the next lines, |
---|
186 | the cost of opening each location appears, one cost per line. Then each of the |
---|
187 | remaining lines is like |
---|
188 | |
---|
189 | $ |
---|
190 | i \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 |
---|
196 | set to $10^7$. |
---|
197 | |
---|
198 | |
---|
199 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
200 | \subsection{{\tt ufl.hpp}} |
---|
201 | |
---|
202 | This file contains C++ classes specific to the UFLP. |
---|
203 | |
---|
204 | First we have a class of parameters specific to the UFLP. The description |
---|
205 | of these parameters appears in the preceding section. |
---|
206 | |
---|
207 | \begin{verbatim} |
---|
208 | class UFL_parms { |
---|
209 | public: |
---|
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 | |
---|
222 | Before 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 |
---|
224 | illustrates their use. |
---|
225 | |
---|
226 | \begin{verbatim} |
---|
227 | int n=100; |
---|
228 | VOL_dvector x(n); // a double vector with n entries |
---|
229 | x=0.; // sets to 0. all entries of x |
---|
230 | VOL_dvector y; // a double vector, it size remains to be set |
---|
231 | y.allocate(n); // size is set |
---|
232 | y=x; // copy each entry of x into y |
---|
233 | VOL_dvector z(y); // a double vector of the same size as y, |
---|
234 | // all entries of y are copied into z |
---|
235 | x[0]=-1; // first entry of x is set to -1 |
---|
236 | y[0]=x[0]; // copy first entry of x into first entry of y |
---|
237 | \end{verbatim} |
---|
238 | |
---|
239 | The class {\tt VOL\_ivector} is used for vectors of {\tt int}. One can do the |
---|
240 | same operations as for {\tt VOL\_dvector}. |
---|
241 | |
---|
242 | Then we have a class containing the data for the UFLP. |
---|
243 | |
---|
244 | \begin{verbatim} |
---|
245 | class UFL_data { // original data for uncapacitated facility location |
---|
246 | public: |
---|
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 |
---|
254 | public: |
---|
255 | UFL_data() : icost(DBL_MAX) {} |
---|
256 | ~UFL\_data() {} |
---|
257 | }; |
---|
258 | \end{verbatim} |
---|
259 | |
---|
260 | Then we have |
---|
261 | |
---|
262 | \begin{verbatim} |
---|
263 | class UFL_hook : public VOL_user_hooks { |
---|
264 | public: |
---|
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 | |
---|
281 | Here the function {\tt compute\_rc} is used to compute reduced costs. In the |
---|
282 | function {\tt solve\_subproblem} we solve the lagrangian problem. In {\tt |
---|
283 | heuristics} we run a heuristic to produce a primal integer solution. |
---|
284 | |
---|
285 | Finally 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 | |
---|
292 | This file contains several functions that we describe below. |
---|
293 | |
---|
294 | First we have {\tt int main(int argc, char* argv[])}. In here we initialize |
---|
295 | the classes described in {\tt ufl.hpp}, and read the data. Then {\tt |
---|
296 | volp.psize()} is set to the number of primal variables, and {\tt volp.dsize()} |
---|
297 | is set to the number of dual variables. Then we check if a dual solution is |
---|
298 | provided and if so we read it. |
---|
299 | |
---|
300 | For the UFLP all relaxed constraints are equations, so the dual variables are |
---|
301 | unrestricted. In this case we do not have to set bounds for the dual |
---|
302 | variables. If we have inequalities of the type $ax \ge b$, then we have to set |
---|
303 | the lower bounds of their dual variables equal to 0. If we had constraints of |
---|
304 | the type type $ax \le b$, then we have to set the upper bounds of their |
---|
305 | variables 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 |
---|
309 | volp.dual_lb.allocate(volp.dsize); |
---|
310 | volp.dual_lb = -1e31; |
---|
311 | volp.dual_ub.allocate(volp.dsize); |
---|
312 | volp.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. |
---|
315 | for (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 | |
---|
325 | The function {\tt volp.solve} invokes the VA. After completion we compute the |
---|
326 | violation of the fractional primal solution obtained. This vector is {\tt |
---|
327 | psol}. Then we check if the user provided the name of a file to save the dual |
---|
328 | solution. If so, we save it. Then we run the primal heuristic using {\tt psol} |
---|
329 | as an input. Notice that this heuristic has also been run periodically during |
---|
330 | the execution of the VA. Then if the user has provided the name of a file to |
---|
331 | save the integer heuristic solution, we do it. Finally the values of the |
---|
332 | solutions and some statistics are printed. |
---|
333 | |
---|
334 | The next function is {\tt void UFL\_read\_data(const char* fname, UFL\_data\& |
---|
335 | data)}, 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 |
---|
337 | containing the cost of opening each location. {\tt data.dist} is a vector |
---|
338 | containing the cost of serving customers from facilities. All entries are |
---|
339 | initialized to $10^7$ and then particular entries are being set with the |
---|
340 | statement |
---|
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 |
---|
345 | of a customer. Here the indices start from 1. Finally we have a vector {\tt |
---|
346 | data.fix} associated with the locations. A particular entry is set to 0 if the |
---|
347 | location should be closed, it is set to 1 if it should be open, and it is set |
---|
348 | to -1 if this variable is free. Initially all entries are set to -1. |
---|
349 | |
---|
350 | In the function |
---|
351 | |
---|
352 | {\tt double solve\_it(void * user\_data, const double* rdist, |
---|
353 | VOL\_ivector\& sol)} |
---|
354 | |
---|
355 | \noindent we solve the lagrangian problem. |
---|
356 | We receive the data and reduced costs as input and return a primal vector. The |
---|
357 | solution is in the vector {\tt sol}. Its first {\tt n} entries correspond to |
---|
358 | the locations, then all remaining entries correspond to connections between |
---|
359 | locations and customers. |
---|
360 | |
---|
361 | In the function |
---|
362 | |
---|
363 | {\tt int UFL\_hook::compute\_rc(void * user\_data, const VOL\_dvector\& u, |
---|
364 | VOL\_dvector\& rc)} |
---|
365 | |
---|
366 | \noindent we compute the reduced costs. They will be used to solve the |
---|
367 | lagrangian problem. |
---|
368 | |
---|
369 | In 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 |
---|
380 | the objective value and the vector $v$ defined as follows. If $\hat x$ is the |
---|
381 | primal solution given by {\tt solve\_it}, and $Ax \sim b$ is the set of |
---|
382 | relaxed constraints, then the difference $v$ is $$v = b - A \hat x.$$ |
---|
383 | |
---|
384 | The 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. |
---|
392 | Given a fractional solution $(\bar x, \bar y)$, let $\bar y_i$ be the variable |
---|
393 | associated 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 |
---|
395 | every facility, then given the set of open facilities we find a minimum cost |
---|
396 | assignment of customers. This function is invoked periodically in the VA and |
---|
397 | by the main program after the VA has finished. |
---|
398 | |
---|
399 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
400 | |
---|
401 | \section{{\tt COIN/Examples/Volume-LP}} |
---|
402 | |
---|
403 | Here we focus on {\it Combinatorial Linear Programs}, |
---|
404 | these are linear programs where the matrix has 0, 1, -1 coefficients |
---|
405 | and the variables are bounded between 0 and 1. The VA has been very |
---|
406 | effective at producing fast approximate solutions to these LPs, see |
---|
407 | \cite{BA2}. |
---|
408 | As a first step, a new user should be able to run our code ``as is''. |
---|
409 | The input should be an MPS file. |
---|
410 | |
---|
411 | |
---|
412 | Initially this directory contains the files: {\tt README, Makefile, |
---|
413 | lp.hpp, lp.cpp, lp.par,} \goodbreak |
---|
414 | {\tt data.mps.gz, lpc.h, lpc.cpp, |
---|
415 | reader.h, reader.cpp}. On a Unix system one |
---|
416 | should type ``{\tt make}'', ``{\tt gunzip data.mps.gz}'' and ``{\tt volume-lp}'' |
---|
417 | to run the code. Then the code will run and produce the files {\tt primal.txt} |
---|
418 | and {\tt dual.txt} that contain approximate solutions to both the primal |
---|
419 | and the dual problem. |
---|
420 | |
---|
421 | \smallskip |
---|
422 | |
---|
423 | We 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 | |
---|
430 | Let $\pi$ be a set of |
---|
431 | Lagrange multipliers for constraints (\ref{fp2x}). When we dualize |
---|
432 | them we obtain the {\it lagrangian problem} |
---|
433 | |
---|
434 | \begin{eqnarray*} |
---|
435 | L(u) & = & \min (c-\pi A) x + \pi b, \\ |
---|
436 | &&l \leq x \le u. |
---|
437 | \end{eqnarray*} |
---|
438 | |
---|
439 | We apply the VA to maximize $L(\cdot)$ and to produce a |
---|
440 | dual vector $\bar \pi$, and |
---|
441 | primal vector $\bar x$ that is an approximate solution of |
---|
442 | (\ref{fp1x})-(\ref{fp3x}). |
---|
443 | |
---|
444 | In what follows we describe the files {\tt lp.par} and |
---|
445 | {\tt data.mps}. |
---|
446 | |
---|
447 | |
---|
448 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
---|
449 | \subsection{{\tt lp.par}} |
---|
450 | |
---|
451 | This file contains a set of parameters that control the algorithm and contain |
---|
452 | information 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 |
---|
457 | other character in the first column, the line is ignored or considered as a |
---|
458 | comment. The file looks as below |
---|
459 | |
---|
460 | \bigskip |
---|
461 | \begin{verbatim} |
---|
462 | fdata=data.mps |
---|
463 | *dualfile=dual.txt |
---|
464 | dual_savefile=dual.txt |
---|
465 | primal_savefile=primal.txt |
---|
466 | h_iter=0 |
---|
467 | var_ub=1.0 |
---|
468 | |
---|
469 | |
---|
470 | printflag=3 |
---|
471 | printinvl=20 |
---|
472 | heurinvl=100000000 |
---|
473 | |
---|
474 | greentestinvl=2 |
---|
475 | yellowtestinvl=2 |
---|
476 | redtestinvl=10 |
---|
477 | |
---|
478 | lambdainit=0.1 |
---|
479 | alphainit=0.01 |
---|
480 | alphamin=0.0001 |
---|
481 | alphafactor=0.5 |
---|
482 | alphaint=80 |
---|
483 | |
---|
484 | maxsgriters=2000 |
---|
485 | primal_abs_precision=0.02 |
---|
486 | gap_abs_precision=0. |
---|
487 | gap_rel_precision=0.01 |
---|
488 | granularity=0. |
---|
489 | |
---|
490 | \end{verbatim} |
---|
491 | |
---|
492 | The first group of parameters are specific to LP and the user should |
---|
493 | define them. {\tt fdata} is the name of the file containing the data. {\tt |
---|
494 | dualfile} is the name of a file containing an initial dual vector. If we add |
---|
495 | an extra character at the beginning ({\tt *dualfile}) this line is ignored, |
---|
496 | this means that no initial dual vector is given. {\tt dual\_savefile} is the |
---|
497 | name of a file where we save the final dual vector. If this line is missing, |
---|
498 | then the dual vector is not saved. {\tt primal\_savefile} is the name of a file |
---|
499 | to save the primal solution, if this |
---|
500 | line is missing, then this vector is not saved. {\tt h\_iter} is the number of |
---|
501 | times that the heuristic is run after the VA has finished. We did not include |
---|
502 | a heuristic in this implementation. {\tt var\_ub} is an upper bound |
---|
503 | for all primal variables, for 0-1 problems we set {\tt var\_ub=1}. |
---|
504 | |
---|
505 | The remaining parameters are specific to the VA. {\tt printflag} controls the |
---|
506 | level of output, it should be an integer between 0 and 5. {\tt printinvl=k} |
---|
507 | means that we print algorithm information every {\tt k} iterations. {\tt |
---|
508 | heurinvl=k} means that the primal heuristic is run every {\tt k} iterations. |
---|
509 | {\tt greentestinvl=k} means that after {\tt k} consecutive green iterations |
---|
510 | the value of $\lambda$ is multiplied by 2. {\tt yellowtestinvl=k} means that |
---|
511 | after {\tt k} consecutive yellow iterations the value of $\lambda$ is |
---|
512 | multiplied by 1.1. {\tt redtestinvl=k} means that after {\tt k} consecutive |
---|
513 | red iterations the value of $\lambda$ is multiplied by 0.67. {\tt lambdainit} |
---|
514 | is 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} |
---|
516 | iterations we check if the objective function has increased by at least 1\%, |
---|
517 | if not we multiply $\alpha$ by {\tt f}. |
---|
518 | |
---|
519 | There are three termination criteria. First {\tt maxsgriter} is the maximum |
---|
520 | number of iterations. The second terminating criterion is as follows. {\tt |
---|
521 | primal\_abs\_precision} is the maximum primal violation to consider a primal |
---|
522 | vector ``near-feasible''. Let {\tt gap\_rel\_precision=$g$}, let $z$ be the |
---|
523 | value of the current dual solution, and $p$ be the value of a current |
---|
524 | near-feasible primal solution. If $|z| > 0.0001$ and |
---|
525 | $$ |
---|
526 | { | z - p | \over | z | } < g, |
---|
527 | $$ |
---|
528 | then the algorithms stops. Let {\tt gap\_abs\_precision=$f$}, if $|z| \le |
---|
529 | 0.0001$ and $| z - p | < f$ then we stop. Finally, let {\tt granularity=$k$}, |
---|
530 | and 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 |
---|
532 | implementation. |
---|
533 | |
---|
534 | \subsection{{\tt data.mps}} |
---|
535 | |
---|
536 | This is an MPS file that is read with code in {\tt reader.cpp}. |
---|
537 | If a different type of input has to be used, one should change |
---|
538 | the code in {\tt reader.cpp}. |
---|
539 | |
---|
540 | \section{{\tt COIN/Examples/VolLp}} |
---|
541 | |
---|
542 | This 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 |
---|
544 | code uses other components of {\tt COIN-OR} while the code in \goodbreak |
---|
545 | {\tt COIN/Examples/Volume-LP} is self contained. |
---|
546 | The files here are {\tt INSTALL, Makefile, \goodbreak |
---|
547 | Makefile.vollp, vollp.cpp}. |
---|
548 | The {\tt INSTALL} contains instructions on how to compile and build |
---|
549 | the code. The input should be an MPS file. |
---|
550 | |
---|
551 | \section{{\tt COIN/Osi/OsiVol}} |
---|
552 | |
---|
553 | In this directory there is the file {\tt OsiVolSolverInterface.cpp} |
---|
554 | that allows the user to call the VA through {\tt OSI}. This is also |
---|
555 | intended to deal with combinatorial linear programs. The code below |
---|
556 | reads an MPS file and calls the VA through OSI. |
---|
557 | |
---|
558 | \begin{verbatim} |
---|
559 | #include "OsiVolSolverInterface.hpp" |
---|
560 | |
---|
561 | #include <iostream> |
---|
562 | |
---|
563 | int 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 | |
---|
590 | This directory contains code for doing Branch-and-Cut based on the |
---|
591 | VA as in \cite{BL}. The code is specialized to the Max-Cut problem. |
---|
592 | |
---|
593 | |
---|
594 | \bibliography{volDoc} |
---|
595 | |
---|
596 | \end{document} |
---|
597 | |
---|
598 | |
---|