Does Mathematica offer any means for solving linear programming problems with "lazy constraints", as described e.g. here?

While I am not very familiar with linear programming, my understanding of the technique is the following:

  1. Solve the problem with only some of the constraints included.
  2. Identify a still not included constraint that is violated by the solution and provide it to the solver.
  3. Repeat from 1. until there are no more unsatisfied constraints left.

The solver is supposed to be able to re-use information from previous runs to achieve better performance. The technique should be useful when the total number of constraints is very large, so it is not practical to provide all of them at once.

If I try to naïvely re-run the LinearProgramming function with more and more constraints, of course it works, but the performance is not nearly as good as with other systems.

  • $\begingroup$ If you have some core constraints, and some extra constraints, you could randomly sample a handful of the extra constraints and include them in the problem alongside the core constraints. Then get a solution, which must also be checked against the remaining unused extra constraints. If it violates then throw out the extras currently in the problem and replace with a different sample. And repeat this process until all constraints are satisfied. $\endgroup$
    – flinty
    Jun 26, 2020 at 14:40


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.