source: trunk/Bonmin/doc/BOUM_options.tex @ 1

Last change on this file since 1 was 1, checked in by andreasw, 13 years ago

imported initial code

File size: 16.9 KB
Line 
1\PageHead{Setting Options}
2\StartPageSummary
3\PageSection{Passing options to \Bonmin }{sec:opt_opt}
4\PageSection{Getting good solutions to nonconvex problems}{sec:opt_nonconv}
5\PageSection{Notes on \Ipopt\ options}{sec:opt_ipopt}
6\EndPageSummary
7\NavigationPanel
8
9\PageTitle{Options}{sec:opt}
10\subsectionH{Passing options to \Bonmin}{sec:opt_opt}
11Options in \Bonmin\ can be set in several different ways.
12
13First, you can set options by putting them in a file called {\tt
14bonmin.opt} in the directory where {\tt bonmin} is executing. If you
15are familiar with the file
16\href{http://www.coin-or.org/Ipopt/documentation/node38.html}{\tt
17ipopt.opt} (formerly named {\tt PARAMS.DAT}) in {\tt Ipopt}, the
18syntax of the {\tt bonmin.opt} is similar. For those not familiar
19with {\tt ipopt.opt}, the syntax is simply to put the name of the
20option followed by its value, with no more than two options on a
21single line. Anything on a line after a \# symbol is ignored (i.e.,
22treated as a comment).
23
24Note that \Bonmin\ sets options for {\tt
25Ipopt}. If you want to set options for {\tt Ipopt} (when used inside \Bonmin) you have to set them
26in the file {\tt bonmin.opt} (the standard {\tt Ipopt} option file {\tt ipopt.opt}
27is not read by \Bonmin.)
28For a list and a description of all the {\tt Ipopt} options, the
29reader may refer to the
30\footlink{http://www.coin-or.org/Ipopt/documentation/node43.html}{documentation
31of {\tt
32Ipopt}}.
33
34Since {\tt bonmin.opt} contains both {\tt Ipopt} and \Bonmin\ options, for clarity
35all \Bonmin\ options should be preceded with the prefix ``{\tt bonmin.}'' in {\tt bonmin.opt}~.
36Note that some options can also be passed to the MILP subsolver used by \Bonmin\
37in the outer approximation decomposition
38and the hybrid (see Subsection \ref{sec:milp_opt}).\\
39
40The most important option in \Bonmin\ is the choice of the solution
41algorithm. This can be set by using the option named {\tt
42bonmin.algorithm} which can be set to {\tt B-BB}, {\tt B-OA}, {\tt
43B-QG} or {\tt B-Hyb} (it's default value is {\tt B-Hyb}). Depending
44on the value of this option, certain other options may be available
45or not. Table \ref{tab:options} gives the list of options together
46with their types, default values and availability in each of the
47four algorithms. The column labeled `type' indicates the type of the
48parameter (`F' stands for float, `I' for integer, and `S' for
49string). The column labeled default indicates the global default
50value. Then for each of the four algorithm {\tt B-BB}, {\tt B-OA},
51{\tt B-QG} and {\tt B-Hyb}, `$+$' indicates that the option is
52available for that particular algorithm
53while `$-$' indicates that it is not.\\
54
55An example of a {\tt bonmin.opt} file including all the options
56with their default values is located in the {\tt Test}
57sub-directory.
58
59A small example is as follows:
60\begin{verbatim}
61   bonmin.bb_log_level 4
62   bonmin.algorithm B-BB
63   print_level 6
64\end{verbatim}
65This sets the level of output of the branch-and-bound in \Bonmin\ to $4$, the algorithm to branch-and-bound
66and the output level for {\tt Ipopt} to $6$.\\
67
68When \Bonmin\ is run from within {\tt Ampl}, another way to set
69an option is through the
70internal {\tt Ampl} command {\tt options}.
71For example
72\begin{verbatim}
73options bonmin_options "bonmin.bb_log-level 4 \
74                  bonmin.algorithm B-BB print_level 6";
75\end{verbatim}
76has the same affect as the {\tt bonmin.dat} example above.
77Note that any \Bonmin\ option specified in the file {\tt bonmin.opt}
78overrides any setting of that option from within {\t Ampl}.\\
79
80A third way is to set options directly in the C/C++ code when
81running \Bonmin\ from inside a C/C++ program as is explained in the reference manual.
82
83A detailed description of all of the \Bonmin\ options is given in Appendix \ref{sec:optList}.
84In the following, we give some more details on options for the MILP subsolver and
85on the options specifically designed
86for nonconvex problems.\\
87
88\mylatexhtml{
89\begin{latexonly}
90%\begin{table}[htb]
91%\centering
92\begin{threeparttable}%[tb]
93\caption{\label{tab:options} %\parbox{\linewidth}{
94    List of options and compatibility with the different algorithms.
95    }
96\begin{tabular}{|l|r|r|r|r|r|r|}
97\hline
98Option & type &  default & {\tt B-BB} & {\tt B-OA} & {\tt B-QG} & {\tt B-Hyb} \\
99\hline
100\multicolumn{1}{|c}{} & \multicolumn{6}{l|}{output options}\\
101\hline
102bb\_log\_level & I & 1 & + & $-$  & + & +\\
103bb\_log\_interval & I & 100 & + & $-$ & + & +\\
104lp\_log\_level & I & 0 & $-$ & $-$ & + & +\\
105milp\_log\_level & I &  0 & $-$ &  + & $-$ & +\\
106oa\_log\_level & I & 1 & $-$ &  + & $-$ & +\\
107nlp\_log\_level & I & 0 & +&  + & + & +\\
108print\_user\_options & S & no & + & + & + & +\\
109\hline
110\multicolumn{1}{|c}{} & \multicolumn{6}{l|}{branch-and-bound options}\\
111\hline
112allowable\_gap  & F & 0 & + & + & + & +\\
113allowable\_fraction\_gap & F & 0& +& + & +& +\\
114cutoff & F& 1e+100 &  + & +& +& +\\
115cutoff\_decr & F & 1e$-$05 & + & + & + & +\\
116integer\_tolerance & F & + &  + & + & + & +\\
117node\_limit & I & INT\_MAX &  + & +& + & + \\
118nodeselect\_stra$^*$ & S & best-bound & + & + & +& +\\
119number\_before\_trust$^*$ & I & 8 & $-$ & + & + & +\\
120number\_strong\_branch$^*$ & I & 20 & $-$ & + & + &+ \\
121time\_limit & F & 1e+10 & + & + & + & +\\
122\hline
123\multicolumn{1}{|c}{} & \multicolumn{6}{l|}{options for robustness}\\
124\hline
125max\_random\_point\_radius & F &&+ &+ &+ &+\\
126num\_consecutive\_failures & I & 1 & + & $-$ & $-$ & $-$\\
127nlp\_failure\_behavior & S & stop   & + & + & + & + \\
128num\_iterations\_suspect & I & $-$1 & + & + & + & + \\
129num\_retry\_unsolved\_random\_point & I & 0 & + & + & + & + \\
130\hline
131\multicolumn{1}{|c}{} & \multicolumn{6}{l|}{options for nonconve+ problems}\\
132\hline
133num\_consecutive\_infeasible & I & 1 & + & $-$ & $-$ & $-$\\
134num\_resolve\_at\_node & I & 0 & + & +  & + & + \\
135num\_resolve\_at\_root & I & 0& + & + & + & +  \\
136\hline
137\multicolumn{1}{|c}{} & \multicolumn{6}{l|}{{\tt B-Hyb }specific options}\\
138\hline
139nlp\_solve\_frequency & I & 10 & $-$ & $-$ & $-$ & +\\
140oa\_dec\_time\_limit & F& 120 & $-$ & $-$ & $-$ & +\\
141tiny\_element & F & 1e$-$08 & $-$ & + & + & + \\
142very\_tiny\_element & F & 1e$-$17 & $-$ & + & + & + \\
143\hline
144\multicolumn{1}{|c}{} & \multicolumn{6}{l|}{MILP options}\\
145\hline
146cover\_cuts$^*$  & I & $-$5 & $-$ & + & $-$ & +\\
147Gomory\_cuts$^*$ & I & $-$5 & $-$ &  + & $-$ & + \\
148milp\_subsolver &S & {\tt Cbc\_D} & $-$ & + & $-$ & + \\
149mir\_cuts$^*$  & I & $-$5 & $-$  & + & $-$ &+\\
150probing\_cuts$^1$$^*$  & I & 0 & $-$ & + & $-$ & +\\
151\hline
152\end{tabular}
153\begin{tablenotes}
154\item $\strut^*$ option is available
155         for MILP subsolver (it is only passed if the {\tt milp\_subsolver} option is set to {\tt Cbc\_Par},
156         see Subsection \ref{sec:milp_opt}).
157\item $\strut^1$ disabled for stability reasons.
158\end{tablenotes}
159\end{threeparttable}
160\end{latexonly}
161}{
162\begin{rawhtml}
163<table border="1">
164  <tr>
165    <td>Option </td>
166    <td> type </td>
167    <td> default </td>
168    <td> B-BB</td>
169    <td> B-OA</td>
170    <td> B-QG</td>
171    <td> B-Hyb</td>
172  </tr>
173  <tr>
174    <td>bb_log_level </td>
175    <td> I </td>
176    <td> 1 </td>
177    <td> + </td>
178    <td> - </td>
179    <td> + </td>
180    <td> +</td>
181  </tr>
182  <tr>
183    <td>bb_log_interval </td>
184    <td> I </td>
185    <td> 100</td>
186    <td> + </td>
187    <td> - </td>
188    <td> + </td>
189    <td> +</td>
190  </tr>
191  <tr>
192    <td>lp_log_level </td>
193    <td> I </td>
194    <td> 0 </td>
195    <td> - </td>
196    <td> - </td>
197    <td> + </td>
198    <td> +</td>
199  </tr>
200  <tr>
201    <td>milp_log_level </td>
202    <td> I </td>
203    <td> - </td>
204    <td> + </td>
205    <td> - </td>
206    <td> +</td>
207  </tr>
208  <tr>
209    <td>oa_log_level </td>
210    <td> I </td>
211    <td> 1 </td>
212    <td> - </td>
213    <td> + </td>
214    <td> - </td>
215    <td> +</td>
216  </tr>
217  <tr>
218    <td>nlp_log_level </td>
219    <td> I </td>
220    <td> 0 </td>
221    <td> +</td>
222    <td> + </td>
223    <td> + </td>
224    <td> +</td>
225  </tr>
226  <tr>
227    <td>allowable_gap </td>
228    <td> F </td>
229    <td> 0 </td>
230    <td> + </td>
231    <td> + </td>
232    <td> + </td>
233    <td> +</td>
234  </tr>
235  <tr>
236    <td>allowable_fraction_gap </td>
237    <td> F </td>
238    <td> 0</td>
239    <td> +</td>
240    <td> + </td>
241    <td> +</td>
242    <td> +</td>
243  </tr>
244  <tr>
245    <td>cutoff </td>
246    <td> F</td>
247    <td> 1e100 </td>
248    <td> + </td>
249    <td> +</td>
250    <td> +</td>
251    <td> +</td>
252  </tr>
253  <tr>
254    <td>cutoff_decr </td>
255    <td> F </td>
256    <td> 1e-05 </td>
257    <td> + </td>
258    <td> + </td>
259    <td> + </td>
260    <td> +</td>
261  </tr>
262  <tr>
263    <td>integer_tolerance </td>
264    <td> F </td>
265    <td> + </td>
266    <td> + </td>
267    <td> + </td>
268    <td> + </td>
269    <td> +</td>
270  </tr>
271  <tr>
272    <td>node_limit </td>
273    <td> I </td>
274    <td> INT_MAX </td>
275    <td> + </td>
276    <td> +</td>
277    <td> + </td>
278    <td> + </td>
279  </tr>
280  <tr>
281    <td>nodeselect_stra<a href="#MILP_options">(1)</a></td>
282    <td> S </td>
283    <td> best-bound </td>
284    <td> + </td>
285    <td> + </td>
286    <td> +</td>
287    <td> +</td>
288  </tr>
289  <tr>
290    <td>number_before_trust<a href="#MILP_options">(1)</a></td>
291    <td> I </td>
292    <td> 8 </td>
293    <td> - </td>
294    <td> + </td>
295    <td> + </td>
296    <td> +</td>
297  </tr>
298  <tr>
299    <td>number_strong_branch<a href="#MILP_options">(1)</a></td>
300    <td> I </td>
301    <td> 20 </td>
302    <td> - </td>
303    <td> + </td>
304    <td> + </td>
305    <td>+ </td>
306  </tr>
307  <tr>
308    <td>time_limit </td>
309    <td> F </td>
310    <td> 1e10 </td>
311    <td> + </td>
312    <td> + </td>
313    <td> + </td>
314    <td> +</td>
315  </tr>
316  <tr>
317    <td>ma+_random_point_radius </td>
318    <td> F </td>
319    <td>1e08</td>
320    <td>+ </td>
321    <td>+ </td>
322    <td>+ </td>
323    <td>+</td>
324  </tr>
325  <tr>
326    <td>ma+_consecutive_failures </td>
327    <td> I </td>
328    <td> 1</td>
329    <td> + </td>
330    <td> - </td>
331    <td> - </td>
332    <td> -</td>
333  </tr>
334  <tr>
335    <td>nlp_failure_behavior </td>
336    <td> S </td>
337    <td> stop </td>
338    <td> + </td>
339    <td> + </td>
340    <td> + </td>
341    <td> + </td>
342  </tr>
343  <tr>
344    <td>num_iterations_suspect </td>
345    <td> I </td>
346    <td> -1 </td>
347    <td> + </td>
348    <td> + </td>
349    <td> + </td>
350    <td> + </td>
351  </tr>
352  <tr>
353    <td>num_retry_unsolved_random_point </td>
354    <td> I </td>
355    <td> 0 </td>
356    <td> + </td>
357    <td> + </td>
358    <td> + </td>
359    <td> + </td>
360  </tr>
361  <tr>
362    <td>ma+_consecutive_infeasible </td>
363    <td> I </td>
364    <td> 0 </td>
365    <td> 0 </td>
366    <td> 0 </td>
367    <td> 0 </td>
368    <td> 0 </td>
369  </tr>
370  <tr>
371    <td>num_resolve_at_node </td>
372    <td> I </td>
373    <td> 0 </td>
374    <td> + </td>
375    <td> + </td>
376    <td> + </td>
377    <td> + </td>
378  </tr>
379  <tr>
380    <td>num_resolve_at_root </td>
381    <td> I </td>
382    <td> 0</td>
383    <td> + </td>
384    <td> + </td>
385    <td> + </td>
386    <td> + </td>
387  </tr>
388  <tr>
389    <td>nlp_solve_frequency </td>
390    <td> I </td>
391    <td> 10 </td>
392    <td> - </td>
393    <td> - </td>
394    <td> - </td>
395    <td> 10</td>
396  </tr>
397  <tr>
398    <td>oa_dec_time_limit </td>
399    <td> F</td>
400    <td> 120. </td>
401    <td> - </td>
402    <td> - </td>
403    <td> - </td>
404    <td> +</td>
405  </tr>
406  <tr>
407    <td>tiny_element </td>
408    <td> F</td>
409    <td> 1e-08 </td>
410    <td> - </td>
411    <td> + </td>
412    <td> + </td>
413    <td> + </td>
414  </tr>
415  <tr>
416    <td>very_tiny_element </td>
417    <td> F</td>
418    <td> 1e-17 </td>
419    <td> - </td>
420    <td> + </td>
421    <td> + </td>
422    <td> + </td>
423  </tr>
424    <tr>
425    <td>cover_cuts<a href="#MILP_options">(1)</a></td>
426    <td> I </td>
427    <td> -5 </td>
428    <td> - </td>
429    <td> + </td>
430    <td> - </td>
431    <td> +</td>
432  </tr>
433  <tr>
434    <td>Gomory_cuts<a href="#MILP_options">(1)</a></td>
435    <td> I </td>
436    <td> -5 </td>
437    <td> - </td>
438    <td> + </td>
439    <td> - </td>
440    <td> + </td>
441  </tr>
442  <tr>
443    <td>milp_subsolver </td>
444    <td>S </td>
445    <td> Cbc_D </td>
446    <td> - </td>
447    <td> + </td>
448    <td> - </td>
449    <td> + </td>
450  </tr>
451  <tr>
452    <td>mir_cuts<a href="#MILP_options">(1)</a></td>
453    <td> I </td>
454    <td> -5 </td>
455    <td> - </td>
456    <td> + </td>
457    <td> - </td>
458    <td>+</td>
459  </tr>
460  <tr>
461    <td>probing_cuts<a href="#MILP_options">(1)</a><a href="#disabled">(2)</a></td>
462    <td> I </td>
463    <td> 0 </td>
464    <td> - </td>
465    <td> + </td>
466    <td> - </td>
467    <td> +</td>
468  </tr>
469</table>
470\end{rawhtml}
471}
472
473
474\subsection{Passing options to the MILP subsolver}
475\label{sec:milp_opt}
476In the context of outer approximation decomposition, a standard MILP solver is used.
477Several option are available for configuring this MILP solver.
478\Bonmin\ allows a choice of different MILP solvers through the option
479{\tt bonmin.milp\_subsolver}. Values for this option are: {\tt Cbc\_D} which uses {\tt Cbc} with its
480default settings, {\tt Cplex} which uses {\tt Cplex} with its default settings, and
481{\tt Cbc\_Par} which uses a version of {\tt Cbc} that can be parameterized by the user.
482
483The options that can be set are the node-selection strategy, the number of strong-branching candidates,
484the number of branches before pseudo costs are to be trusted, and the frequency of the various cut generators
485(options marked with $^*$ in Table \ref{tab:options}). To pass those options to the MILP subsolver, you have
486to replace the prefix ``{\tt bonmin.}'' with ``{\tt milp\_sub.}''.
487
488
489\subsectionH{Getting good solutions to nonconvex problems}{sec:opt_nonconv}
490\label{sec:non_convex}
491A few options have been designed in \Bonmin\ specifically to treat
492problems that do not have a convex continuous relaxation.
493In such problems, the solutions obtained from {\tt Ipopt} are
494not necessarily globally optimal, but are only locally optimal. Also the outer-approximation
495constraints are not necessarily valid inequalities for the problem.
496
497No specific heuristic method for treating nonconvex problems is implemented
498yet within the OA framework.
499But for the pure branch-and-bound {\tt B-BB}, we implemented a few options having
500in mind that lower bounds provided by {\tt Ipopt} should not be trusted, and with the goal of
501trying to get good solutions. Such options are at a very experimental stage.
502
503First, in the context of nonconvex problems, {\tt Ipopt} may find different local optima when started
504from different starting points. The two options {\tt num\_solve\_at\_root} and {\tt num\_solve\_at\_node}
505allow for solving the root node or each node of the tree, respectively, with a user-specified
506number of different randomly-chosen
507starting points, saving the best solution found. Note that the function to generate a random starting point
508is very na\"{\i}ve: it chooses a random point (uniformly) between the bounds provided for the variable.
509In particular if there are some functions
510that can not be evaluated at some points of the domain, it may pick such points,
511 and so it is not robust in that respect.
512
513Secondly, since the solution given by {\tt Ipopt} does not truly give a lower bound, we allow for
514changing the fathoming rule
515to continue branching even if the solution value to the current node is worse
516than the best-known
517solution. This is achieved by setting {\tt allowable\_gap}
518and {\tt allowable\_fraction\_gap} and {\tt cutoff\_decr} to negative values.
519
520\subsectionH{Notes on \Ipopt\ options}{sec:opt_ipopt}
521\Ipopt\ has a very large number of options, to get a complete description of them, you
522should refer to the \Ipopt\ manual.
523Here we only mention and explain some of the options that have been more important to us, so far,
524in developing and using \Bonmin.
525\subsubsection{Default options changed by \Bonmin}
526\Ipopt\ has been tailored to be more efficient when used in the context of the
527solution of a MINLP problem. In particular, we have tried to
528improve \Ipopt's warm-starting capabilities and its ability to prove quickly that a subproblem
529is infeasible. For ordinary NLP problems, \Ipopt\ does not use these options
530by default, but \Bonmin\ automatically changes these options from their default values.
531
532Note that options set by the user in {\tt bonmin.opt} will override these
533settings.
534
535\paragraph{{\tt mu\_strategy} and {\tt mu\_oracle}} are set, respectively, to
536{\tt adaptive} and {\tt probing} by default (these are newly implemented strategies in \Ipopt\
537for updating the barrier parameter \cite{NocedalAdaptive} which we have found to be
538more efficient in the context of MINLP).
539\paragraph{{\tt gamma\_phi} and {\tt gamma\_theta}} are set to $10^{-8}$ and $10^{-4}$
540respectively. This has the effect of reducing the size of the filter in the line search performed by Ipopt.
541
542\paragraph{required\_infeasibility\_reduction} is set to $0.1$.
543This increases the required infeasibility reduction when \Ipopt\ enters the
544restoration phase and should thus help
545detect infeasible problems faster.
546
547\paragraph{expect\_infeasible\_problem} is set to {\tt yes} which enables some heuristics
548to detect infeasible problems faster.
549
550\paragraph{\tt warm\_start\_init\_point} is set to {\tt yes} when a full primal/dual starting
551point is available (generally all the optimizations after the continuous relaxation has been solved).
552
553\paragraph{\tt print\_level} is set to $0$ by default to turn off Ipopt output.
554\subsubsection{Some useful \Ipopt\ options}
555\paragraph{bound\_relax\_factor} is by default set to $10^{-8}$ in \Ipopt. All of the bounds
556of the problem are relaxed by this factor. This may cause some trouble
557when constraint functions can only be evaluated within their bounds.
558In such cases, this
559option should be set to 0.
Note: See TracBrowser for help on using the repository browser.