4 ms·

I do research in combinatorial optimization. Does your company solve any problems with a combinatorial flavor? (say, things can be optimized using combinatorial

by chaoxu 10y ago

I do research in combinatorial optimization. Does your company solve any problems with a combinatorial flavor? (say, things can be optimized using combinatorial algorithms instead of going for gradient descent.

Zephyr314 10y ago
We don't (yet), but we are growing rapidly and always looking for ways to help our customers solve optimization problems. Fwiw, we do support categorical parameters (as well as continuous and integer) and our ensemble of Bayesian optimization techniques are able to solve this mixed type problem much more efficiently than techniques like gradient decent. Although the way we handle the purely combinatorial (only category) problem isn't as flushed out as our mixed type problems. We are looking to grow the team (and our offerings) if you're interested though [1]. [1]: https://sigopt.com/careers https://sigopt.com/careers
- wolfgke 10y ago
  > [We] are able to solve this mixed type problem much more efficiently than techniques like gradient decent. Naive gradient descent is probably the simplest strategy that one can imagine. How do your algorithms compare to Newton methods for minimizing the primal-dual gap (interior point methods)?
  - Zephyr314 10y ago
    We compare to some standard convex optimization techniques implemented in scipy here [1]. We have comparisons to some other Bayesian methods here [2]. I'm happy to answer any questions! [1]: https://github.com/sigopt/sigopt-examples/blob/master/ipython-notebook-example/SigOpt_Introduction.ipynb https://github.com/sigopt/sigopt-examples/blob/master/ipytho... [2]: http://arxiv.org/abs/1603.09441 http://arxiv.org/abs/1603.09441
pizza 10y ago
What are the bread and butter of combinatorial optimization? In other words, the concepts you would first come across, at an undergrad level if possible?
- wolfgke 10y ago
  Doing research in mixed-integer linear optimization (but wrote diploma thesis about some topic in combinatorial optimization): > What are the bread and butter of combinatorial optimization? In other words, the concepts you would first come across, at an undergrad level if possible? - Polyhedral combinatorics (Books: "Alexander Schrijver - Combinatorial Optimization: Polyhedra and Efficiency" (more focus on polyhedral combinatorics; IMHO the best book, but not the most approachable), "Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms" (more focus on algorithms; easier to read). This of course includes (mixed-)integer linear programming ((M)ILP). - Of course learning about (M)ILPs means understanding linear programming (LP). Here I personally prefer "Alexander Schrijver - Theory of Linear and Integer Programming" (this books also covers ILP aspects, but not MILPs). - Other books for learning about ILPs are "Dimitris Bertsimas, Robert Weismantel - Optimization Over Integers" (main focus is ILP, nevertheless a good book) and "Conforti, Cornuejols, Zambelli - Integer Programming". There are no really good books about MILPs that I know of, but these two books at least will cover some aspects of it. - Sometimes semidefinite relaxations will occur (most famous example: Goemans-Williamson Algorithm; less famous, but also important: Lovasz-Schrijver hierarchy, Sherali-Adams hierarchy, Lasserre hierarchy)
  - mccourt 10y ago
    I'd also like to throw in some work by a former colleague of mine at Argonne, Sven Leyffer on nonlinear programming: - A compendium he co-edited named (appropriately enough) Mixed Integer Nonlinear Programming - A review paper he co-authored for Acta Numerica: http://www.mcs.anl.gov/papers/P3060-1112.pdf http://www.mcs.anl.gov/papers/P3060-1112.pdf Also, yeah, the "Alexander Schrijver - Theory of Linear and Integer Programming" reference is solid.
    - wolfgke 10y ago

by chaoxu 10y ago

Zephyr314 10y ago

We don't (yet), but we are growing rapidly and always looking for ways to help our customers solve optimization problems. Fwiw, we do support categorical parameters (as well as continuous and integer) and our ensemble of Bayesian optimization techniques are able to solve this mixed type problem much more efficiently than techniques like gradient decent. Although the way we handle the purely combinatorial (only category) problem isn't as flushed out as our mixed type problems. We are looking to grow the team (and our offerings) if you're interested though [1]. [1]: https://sigopt.com/careers https://sigopt.com/careers

wolfgke 10y ago
> [We] are able to solve this mixed type problem much more efficiently than techniques like gradient decent. Naive gradient descent is probably the simplest strategy that one can imagine. How do your algorithms compare to Newton methods for minimizing the primal-dual gap (interior point methods)?
- Zephyr314 10y ago
  We compare to some standard convex optimization techniques implemented in scipy here [1]. We have comparisons to some other Bayesian methods here [2]. I'm happy to answer any questions! [1]: https://github.com/sigopt/sigopt-examples/blob/master/ipython-notebook-example/SigOpt_Introduction.ipynb https://github.com/sigopt/sigopt-examples/blob/master/ipytho... [2]: http://arxiv.org/abs/1603.09441 http://arxiv.org/abs/1603.09441

pizza 10y ago

What are the bread and butter of combinatorial optimization? In other words, the concepts you would first come across, at an undergrad level if possible?

wolfgke 10y ago
Doing research in mixed-integer linear optimization (but wrote diploma thesis about some topic in combinatorial optimization): > What are the bread and butter of combinatorial optimization? In other words, the concepts you would first come across, at an undergrad level if possible? - Polyhedral combinatorics (Books: "Alexander Schrijver - Combinatorial Optimization: Polyhedra and Efficiency" (more focus on polyhedral combinatorics; IMHO the best book, but not the most approachable), "Bernhard Korte, Jens Vygen - Combinatorial Optimization: Theory and Algorithms" (more focus on algorithms; easier to read). This of course includes (mixed-)integer linear programming ((M)ILP). - Of course learning about (M)ILPs means understanding linear programming (LP). Here I personally prefer "Alexander Schrijver - Theory of Linear and Integer Programming" (this books also covers ILP aspects, but not MILPs). - Other books for learning about ILPs are "Dimitris Bertsimas, Robert Weismantel - Optimization Over Integers" (main focus is ILP, nevertheless a good book) and "Conforti, Cornuejols, Zambelli - Integer Programming". There are no really good books about MILPs that I know of, but these two books at least will cover some aspects of it. - Sometimes semidefinite relaxations will occur (most famous example: Goemans-Williamson Algorithm; less famous, but also important: Lovasz-Schrijver hierarchy, Sherali-Adams hierarchy, Lasserre hierarchy)
- mccourt 10y ago
  I'd also like to throw in some work by a former colleague of mine at Argonne, Sven Leyffer on nonlinear programming: - A compendium he co-edited named (appropriately enough) Mixed Integer Nonlinear Programming - A review paper he co-authored for Acta Numerica: http://www.mcs.anl.gov/papers/P3060-1112.pdf http://www.mcs.anl.gov/papers/P3060-1112.pdf Also, yeah, the "Alexander Schrijver - Theory of Linear and Integer Programming" reference is solid.
  - wolfgke 10y ago