ISSN:
1436-4646
Keywords:
Integer Programming
;
Cutting-Planes
;
Subadditive Duals
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract We consider integer programs in which the objective function and constraint matrix are fixed while the right-hand side varies. The value function gives, for each feasible right-hand side, the criterion value of the optimal solution. We provide a precise characterization of the closed-form expression for any value function. The class of Gomory functions consists of those functions constructed from linear functions by taking maximums, sums, non-negative multiples, and ceiling (i.e., next highest integer) operations. The class of Gomory functions is identified with the class of all possible value functions by the following results: (1) for any Gomory functiong, there is an integer program which is feasible for all integer vectorsv and hasg as value function; (2) for any integer program, there is a Gomory functiong which is the value function for that program (for all feasible right-hand sides); (3) for any integer program there is a Gomory functionf such thatf(v)≤0 if and only ifv is a feasible right-hand side. Applications of (1)–(3) are also given.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01583794
