Skip to main content

Simplifying the set of constraints of an optimization problem

Answered

Comments

8 comments

  • Michel Soares
    Thought Leader

    Hi Paul,

    Generic algorithms for this reduction are exactly what pre-solve does and there many techniques behind this. Here is a paper on some of pre-solve techniques used in Gurobi.

    Specific ideas for you problem would involve understanding the model and seeking improvements:

    • Some ideas involve decompositions, such as Column Generation and Benders. In these techniques, you optimize one model followed by another model multiples times, such that each model is individually smaller than the original problem.
    • Using lazy constraints for some class of constraints of your model. 
    • General improvements in tightening bounds, RHS, or reformulating constraints.

    In short, most of the generic algorithms to reduce the number of constraints of your model is already implemented in Gurobi's presolve. Other techniques would involve re-modelling your problem, with business-model-specific ideas.

     

    0
  • Paul Pacaud
    First Comment
    First Question

    Hi Michel,

    Thank you for your reply. As much as I know, presolvers remove redundant constraints of the problem, this is not exactly what I need.

    Let's say you have a problem P with a set of constraints S1. You use a combination of presolver techniques which remove redundant/useless constraints, it reduces down the set S1 to S2 (smaller).
    My question is, how can you prune further this set of constraints ? Reusing presolver techniques will not help as the problem has already been reduced. But yet, I still want to reduce the number of constraints.
    Visually, in 2D, it's like the presolver has reduced the problem to only 4 constraints (let's say the solution space looks like a square), and I want to prune it further to let's say 3 (then the square is pruned to a triangle).
    Is it possible to do this?

    0
  • Michel Soares
    Thought Leader

    You could presolve a model and export it:

    reduced_model = model.presolve()
    reduced_model.write("reduced_model.lp")

    Based on this LP file your can get to a new model with fewer constraints.

    0
  • Paul Pacaud
    First Comment
    First Question

    I see thank you, but my question is: once you have this reduced model, how can you reduce it further ?

    I already have a presolved model, but it has still more than 100 constraints, and I want to remove the ones that don't impact significantly the solution space. For example in 2D, in the drawing below, the presolver gives us the constrainsts ( c1, c2, c3, c4, c5, c6 ), but you can see that removing c2 could help reducing the nb of constrainsts without changing too much the solutions space, because c2 is not very significant. I just don't know how to code this.

     

    0
  • Michel Soares
    Thought Leader

    In your example you could not remove C2.
    Let's say your objective function is to maximize X + Y. The optimal solution of the original model would be in the intersection of C2 and C4. If you take out C2, the optimal solution would be in the intersection of C1 and C4. Therefore, taking out the constraint C2 would greatly affect your solution space, even changing the optimal solution.

    What you are trying to achieve is exactly what pre-solve does in Gurobi, and for that there are many complicated algorithms and techniques. When running pre-solve, Gurobi will attempt to get to the smallest/most efficient model in a way that will not change the optimal solution.
    I cannot recommend other ways to do this besides Gurobi's presolve, which is possibly the best on the market. You could change the Presolve parameter to get to smaller model, but that should be all.

    0
  • Paul Pacaud
    First Comment
    First Question

    Of course, as you pinpoint, it will affect the optimal solution. But in many applications, there is a trade-off to find between computational time to solve the problem and accuracy. 

    In my case, I am fine with losing some accuracy by slightly modifying the solution space, because computation time is very important to me. The challenge is measuring how much accuracy you lose by changing your solution space into simpler shapes. Nevertheless, if I understand correctly from our discussion, this is not currently a feature in Gurobi, as the pre-solvers will always output the smallest model that does not change the optimal solution, not allowing for some trade-off in terms of accuracy...

    0
  • Michel Soares
    Thought Leader

    Yes, that it is indeed the case, Gurobi will always maintain a search space with the optimal solution in it.

    I am unaware of papers with "generic heuristic constraint reductions", but there are many papers that look into specific problems and propose relaxations to speed-up the optimization, you may be able to find some that works for your problem.

    1
  • Paul Pacaud
    First Comment
    First Question

    Thank you for your help anyway :)

    0

Please sign in to leave a comment.