Computational Complexity of Some Problems in Parametric Discrete Programming. I

We explore the computational complexity of certain issues regarding parametric linear and integer linear programming.

For example, we demonstrate that: (1) The equality of optimal value of two integer programs for all right-hand sides (r.h.s) is NP-complete either when the problem is stated in matrix or in functional form; (2) The equality of optimal value of two linear programs for all r.h.s. in matrix form is polynomial, but it becomes NP-complete when one desires equality for all r.h.s. in a polyhedral cone described by generators; (3) The equality of a general polyhedral function (allowing nested “maxes”) to the value of a linear program in matrix form, or to another polyhedral function, is NP-complete; (4) The shortest expression, for the optimum to the subadditive dual of an integer program in matrix form, can require exponential space.