The Value Function of a Mixed-Integer Linear Program with a Single Constraint

Menal Guzelsoy(mguzelsoylehigh.edu)
Ted Ralphs(tedlehigh.edu)

Abstract: The value function of a mixed-integer linear program (MILP) is a function that returns the optimal solution value as a function of the right-hand side. In this paper, we analyze the structure of the value function of a MILP with a single constraint. We show that the value function is uniquely determined by a finite number of break points and at most two slopes. We derive conditions for the value function to be continuous and analyze its behavior where it is discontinuous. We also propose a method for systematically extending the value function from a neighborhood of the origin to the entire real line using the technique of maximal subadditive extension.

Keywords: Value Function; Mixed Integer Program

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Citation: Technical Report, COR@L Lab, Lehigh University

Download: [PDF]

Entry Submitted: 03/27/2008
Entry Accepted: 03/27/2008
Entry Last Modified: 03/27/2008

Modify/Update this entry