Free Access

Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming

A. M. Geoffrion
A. M. Geoffrion
University of California, Los Angeles
Search for more papers by this author
,
R. Nauss
R. Nauss
University of Missouri-St. Louis
Search for more papers by this author

A. M. Geoffrion

University of California, Los Angeles

Search for more papers by this author

R. Nauss

University of Missouri-St. Louis

Search for more papers by this author

Published Online:1 Jan 1977https://doi.org/10.1287/mnsc.23.5.453

Abstract

The purpose of this paper is to take stock of what is known and to suggest some conceptual foundations for future progress in the areas of postoptimality analysis and parametric optimization techniques for integer programming.

Cited by
- Extended local stability radii for post-optimality analysis of linear multi-objective integer optimization problems
  28 April 2026 | Engineering Optimization, Vol. 48
- A survey of exact and approximation algorithms for linear-parametric optimization problems
  28 June 2025 | Journal of Global Optimization, Vol. 93, No. 1
- 0–1 Linear programming under interval uncertainty
  13 May 2025 | Soft Computing, Vol. 29, No. 7
- Inside the Box: 0–1 Linear Programming Under Interval Uncertainty
  1 January 2025
- An outer approximation algorithm for generating the Edgeworth–Pareto hull of multi-objective mixed-integer linear programming problems
  4 January 2024 | Mathematical Methods of Operations Research, Vol. 100, No. 1
- Pricing in non-convex electricity markets with flexible trade-off of pricing properties
  Energy, Vol. 274
- An Exact Solution Algorithm for Integer Bilevel Programming with Application in Energy Market Optimization
  20 March 2023 | Journal of Optimization Theory and Applications, Vol. 197, No. 2
- MILP Sensitivity Analysis for the Objective Function Coefficients
  Kim Allan Andersen,
  Trine Krogh Boomsma,
  Lars Relund Nielsen
  1 September 2022 | INFORMS Journal on Optimization, Vol. 5, No. 1
- Multiple cost coefficients sensitivity theorems of integer linear optimization
  7 March 2021 | Optimization, Vol. 71, No. 10
- Power-to-gas: Decarbonization of the European electricity system with synthetic methane
  Applied Energy, Vol. 323
- Bilevel programming solution algorithms for optimal price-bidding of energy producers in multi-period day-ahead electricity markets with non-convexities
  11 June 2020 | Optimization and Engineering, Vol. 22, No. 1
- Multi‐parametric Mixed‐integer Linear Programming
  18 December 2020
- Real-time personnel re-scheduling after a minor disruption in the retail industry
  Computers & Operations Research, Vol. 120
- Compact representation of near-optimal integer programming solutions
  9 April 2019 | Mathematical Programming, Vol. 182, No. 1-2
- Parametric Optimisation: 65 years of developments and status quo
  5 February 2020
- Support Parametric Vector Analysis of Available Resources for Minimisation of Project Duration–Four Varieties of Conditions
  11 May 2018
- Multi-parametric mixed integer linear programming under global uncertainty
  Computers & Chemical Engineering, Vol. 116
- Rigorous synthesis of energy systems by decomposition via time-series aggregation
  Computers & Chemical Engineering, Vol. 112
- Optimizing high-level nuclear waste disposal within a deep geologic repository
  3 June 2016 | Annals of Operations Research, Vol. 253, No. 2
- Low-complexity control of hybrid systems using approximate multi-parametric MILP
  Automatica, Vol. 63
- Clustering and Resource Allocation for Dense Femtocells in a Two-Tier Cellular OFDMA Network
  IEEE Transactions on Wireless Communications, Vol. 13, No. 3
- Parametric optimization with uncertainty on the left hand side of linear programs
  Computers & Chemical Engineering, Vol. 60
- Mixed integer parametric bilevel programming for optimal strategic bidding of energy producers in day-ahead electricity markets with indivisibilities
  Optimization, Vol. 62, No. 8
- From multi-parametric programming theory to MPC-on-a-chip multi-scale systems applications
  Computers & Chemical Engineering, Vol. 47
- An approach to estimating the complexity of probabilistic procedures for the postoptimality analysis of discrete optimization problems
  24 November 2012 | Cybernetics and Systems Analysis, Vol. 48, No. 6
- Theoretical and algorithmic advances in multi-parametric programming and control
  21 April 2012 | Computational Management Science, Vol. 9, No. 2
