4 ms·

It's the answer, a vector of integers

by Frummy 1y ago

ayhanfuat 1y ago
Simplex cannot give a vector of integers though, unless the constraint matrix is unimodular. Maybe the integrality constraint was relaxed.
- cweld510 1y ago
  You're right -- we do relax the integrality constraint, gaining performance at the expense of some precision, and we're generally able to paper over the difference at scheduling time. We've investigated integer linear programming for some use cases, but for solves to run quickly, we have to constrain the inputs significantly.
  - ayhanfuat 1y ago
    Thanks for the clarification. I guess it wouldn’t matter much if the numbers are large. Initially I thought they were mostly ones and zeros.
  - stncls 1y ago
    If this is business critical for you, you may want to switch to a faster solver. Glop is very nice, but it would be reasonable to expect a commercial solver (Gurobi, XPress, COpt) to be 60x faster [1]. By the same measure, the best open source solvers (CLP, HiGHS) are 2-3x faster than Glop. Actually, the commercial solvers are so fast that I would not be surprised if they solved the IP problem as fast as Glop solves the LP. (Yes, the theory says it is impossible, but in practice it happens.) The cost of a commercial solver is 10k to 50k per license. [1] ... this 60x number has very high variance depending on the type of problem, but it is not taken out of nowhere, it comes from the Mittelmann LP benchmarks https://plato.asu.edu/ftp/lpopt.html https://plato.asu.edu/ftp/lpopt.html There are also benchmarks for other types of problems, including IP, see the whole list here: https://plato.asu.edu/bench.html https://plato.asu.edu/bench.html
  - petters 1y ago
    If you are able to paper over the fractional numbers and get a usable solution, an integer solver should also be able to find a feasible solution easily. Perhaps not optimal, but better than just solving the LP and rounding
  - hustwindmaple1 1y ago
    You are basically doing a heurstic. Your solutions are not guaranteed to be optimal. Integer programming is the way to do.

It's the answer, a vector of integers

by Frummy 1y ago

It's the answer, a vector of integers

Simplex cannot give a vector of integers though, unless the constraint matrix is unimodular. Maybe the integrality constraint was relaxed.

cweld510 1y ago
You're right -- we do relax the integrality constraint, gaining performance at the expense of some precision, and we're generally able to paper over the difference at scheduling time. We've investigated integer linear programming for some use cases, but for solves to run quickly, we have to constrain the inputs significantly.
- ayhanfuat 1y ago
  Thanks for the clarification. I guess it wouldn’t matter much if the numbers are large. Initially I thought they were mostly ones and zeros.
- stncls 1y ago
  If this is business critical for you, you may want to switch to a faster solver. Glop is very nice, but it would be reasonable to expect a commercial solver (Gurobi, XPress, COpt) to be 60x faster [1]. By the same measure, the best open source solvers (CLP, HiGHS) are 2-3x faster than Glop. Actually, the commercial solvers are so fast that I would not be surprised if they solved the IP problem as fast as Glop solves the LP. (Yes, the theory says it is impossible, but in practice it happens.) The cost of a commercial solver is 10k to 50k per license. [1] ... this 60x number has very high variance depending on the type of problem, but it is not taken out of nowhere, it comes from the Mittelmann LP benchmarks https://plato.asu.edu/ftp/lpopt.html https://plato.asu.edu/ftp/lpopt.html There are also benchmarks for other types of problems, including IP, see the whole list here: https://plato.asu.edu/bench.html https://plato.asu.edu/bench.html
- petters 1y ago
  If you are able to paper over the fractional numbers and get a usable solution, an integer solver should also be able to find a feasible solution easily. Perhaps not optimal, but better than just solving the LP and rounding
- hustwindmaple1 1y ago
  You are basically doing a heurstic. Your solutions are not guaranteed to be optimal. Integer programming is the way to do.