|Version 2 (modified by tkr, 4 years ago) (diff)|
Looking at Osi
Branching information objects exist in Osi. COIN-OR solvers (e.g., CBC, BCP, etc.) having similiar information should have similiar results (e.g., size of search tree, etc.) According to JJHF and LL in their work, this was not the case. Someone should/could/would explore what's happening. Buzz on the grapevine was that maybe Andreas W. (IPOPT) or Pierre B. (Bonmin) would have interest.
There are many parameters in the code, and by selecting the appropriate magic values, the code's performance can be greatly changed. The milestone is to (1) improve Cbc's default values, and (2) have a good set of parameter values be automatically determined by the software itself.
- Relaxation Induced Neighborhood Search: As I understand it, the RINS heuristic solvers a dozen of so LPs, identifies integer vars that have remained fixed, fixes those integer vars at their sticking point values then branches a while.
- Feasibility Pump: The initial algorithm was proposed by Andrea Lodi. Rumor has it that variations on it by JJHF perform even better.
Wouldn't it be nice if structure in a problem (that could be exploited to more quickly solve the problem) was labeled, so you didn't have to waste processing time finding it? That's the general idea.
It is known that at least one illustrious mip solvers of the past successfully made more use of "cliques" (e.g., knapsack cover cuts with cliques.)
In 1999, JJHF presented a solution to the unsolved SWATH problem of the miplib test set (http://dimacs.rutgers.edu/Workshops/Gomory/abstracts.html#forrest). There were two key ideas.
- how they used the objective function together with constraints in logical processing to identify new cuts
- identifying problem structure (e.g., variables that were labeled as continuous, had to be binary)