On the Value Function of a Mixed Integer Linear Optimization Problem and an Algorithm for its Construction
Anahita Hassanzadeh (anahita.hassanzadehgmail.com)
Abstract: This paper addresses the value function of a general mixed integer linear optimization problem (MILP). The value function describes the change in optimal objective value as the right-hand side is varied and understanding its structure is central to solving a variety of important classes of optimization problems. We propose a discrete representation of the MILP value function and describe a cutting plane algorithm for its construction. We show that this algorithm is finite when the set of right-hand sides over which the value function of the associated pure integer optimization problem is finite is bounded. We explore the structural properties of the MILP value function and provide a simplification of the Jeroslow Formula obtained by applying our results.
Keywords: Mixed Integer Programming, Stochastic Integer Programming, Parametric Integer Programming, Value Function
Category 1: Integer Programming ((Mixed) Integer Linear Programming )
Category 2: Stochastic Programming
Citation: Laboratory for Computational Optimization at Lehigh (COR@L), Department of Industrial and Systems Engineering, Lehigh University, Technical Report 14T-004.
Entry Submitted: 08/03/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|