Sensitivity analysis for linear changes of the constraint matrix of a linear program

Understanding the variation of the optimal value with respect to
change in the data is an old problem of mathematical optimisation. This paper
focuses on the linear problem f(λ) = min ctx such that (A+λD)x ≤ b, where
λ is an unknown parameter that varies within an interval and D is a matrix
modifying the coefficients of the constraint matrix A. This problem is used
to analyse the impact of multiple affine changes in the constraint matrix on
the objective function. The function f(λ) can have an erratic behaviour and
computing it for a large number of points is computationally heavy while not
providing any guarantees in between the computed points. As a new approach
to the problem, we derive several bounding methods that provide guarantees
on the objective function’s behaviour. Those guarantees can be exploited to
avoid recomputing the problem for numerous λ. The bounding methods are
based on approaches from robust optimisation or Lagrangian relaxations. For
each approach, we derive three methods of increasing complexity and precision,
one that provides constant bounds, one that provides λ-dependant bounds
and envelope bounds. We assess each bounding method in terms of precision,
availability and timing. We show that for a large number of problems, the
bound approach outperforms the naive sampling approach considered with
100 points while still providing a good precision and stronger guarantees on a
large dataset of problems. We also introduce an iterative algorithm that uses
these bounds to compute an approximation of the original function within a
given error threshold and discuss its performances.