Optimization Online


On the Value Function of a Mixed Integer Linear Optimization Problem and an Algorithm for its Construction

Anahita Hassanzadeh (anahita.hassanzadeh***at***gmail.com)
Ted Ralphs (ted***at***lehigh.edu)

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.

Download: [PDF]

Entry Submitted: 08/03/2014
Entry Accepted: 08/03/2014
Entry Last Modified: 12/12/2016

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society