3 ms·

I'm always glad to see articles about integer programming as it's an incredibly powerful tool which deserves to be more widely known. However, I'm not sure the

I'm always glad to see articles about integer programming as it's an incredibly powerful tool which deserves to be more widely known. However, I'm not sure the example chosen was the right introductory problem. As illustrated, we don't get the certifiably optimal solution because the true optimal solution may involve one of the duties we didn't randomly generate. If we don't get the optimal solution, why not just use a heuristic? Yes, there's a brief allusion to column generation which can address this problem, but surely there's an introductory problem which can be solved without requiring the user to think about column generation or similar?

contravariant 9y ago
Yeah, having read it I can't help but feel that a simulated annealing approach might end up generating a better result. If only because the limiting factor for simulated annealing is how quickly you can generate random duties and check some objective function, and not how quickly you can solve some NP complete problem for a large number of variables. Of course having found a couple of good combinations of duties with simulated annealing there's nothing stopping you from trying the integer program on those (+ variations) to try and find a better version.