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: | Williams H. Paul |
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.