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.
Citation
Laboratory for Computational Optimization at Lehigh (COR@L), Department of Industrial and Systems Engineering, Lehigh University, Technical Report 14T-004.