Simplifying the set of constraints of an optimization problem
Answered
I’m currently working on a constrained optimization problem where the constraints define a solutions space which forms a complex polytope with many facets. I’m interested in finding a simpler polytope that approximates the original solutions domain, but with fewer facets. At the end, I am looking for an algorithm that, given a set S1 of n constraints, returns a set S2 of m constraints, where m < n.
Below is my specific constraints set, but my question is much more general and can be applied to many different situations! The initial set of constraints is defined as below, you have approximately 130 constraints after pre-solving:
\[ \sum_{z} A_{z,i} \cdot X_z \leq b_{i} \quad \forall i \in CB. \]
In a matrix form:
\[ A \cdot X \leq b \]
\[ \text{A} \in \mathbb{R}^{130 \times 14} \]
\[ \text{X} \in \mathbb{R}^{14 \times 1} \]
\[ \text{b} \in \mathbb{R}^{130 \times 1} \]
The constraints are linear and the solution space is convex. I repeat: the set of constraints has already been passed through a pre-solver which removed redundant or useless constraints. And I don't want to remove variables from the problem.
Question: How can you simplify the set of constraints so as to reduce down the number of constraints to let's say a dozens of them? In other words, how can you prune the complex polyhedron to get a simpler polyhedron with less facets but still approximating the complex one?
Any advice or references to relevant literature would be greatly appreciated. Thank you in advance for your help!
-
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 -
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 -
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 -
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 -
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 -
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 -
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 -
Thank you for your help anyway :)
0
Please sign in to leave a comment.
Comments
8 comments