Name
Title | ||
|---|---|---|
A composite branch and bound, cutting plane algorithm for concave minimization over a polyhedron |
Abstract | ||
|---|---|---|
We present an algorithm that combines branch and bound with cutting planes to globally minimize a concave function over a polyhedron. The algorithm solves a series of linear underestimating subproblems over subsets of the feasible region, yielding lower and upper bounds on the optimal objective value of the original problem. The algorithm also uses a form of the Tuy cutting plane in the subproblems of the branch and bound tree. As in cone splitting algorithms for concave minimization, we construct the cutting planes such that no restrictive nondegeneracy assumptions are required and such that the hyperplanes defining the cuts do not need to be explicitly calculated, eliminating matrix inversions. An additional advantage of our algorithm is that the cuts cause the linear underestimating functions to more accurately approximate the concave objective function, yielding tighter lower bounds. Computational results with the algorithm are reported. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0305-0548(94)90007-8 | Computers & OR |
Keywords | DocType | Volume |
concave minimization,plane algorithm,composite branch | Journal | 21 |
Issue | ISSN | Citations |
7 | Computers and Operations Research | 2 |
PageRank | References | Authors |
0.41 | 16 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Kurt M. Bretthauer | 1 | 300 | 23.24 |
| A. Victor Cabot | 2 | 10 | 1.87 |