3 ms·

This is really cool. Is it possible to express the edge coloring constraints simply via integer linear programming? This seems like the type of problem that mig

by blt 8y ago

This is really cool. Is it possible to express the edge coloring constraints simply via integer linear programming? This seems like the type of problem that might be NP-hard but tractable in practice with good heuristics.

indiesolver 8y ago
You can use heuristics if/when the problem becomes ugly due to various constraints you may impose. The trick is to select heuristics depending on the problem at hand and in a way that their hyperparameter values are selected properly.
- wenc 8y ago
  Most modern solvers like CPLEX and Gurobi have built-in heuristics [1] that are automatically selected and applied without user intervention. They typically exploit the structure of the problem or encode the experiences of the developers over large problem testsets. The default heuristics for commercial solvers are actually pretty darned good these days and there's typically no need to hand-pick them. In the MIP world, they are the secret sauce to fast solution times. Hyperparameter tuning has been studied for MIPs (many papers written on this), but ultimately they are black box solutions. My experience inclines me to not even consider hyperparameters except as a last resort or unless you know something specific that a hyperparameter can exploit; there are other more high leverage things than can be done. Random perturbations to the problem have been found to be much more fruitful for forcing a diversity of branch traversal paths and have lead to significant speedups. (M. Fischetti popularized this idea in 2010s [2]) [1] https://resources.mpi-inf.mpg.de/conferences/adfocs-03/Slides/Rothberg_3.pdf https://resources.mpi-inf.mpg.de/conferences/adfocs-03/Slide... Also: http://transp-or.epfl.ch/zinal/2017/slides/group5.pdf http://transp-or.epfl.ch/zinal/2017/slides/group5.pdf [2] https://mat.tepper.cmu.edu/blog/index.php/2012/09/25/fischetti-speeds-up-optimization-with-randomness/ https://mat.tepper.cmu.edu/blog/index.php/2012/09/25/fischet...
  - indiesolver 8y ago
    Thank you for providing useful references. Hyperparameter tuning can accelarate CPLEX by 10x and more depending on problem instances (however, it it true that each new version of CPLEX is faster and faster). What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly.
    - wenc 8y ago
      > What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly. Ah makes sense... stochastic and multiobjective formulations have superstructures that are not exploited by MIP solvers by default, so hyperparameter tuning might be useful. Creating (exact) heuristics for these superstructures are also an active area of research. Some solvers like CPLEX are starting to natively support higher level structures like Benders decompositions [1], but they will never support every structural variation. [1] Benders: https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/ReleaseNotes/topics/releasenotes127/newBenders.html https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0...
wenc 8y ago
Yes, that's right. NP-hard doesn't mean intractable in general, though it has acquired that reputation among computer types. Large mixed-integer programming programs (millions of variables) are routinely solved in reasonable times (seconds to less than an hour). Sure, full or brute-force enumeration algorithms makes you hit the worst case complexity every time. However, most commercial mixed integer solvers don't use brute-force enumeration. Instead they pre-analyze the problem, and then employ a boatload of mathematical techniques--including heuristics--which exploit problem structure and prune off non-solutions and helps the solver reach a solution fairly quickly on average. (luck is involved, of course)
ishaym 8y ago
Hi, I am an algorithm developer at optibus. So I can explain the logic of the use of heuristics in this case. We actually use MIP solvers for many of our problems, and are quite proficient with it. However, mass transit problems, especially in large cities, tend to be highly complex for CPLEX or any other solver to solve out of the box. There are billions of variables, and many global constrains which involves: vehicle types, multiple depots, fueling and charging considerations, driver unions and regulation, and hundreds of others. Simply using generic solver (though very advanced one) works well for small instances but doesn’t scale well for medium to large ones. Just fitting the model in memory is challenging. We, at Optibus, are distributing the problem using massive cloud resources and dedicated algorithms, and use a mixture of this, MIP solvers, and the heuristics discussed in the article. We wanted to keep our competitive edge, but hopefully, we may write a blog post about it in the near future.
- wenc 8y ago
  Makes sense. MIPs are good for getting to rigorous optimality, but right now they have limits to their scaling (every binary variable and every inequality constraint you add increases the complexity of the problem). Your experiences track those of the folks working in airline fare pricing (e.g. ITA software, now Google Flights). If you are willing to give up strict optimality (or small MIP gap), any number of greedy and / or embarassingly parallel algorithms will likely get you reasonable (maybe not optimal, but good enough) results in a shorter amount of time. Plus, you can do much more massive scale out.

by blt 8y ago

indiesolver 8y ago

