Sensitivity Analysis in Integer Linear Programming: The Right Hand Side Case

An algorithm based on a special duality concept is used to solve an integer linear programming problem and to perform sensitivity analysis for changes of the right-hand side vector. An optimality criterion that easily can be checked is formulated. Dual prices are introduced in order to identify inactive restrictions. 1 Introduction In general, methods for solving optimization problems assume that coefficients are known exactly. Almost all coefficients of practical mathematical problems are estimated with errors. A purpose of sensitivity analysis is to answer the question: How much can data be variied without destroying an optimal solution? In linear programming (LP) exists a well-developed theory and practical application is possible, e.g., see Dinkelbach [1] or Gal [2]. The approaches are frequently based on an optimality condition which is necessary and sufficient. In general, there doesn't exist such a simple optimality test in integer programming, unfortunately. Several efforts ha..