Parametric Integer Programming Analysis: A Contraction Approach
Abstract
An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one. The approach consists primarily of solving the most relaxed problem (θ=1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated. The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ=1) and then contracting to the original region. © Operational Research Society Ltd.
Recommended Citation
M. G. Bailey and B. E. Gillett, "Parametric Integer Programming Analysis: A Contraction Approach," Journal of the Operational Research Society, vol. 31, no. 3, pp. 257 - 262, Taylor and Francis Group; Taylor and Francis, Jan 1980.
The definitive version is available at https://doi.org/10.1057/jors.1980.43
Department(s)
Computer Science
International Standard Serial Number (ISSN)
1476-9360; 0160-5682
Document Type
Article - Journal
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2023 Taylor and Francis Group; Taylor and Francis, All rights reserved.
Publication Date
01 Jan 1980
