Partial derivative of LP solution $(x_1 , \ldots, x_n)$ w.r.t. $x_i$ or $a_i$

Question

Suppose I have an optimal solution and I want to know how the solution would (likely) change if one of the coefficients in the objective function changes, or if I add a constraint that forces $x_i$ away from its optimal value.

Is there a way to estimate for small changes, without re-running the optimization?

Answer 1

As Larry Snyder mentioned in his comment, almost all of the Operations Research books include a chapter dedicated to answering your question which is about "Sensitivity Analysis". A good(short and concise) example can be found here, where all the following changes have been done to the problem and their effects on the optimal solution have been shown:

1. Change the right-hand side of a constraint (resource availability)
2. Change the coefficient of a variable in objective function.
3. Adding a new variable to the model.
4. Adding a new constraint to the model.
5. Simultaneous change in all the coefficients of a variable both in the objective function and in the constraints.

It's not necessary to resolve the problem after any of the abovementioned changes, sensitivity analysis is being used to manage, not only the small changes in the model but also some large modifications like adding a new variable or constraint.

Here is a list of "sensitivity analysis chapters" from two famous operations research books:

• Taha, Hamdy A. Operations research: an introduction. Pearson Education India, 2013. Chapter 3: The Simplex Method and Sensitivity Analysis
• Hillier, Frederick S., and Gerald J. Lieberman. Introduction to operations research. McGraw-Hill Science, Engineering & Mathematics, 1995. Chapter 6: Duality Theory and Sensitivity Analysis

Answer 2

The solution to an LP is given directly by its active set, $I = \{i_1,i_2,...,i_n\}$, which forms a system of equations that recovers the solution $x^*$.

If your solution varies, then the question is whether your active set changes or not:

• If it does not change, then you can simply re-solve the system of equations to get the new solution.
• If it does change, then you need to find the new active set and then solve the resulting system of equations.

This principle was first detailed by Fiacco in 1976, where he called it the "Basic Sensitivity Theorem". The interesting question at this point is of course: how do you decide whether the active set still holds, and what the new active set would be. To understand this, you need to consider:

• Primal feasibility (is the solution feasible): so you get the solution from your set of equations and see whether it satisfies all your constraints.
• Dual feasibility (is the solution optimal): You can prove that the Lagrangian multipliers (which define dual feasibility via $\lambda_i \geq 0$) do not vary when the active set stays the same. So as long as your primal feasibility is given, your active set stays the same. If it becomes infeasible, I'd suggest that you resolve the problem and get the new active set. There are techniques to do this without solving another problem using a variety of approaches, in a field called "multi-parametric programming". A review paper I have written that collects a lot of these thoughts can be found here.