- Reoptimization in Lagrangian methods for the 0–1 quadratic knapsack problem
  Computers & Operations Research, Vol. 39, No. 1
- An approach to estimating the average-case complexity of postoptimality analysis of discrete optimization problems
  29 November 2011 | Cybernetics and Systems Analysis, Vol. 47, No. 6
- Spare parts logistics and installed base information
  21 December 2017 | Journal of the Operational Research Society, Vol. 62, No. 3
- Multiparametric Mixed‐Integer Linear Programming
  13 June 2014
- On estimates of the complexity of numerical characteristics of postoptimality analysis for discrete optimization problems
  8 October 2010 | Cybernetics and Systems Analysis, Vol. 46, No. 5
- On decision support for deliberating with constraints in constrained optimization models
  7 July 2010
- General approach to estimating the complexity of postoptimality analysis for discrete optimization problems
  6 April 2010 | Cybernetics and Systems Analysis, Vol. 46, No. 2
- Enhanced-interval linear programming
  European Journal of Operational Research, Vol. 199, No. 2
- Parametric mixed-integer 0–1 linear programming: The general case for a single parameter
  European Journal of Operational Research, Vol. 194, No. 3
- A mathematical model for product selection strategies in a recommender system
  Expert Systems with Applications, Vol. 36, No. 3
- Warehouse Location Problem
  27 April 2009
- An algorithm for multiparametric 0-1-Integer Programming problems relative to a generalized min max objective function
  28 January 2009 | RAIRO - Operations Research, Vol. 43, No. 1
- Optimal automatic reaction and species elimination in kinetic mechanisms
  Combustion and Flame, Vol. 155, No. 1-2
- Multiparametric Mixed Integer Linear Programming
- Parametric Mixed Integer Nonlinear Optimization
- Postoptimal Analysis in Nonserial Dynamic Programming
- Relaxation-Based Bounds for Semi-Infinite Programs
  SIAM Journal on Optimization, Vol. 19, No. 1
- Using adaptive scheduling for increased resiliency in passive asynchronous replication
  10 November 2007 | Innovations in Systems and Software Engineering, Vol. 3, No. 4
- Multiparametric Mixed‐Integer Linear Programming
  22 June 2011
- TWO BI-OBJECTIVE OPTIMIZATION MODELS FOR COMPETITIVE LOCATION PROBLEMS
  20 November 2011 | International Journal of Information Technology & Decision Making, Vol. 05, No. 03
- The average shadow price for MILPs with integral resource availability and its relationship to the marginal unit shadow price
  European Journal of Operational Research, Vol. 169, No. 1
- An Adapted Step Size Algorithm for a 0-1 Biknapsack Lagrangean Dual
  Annals of Operations Research, Vol. 139, No. 1
- An algorithm for multiparametric min max 0-1-integer programming problems relative to the objective function
  8 April 2006 | RAIRO - Operations Research, Vol. 39, No. 4
- Efficient market-clearing prices in markets with nonconvexities
  European Journal of Operational Research, Vol. 164, No. 1
- Sensitivity Analysis for Scheduling Problems
  Journal of Scheduling, Vol. 7, No. 1
- Analyse de sensibilité pour les problèmes linéaires en variables 0-1
  15 March 2004 | RAIRO - Operations Research, Vol. 37, No. 4
- Sensitivity analysis for multi-attribute project selection problems
  14 September 2010 | Civil Engineering and Environmental Systems, Vol. 20, No. 3
- The multiparametric 0–1-integer linear programming problem: A unified approach
  European Journal of Operational Research, Vol. 139, No. 3
- An algorithm to perform a complete parametric analysis relative to the constraint matrix for a 0–1-integer linear program
  European Journal of Operational Research, Vol. 138, No. 3
- Fuzzy non-linear integer program by parametric programming approach
  Fuzzy Sets and Systems, Vol. 122, No. 2
- THE IMPACT OF PRODUCT RECOVERY ON LOGISTICS NETWORK DESIGN
  1 June 2001 | Production and Operations Management, Vol. 10, No. 2
- Optimality analysis of facility location problems using response surface methodology
  International Journal of Physical Distribution & Logistics Management, Vol. 31, No. 1
- Multiparametric Mixed Integer Linear Programming
- Parametric Mixed Integer Nonlinear Optimization
- An Algorithm for the Solution of Multiparametric Mixed Integer Linear Programming Problems
  Annals of Operations Research, Vol. 99, No. 1-4
