4
$\begingroup$

I am not that experienced with Operations Research yet. I have become familiar with what Sensitivity Analysis and Limits Reports are in general and through the use of Excel.

I know that they can only be performed by Excel on non integer variable problems, but I read somewhere online that you can also do it on Integer Linear Programming models.

I'm curious to learn whether they can be done on an ILP problem with binary variables. From what I understand, sensitivity analysis the allowed reduction or augmentation of a variable's value, as well as does the same for the constraints, whereas limits report gives us the upper and lower limit of the objective function's values. But the first one seems to not be feasible since our variables will either be 1 or 0 and I'm unsure how the same can be done on the constraints and as far as the second one goes I'm clueless as well.

So, can we apply those two on a BILP problem or is the nature of the problem not allowing us to?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Sensitivity analysis relies on dual variables, which you can only access when variables are continuous. $\endgroup$
    – Kuifje
    Commented Jan 7, 2023 at 12:59
  • 1
    $\begingroup$ I never head of Limits Report before, but I'm not an Excel solver user., so thanks for posting and getting me to google it. Per solver.com/excel-solver-create-solver-reports "If Solver finds a (locally or globally) optimal solution, and there are no integer constraints, two additional reports are available: the Sensitivity Report and the Limits Report." So Excel solver will not produce these reports if there are any binary or integer variables. Binary variable is an integer variable. I'll let other people answer what can be done and how when there are binary or integer variables. $\endgroup$
    – Mark L. Stone
    Commented Jan 7, 2023 at 16:01
  • $\begingroup$ @Kuifje Thank you! $\endgroup$
    – Tita
    Commented Jan 7, 2023 at 17:33
  • $\begingroup$ @MarkL.Stone Thank you for your input! $\endgroup$
    – Tita
    Commented Jan 7, 2023 at 17:33

1 Answer 1

Reset to default
3
$\begingroup$

Parametric/sensitivity analysis of a right hand side coefficient in an optimization problem with integer variables can be done, but it is messy. See: Schrage, L, and L. Wolsey (1985), "Sensitivity Analysis for Branch and Bound Integer Programming," Operations Research, 33, (5):1008-1023.

Parametric analysis of an objective coefficient of a variable that appears linearly in the objective is a bit more straight forward. The major result is that the optimal objective value is a concave function (assuming you are minimizing the objective) of the changing objective coefficient. If the optimization problem is a linear integer program, then the optimal objective value is a piecewise linear concave function. Loosely speaking, the approach is: solve a modest number of problems for appropriately/wisely chosen values for the parameter and "connect the dots." See:

Jenkins, L. (1982) "Parametric Mixed Integer Programming: An Application to Solid Waste Management." Management Science 28(11):1270-1284.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.