A branch and bound algorithm for extreme point mathematical programming problems (Q1078072): Difference between revisions

The extreme point mathematical programming problem is to minimize a linear function on those extreme points of a convex polytope Y, which lie within a convex polytope X. Both X and Y are defined by linear inequalities. This generalizes both zero-one and mixed-integer linear programming. After reviewing the known techniques which have been or could be applied, the authors develop their own branch and bound method. Basically branching is achieved by considering a hyperplane defining Y and either impose it as binding, or add it to X's definition, while removing it for Y's definition. Bounds are derived by continuous relaxation, improved by penalties. The efficiency is further increased by the addition, when possible, of some disjunctive constraints. Two different branching rules are proposed. Some computational results are given, indicating that problems with up to 40 variables (including slacks) for defining Y may be solved in reasonable time.