18
$\begingroup$

"Recently" someone asked on Twitter whether "people still use genetic algorithms for integer programs". The "majority answer", i.e., 1 out of 1, was: "Yes" .

So, my follow-up question is: With all the (A) progress in computer hardware, solver improvements and decomposition techniques for IPs on the one hand , (B) "elaborated" frameworks for all kinds of search strategies (TS, SA, GA, VNS, ...) on the other -- and, also, (C) constraint (programming) solvers sitting somewhere in between...

...how do you determine if a problem has to be tackled by technique(s) A, B or/and C [when problem constraints fit to (or: can be captured in) any of these "paradigms"] -- e.g., given a multi-stage version of a JSP or a FSP when the "quality" of the solution outweighs the aspect of availability "near"-time results?

What are the criteria/rules of thumb/... that you apply? Which steps do you think of/go through in order to figure out what might work best?

Improve this question
$\endgroup$
21
$\begingroup$

Here, in approximate order, are my criteria.

  1. Do I need a provably optimal solution (which rules out metaheuristics, other than to generate an initial feasible solution)?
  2. Is this something CPLEX can handle (since I have a license for CPLEX and I'm familiar with it)?
  3. If CPLEX can handle it, should I consider a heuristic, metaheuristic or constraint solver to generate a first feasible solution? (This gets determined empirically in most cases, by running CPLEX and seeing how long it takes to a get a "good" incumbent.)
  4. Assuming that I'm still shopping for an approach at this point, does the problem have a structure that might favor a constraint solver? In my case, given that I have CP Optimizer but am not nearly as familiar with it as with CPLEX, that usually means there's a scheduling aspect to the problem.
  5. If I'm looking for heuristics, is there something in the problem that suggests a likely problem-specific heuristic? If so, go that route. If not, I'll likely go with a GA, since I have experience with GAs and not so much with other metaheuristics.

One other consideration that does not fit neatly into that list: am I doing this for myself or for someone else? If it's for someone else, and they don't have moderately deep pockets (to pay for a solver license), I'll probably switch to a heuristic/metaheuristic and code it myself. I know about the COIN-OR solvers, but they're mainly for C/C++/Python programmers, and I have not kept tabs with progress (if any) adding Java APIs.

Improve this answer
$\endgroup$
4
  • 7
    $\begingroup$ Provably optimal is one aspect of optimization: getting bounds on deviation from optimal can be about as valuable. (enhancing the value of point 1) $\endgroup$
    – Michael Trick
    Jun 6 '19 at 3:01
  • 3
    $\begingroup$ I think there is a major destinction between wanting to 1) solve the problem, and 2) study the problem. Metaheuristics tend more to solving while with decomposition methods it tends more to studying. If time is unlimited it is best to start (my honest opinion) from the IP side and to see what you can learn. That can eventually all be used if you decide to pursue coding a metaheuristic. However, time is often limited and studying the IP is not as straightforward as solving it with a metaheuristic :) $\endgroup$
    – Albert Schrotenboer
    Jun 6 '19 at 13:32
  • $\begingroup$ @AlbertSchrotenboer Could you elaborate on how studying an IP could help with coding metaheuristics? $\endgroup$
    – Antarctica
    Mar 19 '20 at 10:43
  • 1
    $\begingroup$ Nowadays, it is much appreciated if certain parts of a Metaheuristic rely upon solving IPs (or a series of). For instance, I once did a study on routing problems and found that IP formulations with, let's say, 90% of the most expensive arcs removed, gives solutions very close to optimality. This could be exploited in a metaheuristic to speed up operations. Moreover, IP methods could help to provide lower bounds on the metaheuristic solution, which give some insights in the quality of the metaheuristic $\endgroup$
    – Albert Schrotenboer
    Mar 28 '20 at 15:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.