21–30 of 58 posts
Oh lucky you, your optimization problem is linear. I do something similar, but we have to use heuristics because our problem can't be modelled as a linear problem.
Earlier quoted context omitted.
Could you handle your example in MIP through the objective function, making time outside normal hours expensive, but balancing that with a positive value for lunchtime? Possibly with an integer value limiting the number of days where normal hours can be violated?
It is sort of trivially true that any nonlinear model in practice can be approximated by a sufficiently complicated linear model. So yes, probably. However that is not without cost. It reduces the amount of computer time required and increases the amount of human interpretation and attention required (+ increased time to linearise the original model). On the face of it that is a questionable trade. My anecdotes are s…
You don't need 5–10× more wizards, though; you only need one wizard. If her ILP optimal solution is 0.1% better than the GA heuristic solution — which it might not be! — that might mean 3% higher profits for your company for the year. We are not talking about riveting sheet metal here, where productivity is roughly proportional to the number of workers.
What happens if/when shipments miss their ready times?
Oh lucky you, your optimization problem is linear. I do something similar, but we have to use heuristics because our problem can't be modelled as a linear problem.
See, that's what I thought before I audited an operations research class, but it turns out that the reduction from SAT to ILP is trivial, so there are no problems in NP that can't be modeled as integer linear optimization problems.
While theoretically polynomially reducible, if the rewriting multiplies the number of variables by 1000 then it’s likely not good in practice.
Earlier quoted context omitted.
See, that's what I thought before I audited an operations research class, but it turns out that the reduction from SAT to ILP is trivial, so there are no problems in NP that can't be modeled as integer linear optimization problems.
Yeah, but the problem is that the reduction might be large in practice (in the sense that reducing the original problem to SAT or MIP might require the introduction of a large number of variables). While theoretically polynomially reducible, if the rewriting multiplies the number of variables by 1000 then it’s likely not good in practice.
Earlier quoted context omitted.
Yeah, but the problem is that the reduction might be large in practice (in the sense that reducing the original problem to SAT or MIP might require the introduction of a large number of variables). While theoretically polynomially reducible, if the rewriting multiplies the number of variables by 1000 then it’s likely not good in practice.
I don't have experience reducing problems to SAT but I think the usual inflation factor is a lot less than 1000. I think the trivial reduction I found from SAT to ILP uses 3 ILP variables per SAT variable, but there might be a better one, and I might be misremembering; it might be 4 or something.
Either way, I agree that there is likely some way in which the original commenter’s problem can be solved via MILP/MICP methods (indeed, I’ve found very few problems in practice that cannot be easily reduced) :)
In my experience, each sufficiently complicated model becomes non-linear in some respect. For example, you might want to work with margins for time-slots that are non-linear but smooth. So, even though I've worked with constrained linear programming in the past, I tend to prefer algorithms with meta-heuristics, such as simulated annealing or Tabu search. Although this might not provide the 'best' solution, it provide…
Is a specialized MIP solver mandatory, or would using a general SMT solver like Z3 usually be good enough?
I like to think that MIP is a framework that meets halfway between a natural modeling language and a natural solution language. The reason it's good is that the framework naturally lends itself to abusing linear programming as a subroutine, which can cut out a large amount of search state space. And you tend to find you can encode many problems without too much difficulty with just a handful of tricks.
You can encode a great deal into MIP. Piecewise linearized versions of non linear problems, or logical constraints.
Some interesting applications I've seen or played with:
- Verifying neural nets https://github.com/vtjeng/MIPVerify.jl
- Solving the classical Ising Model http://www.philipzucker.com/solving-the-ising-model-using-a-...
- Global Robot arm kinematics http://www.philipzucker.com/2d-robot-arm-inverse-kinematics-...
- model predictive control with collisions constraints http://www.philipzucker.com/flappy-bird-as-a-mixed-integer-p... See Russ Tedrake's group https://groups.csail.mit.edu/locomotion/pubs.shtml