- An algorithm for the multiparametric 0–1-integer linear programming problem relative to the constraint matrix
  Operations Research Letters, Vol. 27, No. 1
- An algorithm for the multiparametric 0–1-integer linear programming problem relative to the objective function
  European Journal of Operational Research, Vol. 125, No. 1
- A PARAMETRIC WEIGHING APPROACH FOR PROJECT SELECTION UNDER RISK
  The Engineering Economist, Vol. 45, No. 1
- Algorithms for the Solution of Multiparametric Mixed-Integer Nonlinear Optimization Problems
  16 September 1999 | Industrial & Engineering Chemistry Research, Vol. 38, No. 10
- An algorithm to perform a complete right-hand-side parametrical analysis for a 0–1-integer linear programming problem
  European Journal of Operational Research, Vol. 114, No. 3
- An algorithm for multiparametric mixed-integer linear programming problems
  Operations Research Letters, Vol. 24, No. 3
- On accuracy of solutions for discrete optimization problems with perturbed coefficientsof the objective function
  Annals of Operations Research, Vol. 86, No. 0
- Stability aspects of the traveling salesman problem based on k-best solutions
  Discrete Applied Mathematics, Vol. 87, No. 1-3
- Enhancing User Understanding in a Decision Support System: A Theoretical Basis and Framework
  7 December 2015 | Journal of Management Information Systems, Vol. 15, No. 2
- A procedure to verify the completeness of the right-hand-side parametric analysis for a mixed integer linear programming problem
  European Journal of Operational Research, Vol. 108, No. 3
- Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study
  European Journal of Operational Research, Vol. 108, No. 3
- Parametric optimization of MILP programs and a framework for the parametric optimization of MINLPs
  Computers & Chemical Engineering, Vol. 22
- An outer-approximation algorithm for the solution of multiparametric MINLP problems
  Computers & Chemical Engineering, Vol. 22
- Optimization Techniques for Process Synthesis and Material Design Under Uncertainty
  Chemical Engineering Research and Design, Vol. 76, No. 3
- An Annotated Bibliography for Post-Solution Analysis in Mixed Integer Programming and Combinatorial Optimization
- A contraction algorithm for the multiparametric integer linear programming problem
  European Journal of Operational Research, Vol. 101, No. 1
- A bi-objective uncapacitated facility location problem
  European Journal of Operational Research, Vol. 100, No. 3
- A response to “A comment on ’Grey integer programming: An application to waste management planning under uncertainty”’ by Larry Jenkins
  European Journal of Operational Research, Vol. 100, No. 3
- A Multiparametric Programming Approach for Linear Process Engineering Problems under Uncertainty
  3 March 1997 | Industrial & Engineering Chemistry Research, Vol. 36, No. 3
- On heuristic mapping of decision surfaces for post-evaluation analysis
- Structural approach to parametric analysis of an IP on the case of the right-hand side
  European Journal of Operational Research, Vol. 92, No. 1
- A comment on “Grey integer programming: an application to waste management planning under uncertainty” by Guo H. Huang, Brian W. Baetz, Gilles G. Patry
  European Journal of Operational Research, Vol. 89, No. 3
- Making Decisions on Fuzzy Integer Linear Programming Problems
- Parametric uncapacitated facility location
  European Journal of Operational Research, Vol. 86, No. 3
- Some concepts of stability analysis in combinatorial optimization
  Discrete Applied Mathematics, Vol. 58, No. 2
- Boolean programming problems with fuzzy constraints
  Fuzzy Sets and Systems, Vol. 55, No. 3
- Stability of discrete optimization problems
  Cybernetics and Systems Analysis, Vol. 29, No. 3
- A methodology for supporting long-term nuclear energy development decisions-a case of Taiwan
  IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23, No. 1
- A decomposition technique for mixed integer programming problems
  Computers & Operations Research, Vol. 19, No. 6
- A fuzzy set-theoretic method for public facility location
  European Journal of Operational Research, Vol. 58, No. 1
- Parametric nonlinear integer programming: The right-hand side case
  European Journal of Operational Research, Vol. 54, No. 2
- Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems
  Discrete Applied Mathematics, Vol. 30, No. 2-3
- Approaching Fuzzy Integer Linear Programming Problems
- Parametric methods in integer linear programming
  Annals of Operations Research, Vol. 27, No. 1
