Constructing the value function for an Integer Linear Program over a Cone

Constructing the value function for an Integer Linear Program over a Cone

0.00 Avg rating0 Votes
Article ID: iaor19981396
Country: Netherlands
Volume: 6
Issue: 1
Start Page Number: 15
End Page Number: 26
Publication Date: Jul 1996
Journal: Computational Optimization and Applications
Authors:
Abstract:

The value function of an Integer Program is the optimal objective value expressed as a function of the right-hand-side coefficients. For an Integer Program over a Cone (ILPC) this takes the form of a Chvátal Function which is built up from the operations of taking non-negative linear combinations and integer round-up. A doubly recursive procedure for calculating such a value function is given. This is illustrated by a small numerical example. It is also shown how the optimal solution of an ILPC can be obtained as a function of the right-hand-side through this recursion. The connection with the Group optimization representation of an ILPC is also given together with a discussion of the difficulty of calculating the value function for a general Integer Program.

Reviews

Required fields are marked *. Your email address will not be published.