wiki:FutureProjects

Half-baked Ideas

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.

Auto Tuning

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.

Heuristics

  • 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.

Preprocessing

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.

Cliques

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.)

SWATH Harvest

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)
Last modified 8 years ago Last modified on Apr 16, 2010 4:37:03 PM