Marginal values in mixed integer linear programming

For a given optimization problem, P, considered as a function of the data, its marginal values are defined as the directional partial derivatives of the value of P with respect to perturbations in that data. For linear programs, formulas for the marginal values were given by Mills, 10], and further developed by the current author 16]. In this paper, the marginal value formulas are extended to the case of mixed integer linear programming (MIP). As in ordinary linear programming, discontinuities in the value can occur, and the analysis here identifies them. This latter aspect extends previous work on continuity by the current author, 18], Geoffrion and Nauss, 5], Nauss, 11], and Radke, 12], and work on the value function of Blair and Jeroslow, 2]. Application is made to model formulation and to post-optimal analysis.Supported in part by the Air Force Office of Scientific Research, Grant # AFSOR-0271 to Rutgers University.