Timeline for current status of combinatorial optimization solvers [closed]
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 13, 2014 at 1:56 | comment | added | Chris Godsil | 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. | |
| Oct 12, 2014 at 21:40 | review | Reopen votes | |||
| Oct 13, 2014 at 13:41 | |||||
| Oct 12, 2014 at 21:37 | comment | added | Timothy Chow | (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. | |
| Oct 12, 2014 at 21:32 | comment | added | Timothy Chow | 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. | |
| Oct 12, 2014 at 11:29 | history | closed |
Suvrit Bjørn Kjos-Hanssen Stefan Kohl♦ Carlo Beenakker Per Alexandersson |
Needs more focus | |
| Oct 12, 2014 at 5:57 | review | Close votes | |||
| Oct 12, 2014 at 11:29 | |||||
| Oct 12, 2014 at 5:40 | comment | added | Suvrit | 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... | |
| Oct 12, 2014 at 5:12 | history | asked | user40780 | CC BY-SA 3.0 |