MILP Sensitivity Analysis for the Objective Function Coefficients

Kim Allan Andersen, Trine Krogh Boomsma, Lars Relund Nielsen

Research output: Contribution to journalJournal articleResearchpeer-review

377 Downloads (Pure)

Abstract

This paper presents a new approach to sensitivity analysis of the objective function coefficients in mixed-integer linear programming (MILP). We determine the maximal region of the coefficients for which the current solution remains optimal. The region is maximal in the sense that, for variations beyond this region, the optimal solution changes. For variations in a single objective function coefficient, we show how to obtain the region by biobjective mixed-integer linear programming. In particular, we prove that it suffices to determine the two extreme nondominated points adjacent to the optimal solution of the MILP problem. Furthermore, we show how to extend the methodology to simultaneous changes to two or more coefficients by use of multiobjective analysis. Two examples illustrate the applicability of the approach.
Original languageEnglish
JournalINFORMS Journal on Optimization
Volume5
Issue number1
Pages (from-to)92-109
Number of pages32
ISSN2575-1484
DOIs
Publication statusPublished - 2023

Cite this