Changeset 2523 for branches


Ignore:
Timestamp:
Mar 9, 2019 4:42:13 PM (4 months ago)
Author:
stefan
Message:

add FAQ, FYI, and fpump from Trac Wiki to Cbc User's Guide

Location:
branches/gh-pages
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • branches/gh-pages/faq.md

    r2521 r2523  
    99(though a rudimentary stand-alone executable exists). The first
    1010documented release was .90.0. (JF 04/01/05)
     11
     12Cbc is designed to work with any OSI capable solver and in particular Clp.
     13It used to be called Sbb (Simple Branch and Bound) but due to people confusing it with GAMS Sbb solver it has been renamed to Cbc.
    1114
    1215**Q:** What are some of the features of CBC?
     
    2326**Q:** Is CBC reliable?
    2427
    25 **A:** CBC has been tested on many problems, but more testing and
    26 improvement is needed before it can get to version 1.0. (JF 04/01/05)
     28**A:** Cbc is at version 1.01.00 so it is no longer a pre-release version - and yes it is reliable. (JF 06/15/06)
     29
     30**Q:** Is it fast?
     31
     32**A:** It is not very fast out of the box, but is very flexible so it can be very effective with correct use of cut generators and heuristics.
     33For instance, cut generators can be switched off, on every so often or only at root node (which is probably best default).
     34The stand-alone code has been much improved to try and make it faster for less experienced users. (JF 06/15/06)
    2735
    2836**Q:** Is there any documentation for CBC?
     
    3745will be able to tailor CBC to their needs. (JF 04/01/05)
    3846
    39 **Q:** When will version 1.0 of CBC be available?
     47**Q:** What are Cbc's advantages?
    4048
    41 **A:** It is expected that version 1.0 will be released in time for the
    42 2005 [INFORMS](http://www.informs.org) annual meeting. (JF 04/01/05)
     49**A:** It is designed to be less heavyweight than BCP or Symphony.
     50It is very easy to add new cut generators and heuristics and branching methods such as lot-sizing variables.
     51I need to publish some more heuristic methods as I have several I use for my own work which at present are too problem specific. (JF 05/24/06)
     52
     53**Q:** How should I start to use it?
     54
     55**A:** There is a stand-alone code `cbc` which I need to improve, both for ease of use and for default behavior.
     56There are also drivers in the examples directory.
     57The sample driver in `Cbc/examples/sample1.cpp` will solve many of the miplib test set as it is.
     58To add a new generator involves adding less than ten lines of code.
     59It is also possible to add heuristics in the same way and to influence the search - `sample2.cpp` and `sample3.cpp` expose more of the strategy as user code. (JF 05/24/06)
     60
     61**Q:** What happened to the SBB code?
     62
     63**A:** SBB stands for Simple Branch and Bound.
     64When COIN-OR LP was being written, the Osi interface demanded an integer solver.
     65An exception could have been thrown but anyone can write a branch and bound code in a day.
     66With Strong Branching it was 460 lines of code, without 300 lines.
     67Somehow the code kept growing and eventually it was moved it to its own project.
     68Now the "Simple" is not as accurate and there was confusion with Gams Sbb code so was frozen as of Halloween 2004.
     69All future development has been on Cbc (COIN-OR Branch and Cut) which is just a renamed version of Sbb. (JF 06/03/06)
     70
     71**Q:** How does one get a list of the undocumented cbc executable options?
     72
     73**A:** Run the cbc executable, set the verbose option to 15, and then enter a *?* to get a list of all commands.
     74```
     75./bin/cbc
     76verbose 15
     77?
     78```
    4379
    4480**Q:** What can the community do to help?
     
    5894  - Tackle any of the "to-dos" listed in the Doxyen documentation and
    5995    contribute back to COIN-OR.
     96
     97# FYI: Lessons from the Trenches
     98
     99 1. *The `-csv` option*
     100
     101    The option `-csv <filename>` causes cbc to print one line of key output statics in commma separated format in a file named <filename>.  This option isn't currently included in the list of commands given by the `?` command in interactive mode.
     102
     103 1. *The `-csv` command works great with one data file.  Is there a way to make it work with the `-miplib` option?*
     104
     105    At present not, according to John. (That's vindicating becuase I tried more things than I'd like to admit under the flawed assumption it did.) John sugggests creating a CbcCsv class and putting some code to do it in there. Sounds like a great enhancement, if someone's looking to contribute <hint, hint>.
     106
     107 1. *Order of options in the command line of the cbc executable matter*
     108
     109    The command line of the cbc executable is parsed as if it were in the interactive mode. The take-away is that if your using the command line, and things aren't working as you think they should, try ordering the commands in the sequence you'd use if you were interactive mode. (I don't have any specific examples right now, but I know others have run into this too.)
     110
     111 1. *How does one build and run a parallel version of cbc?*
     112
     113   To build a parallel enabled version of cbc when running `configure` add the option `--enable-cbc-parallel`.
     114
     115   To run in parallel use the `-threads` option with cbc:
     116   ```
     117   ./cbc -threads 6 -unitTest -dirMiplib=_MIPLIB3DIR_ -miplib
     118   ```
     119   where _MIPLIB3DIR_ is the name of the directory containing the miplib3 mps files.
     120
     121 1. *For a miplib example, say `egout`, should the output related to egout produced by the command `./cbc - miplib` match what I'd get from executing cbc on egout directly?*
     122
     123    No. There's more to -miplib than simply running cbc on each of the miplib datasets (but I don't know exactly what all the differences are).
     124
     125 1. Is there a difference in the default parameter settings when you solve a problem in Cbc's interactive mode versus the command-line mode?
     126
     127    Should not be any difference - the commands are read at a single point in code, switching over after command line ones. <July 8, 2009>
  • branches/gh-pages/heuristics.md

    r2521 r2523  
    1 ## Getting Good Bounds in CBC
    2 
    3 # CbcHeuristic - Heuristic Methods
     1# Getting Good Bounds in CBC
     2
     3## CbcHeuristic - Heuristic Methods
    44
    55In practice, it is very useful to get a good solution reasonably fast.
     
    174174}
    175175```
     176
     177## Notes on the Feasibility Pump Implementation
     178
     179References are
     180- M. Fischetti, L. Bertacco, and A. Lodi. A feasibility pump heuristic for general mixed-integer problems. Technical report, Universita di Bologna - D.E.I.S. - Operations Research, 2005.
     181- M. Fischetti, F. Glover, and A. Lodi. The feasibility pump. Mathematical Programming, 2005.
     182
     183The basic idea (much simplified) is that you start with the relaxed continuous solution and then keep changing the objective function to try and minimize the sum of integer infeasibilities.
     184If this goes to zero then you have a solution.
     185
     186So, how long do you try?  If you get a solution, can you get a better one?
     187Even if you fail to get a solution, can you get any benefit?
     188The answer to the second question is yes - by adding a constraint that says the objective must be better than this solution.
     189The answer to the third question is also yes.
     190By continually changing the objective, you are making the solution go all over the place but there will be variables which despite all this remain fixed at a value.
     191Maybe if you fix these variables and preprocess the resulting problem you will get a much smaller problem on which it will be worth doing a few nodes of branch and cut.
     192
     193By default the Feasibility Pump heuristic is run at the start of CBC's branch and cut, but there are several ways to fine tune the heuristic.
     194Before I answer any of those questions, I should mention one or two undocumented features.
     195There are several parameters you can set to terminate the search early.
     196One is `maxNodes`. If you do `maxN??` in Cbc it will say that the valid range is -1 to 2147483647.
     197If you set maxNodes to 0, cbc will apply all cuts at root node and then terminate, but if you set it to -1, then the cuts will not be computed.
     198This can save some time if all you want to do is find a heuristic solution.
     199Also if `allowableGap` or `ratioGap` is set and a heuristic finds a solution which satisfies the gap criterion, then the code will also terminate before doing the node 0 cut computations.
     200Finally I should mention the `doh` option.  The full name of the parameter is `doHeuristic`.
     201Normally Cbc does preprocessing and then enters branch and cut, where the first thing to be done is the heuristics phase.
     202If a valid value for the objective is known then sometimes the preprocessing can do a better job as it can fix variables on reduced costs.
     203One way of doing this is to run some heuristics, then do preprocessing and go into branch and cut.
     204To do the feasibility pump then do preprocessing and then do feasibility pump inside branch and cut one would do
     205```
     206cbc ....mps -feas both -doh -solve
     207```
     208
     209Anyway back to tuning the feasibility pump.
     210I should mention here that I will give the full name of the option but you can abbreviate it e.g. `passFeasibilityPump` is accepted if you enter `passF`.
     211There are three options which affect the heuristic:
     212
     213 * `passfeasibilityPump` - this says how many passes of feasibility pump to do.
     214   If less than 200 and `hoptions` flag not set then the heuristic will modify this number depending on how things are going.
     215
     216 * `pumpTune` - this is a very complex parameter as more and more was loaded onto it.
     217    It is numeric of the form `fedddcba` where
     218    - `a` is 0,1,2,3.  This is only used if the code is going to fix variables and try a mini branch and cut.
     219      - 0 and 1 have the same meaning and just says - fix all integer variables which have remained at one bound all the time.
     220      - 2 says - also fix those general integer variables which have stayed at an interior integral value.
     221      - 3 says do all that and fix all continuous variables which have stayed at a bound.
     222      The default is 3.
     223    - `b` is used to fine tune how first solve is done. Even I have no clue what this does!
     224    - `c`: at present the only useful values are 0 and 1.
     225      1 says to add a constraint forcing the objective to be better than some initial value.
     226      If the parameter `dextra1` is not set (i.e. is still zero) then this value is 5% more than continuous solution value.
     227      If dextra1 is set then this is used.
     228    - `ddd` says how many solutions to try and get.
     229      If 0 then the heuristic will exit after the first solution.
     230      If n then after n+1 solutions.
     231      After the first time a constraint is added forcing a better solution.
     232    - `e` can be 0,1,4,5.
     233       If 1 or 5 then the mini branch and cut phase is entered.
     234       If 4 or 5 then a different method is used to deal with general integer variables.
     235       The default method is to treat general integer variables as if they were continuous.
     236       When all 0-1 variables are satisfied then if any general are unsatisfied then all 0-1 variables are fixed and a few nodes of branch and bound are tried to satisfy the general integer variables.
     237       If 4/5 is set then the original method of Fischetti and Lodi is used which involves adding one constraint and variable for every general integer variable which is being pushed away from bound.
     238    - `f`: if set then a fraction of the original objective is added in.
     239      This fraction will decay at each pass.  Larger `f` gives a larger fraction.
     240    Whew!  So you think you have finished with options - no way.
     241
     242 * `hOptions` (heuristic options).
     243   The first part of this applies to all heuristics, but only if one of the gap parameters are set to say end search early if gap is reached.
     244   If the 1 bit is set i.e. `hOptions` is odd then the heuristic phase is exited immediately the gap is achieved.
     245   The default behavior is to do all heuristics and then check.
     246   If the 2 bit is set then do exactly the number of passes specified.
     247   Normally if number of passes is 30 then the code will do up to 30 passes each major iteration.
     248   If the 4 bit is set and an initial cutoff is given then the code will relax this cutoff every 50 passes - so that an optimistic guess can be corrected.
     249   If the 8 bit is set then on the second and subsequent major iterations the cutoff will be changed if it does not look as is the code will find a solution.
  • branches/gh-pages/revhist.md

    r2521 r2523  
    44
    55Converted the content from Docbook to Markdown.
     6
     7Integrated some content from the Trac Wiki:
     8- some FAQ items
     9- FYI (on [FAQ page](./faq))
     10- Feasibility pump implementation (on [Heuristics page](./heuristics))
    611
    7120.2 May 2, 2005
Note: See TracChangeset for help on using the changeset viewer.