Marginal values in mixed integer linear programming

DOI10.1007/BF01587077MaRDI QIDQ1119179zbMATH OpenOpenAlexFDO

Authors Alton C. Williams

Publication date 1989

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01587077

zbMATH Keywords

directional partial derivativesMarginal valuesperturbationspost- optimal analysis

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Mixed integer programming (90C11)

Review text

Marginal values of a given optimization problem are the directional partial derivatives of the value with respect to perturbations in the data. If \(v(c,A,b)=\min \{cx|\) Ax\(\geq b\), \(x\geq 0\}\) and if \(u=(c',A',b')\) is a vector, then the marginal value in direction u is defined by \[ \frac{\partial v}{\partial u}=\lim_{\epsilon \to 0+}\frac{v(c+\epsilon c',\quad A+\epsilon A',\quad b+\epsilon b')- v(c,A,b)}{\epsilon}. \] In this paper this concept is extended to mixed integer linear programming problems. Some applications to model formulation and post-optimal analysis are given.

Recommendations

• The marginal value formula on regions of stability
• Dual regularization, marginal (repeated) values of the linear programming problem
• scientific article; zbMATH DE number 508924
• scientific article; zbMATH DE number 800781
• Inference-Based Sensitivity Analysis for Mixed Integer/Linear Programming

Cites work

• Complementarity Theorems for Linear Programming
• Convex Analysis
• Directional differentiability of the optimal value function in a nonlinear programming problem
• Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming
• scientific article; zbMATH DE number 3121288 (Why is no real title available?)
• scientific article; zbMATH DE number 3709922 (Why is no real title available?)
• scientific article; zbMATH DE number 3307201 (Why is no real title available?)
• scientific article; zbMATH DE number 3186512 (Why is no real title available?)
• Integer programming duality: Price functions and sensitivity analysis
• Marginal Values in Linear Programming
• Minimal inequalities
• On the continuity of the value of a linear program and of related polyhedral-valued multifunctions
• Point-to-Set Maps in Mathematical Programming
• The Validity of a Family of Optimization Methods
• The value function of an integer program

Cited in

(4)

• Average shadow price in a mixed integer linear programming problem
• Evaluating Marginal Costs Associated with Ratio and Other Constraints in Linear Programmes
• Lipschitz continuity of the value function in mixed-integer optimal control problems
• Efficient market-clearing prices in markets with nonconvexities

This page was built for publication: Marginal values in mixed integer linear programming

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1119179)