Find the same basis optimal solution for two related LPs
AnsweredI have two very similar linear programs. The first one is
$$c^T x \rightarrow \min$$
$$\text{s.t. } Ax = b, \quad x \ge 0$$
And the second is different in the optimisation goal: $$d^T x \rightarrow \min.$$
The vectors c and d coincide in some entries but in general $$d \ge c \ge 0.$$
Also, $$b \ge 0.$$
I am interested in finding a basis feasible solution that is optimal for both these problems (provided such a solution exists, of course - which I suspect to be the case in my problem). Is there an easy way to find it?
P.S. The number of variables and constraints is not that high, something below 100.
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?. -
-
-
Hi Yauhen,
You could enforce the optimal value from the first objective \(c^*\) as a new constraint when solving for the second objective function.
\[\begin{align}\ & \min & d^T x \\ &\text{s. t.} & Ax &= b \\&& c^Tx &\leq c^* \end{align}\]
Cheers,
Matthias0 -
-
Hi, Matthias,
That's very simple and elegant solution. Thanks!
Regards,
/Y.0 -
-
P.S. How do you type mutliline formulas here? I can't figure it out and don't see any information on how to type Latex here... :)
0 -
-
By the way, why is that you suggest to add the new unequality constraint? Since it was an optimal value, we have that for any feasible solution, $$c^T x \ge c^*$$
Should the new constraint be just $$c^T x = c^*?$$
0 -
-
-
Hi Yauhen,
I just updated our Getting started guide and added how to write multi-line formulas. We're using MathJax, so all common LaTeX commands should work.
Concerning your second question: Using an inequality is often better to avoid numerical issues. Since we already minimized, it's safe to formulate this inequality \(c^Tx \leq c^*\) - we're not going to drop below \(c^*\). In case \(d\) can be minimized while preserving the previous level, we have an optimal solution for both LPs.
Another thing you might want to look into is sensitivity analysis. You can query how much you can alter single bounds or objective coefficients without violating your basic solution. See here for more information.
Cheers,
Matthias0 -
-
Hi Matthias,
Thanks for the detailed answer. I will check further sensitivity analysis.
Kind regards,
/Y.0 -
Post is closed for comments.
Comments
7 comments