- Marginal values in mixed integer linear programming
  Mathematical Programming, Vol. 44, No. 1-3
- A multi-objective two-stage approach to the design of communication networks subject to production constraints for computerized manufacturing systems
  29 March 2007 | International Journal of Production Research, Vol. 27, No. 4
- Optimum design of communication network for computer integrated manufacturing
  3 April 2007 | International Journal of Computer Integrated Manufacturing, Vol. 2, No. 1
- References
  22 August 2014
- An approach to postoptimality and sensitivity analysis of zero-one goal programs
  Naval Research Logistics, Vol. 35, No. 1
- References
- Parametric-objective integer programming using knapsack facets and Gomory cutting planes
  European Journal of Operational Research, Vol. 31, No. 1
- Certain parametric problems of integer convex programming and their approximate solution
  Cybernetics, Vol. 21, No. 4
- Parametric Programming Applied to Reliability Optimization Problems
  IEEE Transactions on Reliability, Vol. R-34, No. 2
- A branch-and-bound algorithm for 0–1 parametric mixed integer programming
  Operations Research Letters, Vol. 4, No. 1
- Postoptimality analysis for a network protocol feature specification model
  Computers & Industrial Engineering, Vol. 9, No. 4
- Cross-Media Transfers of Hazardous Wastes
  10 May 2017 | Northeastern Journal of Agricultural and Resource Economics, Vol. 13, No. 2
- Parameterisation algorithms for the integer linear programs in binary variables
  European Journal of Operational Research, Vol. 17, No. 1
- The Historical Development of Parametric Programming
- Stability, parametric, and postoptimality analysis of discrete optimization problems
  Cybernetics, Vol. 19, No. 4
- An allocation problem in the design of a class of large-scale systems: Model and algorithm
- Stability of mixed-integer quadratic programming problems
  27 February 2009
- Linear parametric programming—A brief survey
  27 February 2009
- Three methods for postoptimal analysis in integer linear programming
  27 February 2009
- Solution of a parametric integer programming problem
  Cybernetics, Vol. 18, No. 3
- Network protocol design: Model relationships, heuristic feature specification and analytical extensions
  Computers & Industrial Engineering, Vol. 7, No. 3
- Selected Bibliography of Works Not Cited
- Parametric integer linear programming: A synthesis of branch and bound with cutting planes
  European Journal of Operational Research, Vol. 10, No. 2
- An algorithm for the multiple objective integer linear programming problem
  European Journal of Operational Research, Vol. 9, No. 4
- Integer programming duality: Price functions and sensitivity analysis
  Mathematical Programming, Vol. 20, No. 1
- The user interface and performance of commercial mixed integer programming software
  OR Spektrum, Vol. 2, No. 4
- Postoptimality analysis in nonlinear integer programming: The right‐hand side case
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 28, No. 2
- Optimal algorithms for sensitivity analysis in associative multiplication problems
  Theoretical Computer Science, Vol. 14, No. 1
- Mean-variance analysis for indivisible assets
  Omega, Vol. 9, No. 1
- Experiments in mixed integer linear programming in a manufacturing system
  Omega, Vol. 8, No. 4
- Approximate solutions of an integer linear programming problem with resource variations
- A Survey of Lagrangean Techniques for Discrete Optimization
- A comparative analysis of linear fitting for non-linear functions on optimization
  European Journal of Operational Research, Vol. 2, No. 6
- Analisis de estrategias en el ajuste lineal de funciones no-lineales en problemas de optimizacion
  Trabajos de Estadistica Y de Investigacion Operativa, Vol. 29, No. 3
- A Dynamic Resource Allocation Model for A Machine Requirements Problem
  9 July 2007 | A I I E Transactions, Vol. 10, No. 3
- Solving an integer programming problem
- Decomposition and Sensitivity Analysis in an Aircraft Tasking Problem
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 15, No. 3

Volume 23, Issue 5

January 1977

Pages 453-543

Article Information

Metrics

Information

Published Online:January 01, 1977

Cite as

A. M. Geoffrion, R. Nauss, (1977) Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming. Management Science 23(5):453-466.

https://doi.org/10.1287/mnsc.23.5.453

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Exceptional Paper—Parametric and Postoptimality Analysis in Integer Linear Programming

Abstract

Volume 23, Issue 5

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News