A branch and bound algorithm for extreme point mathematical programming problems (Q1078072): Difference between revisions
From MaRDI portal
Latest revision as of 14:55, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A branch and bound algorithm for extreme point mathematical programming problems |
scientific article |
Statements
A branch and bound algorithm for extreme point mathematical programming problems (English)
0 references
1985
0 references
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.
0 references
extreme point mathematical programming
0 references
convex polytope
0 references
linear inequalities
0 references
branch and bound
0 references
hyperplane
0 references
continuous relaxation
0 references
penalties
0 references
computational results
0 references
0 references
0 references
0 references
0 references