You can use heuristics if/when the problem becomes ugly due to various constraints you may impose. The trick is to select heuristics depending on the problem at hand and in a way that their hyperparameter values are selected properly.

wenc 8y ago
Most modern solvers like CPLEX and Gurobi have built-in heuristics [1] that are automatically selected and applied without user intervention. They typically exploit the structure of the problem or encode the experiences of the developers over large problem testsets. The default heuristics for commercial solvers are actually pretty darned good these days and there's typically no need to hand-pick them. In the MIP world, they are the secret sauce to fast solution times. Hyperparameter tuning has been studied for MIPs (many papers written on this), but ultimately they are black box solutions. My experience inclines me to not even consider hyperparameters except as a last resort or unless you know something specific that a hyperparameter can exploit; there are other more high leverage things than can be done. Random perturbations to the problem have been found to be much more fruitful for forcing a diversity of branch traversal paths and have lead to significant speedups. (M. Fischetti popularized this idea in 2010s [2]) [1] https://resources.mpi-inf.mpg.de/conferences/adfocs-03/Slides/Rothberg_3.pdf https://resources.mpi-inf.mpg.de/conferences/adfocs-03/Slide... Also: http://transp-or.epfl.ch/zinal/2017/slides/group5.pdf http://transp-or.epfl.ch/zinal/2017/slides/group5.pdf [2] https://mat.tepper.cmu.edu/blog/index.php/2012/09/25/fischetti-speeds-up-optimization-with-randomness/ https://mat.tepper.cmu.edu/blog/index.php/2012/09/25/fischet...
- indiesolver 8y ago
  Thank you for providing useful references. Hyperparameter tuning can accelarate CPLEX by 10x and more depending on problem instances (however, it it true that each new version of CPLEX is faster and faster). What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly.
  - wenc 8y ago
    > What I meant is that in the case if your problem is formulated in a way that the CPLEX and Gurobi cannot treat it (e.g., stochastic and multiobjective) and is not very large-scale, then one can use heuristics. However, the efficiency of the latter will likely depend on hyperparameter settings which need to be set properly. Ah makes sense... stochastic and multiobjective formulations have superstructures that are not exploited by MIP solvers by default, so hyperparameter tuning might be useful. Creating (exact) heuristics for these superstructures are also an active area of research. Some solvers like CPLEX are starting to natively support higher level structures like Benders decompositions [1], but they will never support every structural variation. [1] Benders: https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0/ilog.odms.cplex.help/CPLEX/ReleaseNotes/topics/releasenotes127/newBenders.html https://www.ibm.com/support/knowledgecenter/en/SSSA5P_12.7.0...

wenc 8y ago

Yes, that's right. NP-hard doesn't mean intractable in general, though it has acquired that reputation among computer types. Large mixed-integer programming programs (millions of variables) are routinely solved in reasonable times (seconds to less than an hour). Sure, full or brute-force enumeration algorithms makes you hit the worst case complexity every time. However, most commercial mixed integer solvers don't use brute-force enumeration. Instead they pre-analyze the problem, and then employ a boatload of mathematical techniques--including heuristics--which exploit problem structure and prune off non-solutions and helps the solver reach a solution fairly quickly on average. (luck is involved, of course)

ishaym 8y ago

Hi, I am an algorithm developer at optibus. So I can explain the logic of the use of heuristics in this case. We actually use MIP solvers for many of our problems, and are quite proficient with it. However, mass transit problems, especially in large cities, tend to be highly complex for CPLEX or any other solver to solve out of the box. There are billions of variables, and many global constrains which involves: vehicle types, multiple depots, fueling and charging considerations, driver unions and regulation, and hundreds of others. Simply using generic solver (though very advanced one) works well for small instances but doesn’t scale well for medium to large ones. Just fitting the model in memory is challenging. We, at Optibus, are distributing the problem using massive cloud resources and dedicated algorithms, and use a mixture of this, MIP solvers, and the heuristics discussed in the article. We wanted to keep our competitive edge, but hopefully, we may write a blog post about it in the near future.

wenc 8y ago
Makes sense. MIPs are good for getting to rigorous optimality, but right now they have limits to their scaling (every binary variable and every inequality constraint you add increases the complexity of the problem). Your experiences track those of the folks working in airline fare pricing (e.g. ITA software, now Google Flights). If you are willing to give up strict optimality (or small MIP gap), any number of greedy and / or embarassingly parallel algorithms will likely get you reasonable (maybe not optimal, but good enough) results in a shorter amount of time. Plus, you can do much more massive scale out.