2
$\begingroup$

What is the current status of the solvers in combinatorial optimization? For example, what is the "usual feasible size" for a traveller sale's man problem, say, how many nodes and edges are "usually solvable".

I am actually trying to construct a solver for material science problems and I saw some possible transformation of the material science problems into different types of combinatorial optimization problem before (max-flow). But I believe there should be more transformations and a brief guide of solver performance would possibly help me with a quick evaluations without trying to code out and test speed. Thank you :)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ This is too broad and vague---the world of combinatorial optimization has a very rich variety of problems, the general ones are of course still too tough (maybe you are looking for MINLP), but for specialized structures there are fast methods. I'm voting to close as this is too broad a question... $\endgroup$
    – Suvrit
    Commented Oct 12, 2014 at 5:40
  • 1
    $\begingroup$ The question isn't phrased very well but I think I understand what is being asked, and if so, I don't think it's too broad. Crudely speaking, there are two ways in practice to approach a combinatorial optimization problem: (1) convert it to a "standard form" and use a general-purpose solver; (2) write special-purpose software that exploits the specific structure of your problem. Option 1 generally requires vastly less programming effort and if it's good enough then you can save yourself the trouble of Option 2. $\endgroup$
    – Timothy Chow
    Commented Oct 12, 2014 at 21:32
  • 2
    $\begingroup$ (continued) Probably the two simplest "standard forms" to try are CNF (conjunctive normal form for Boolean satisfiability) and ILP (integer linear programming). If you express your problem in CNF then you can try a SAT solver like MiniSAT; if you express your problem as an ILP then you can try an ILP solver such as SCIP. Most SAT solvers are free, and SCIP is free for academics. If you are not sure how to express your problems as a CNF instance or an ILP, you could try posting the details of one of your materials science problems here and asking for help formulating it as such. $\endgroup$
    – Timothy Chow
    Commented Oct 12, 2014 at 21:37
  • $\begingroup$ The question is not well-posed. For example there are very effective routines for TSP, instances involving thousands of cities have been solved. On the other hand, colouring problems are much more difficult. $\endgroup$
    – Chris Godsil
    Commented Oct 13, 2014 at 1:56

0

Reset to default