Name
Title | ||
|---|---|---|
A branch and bound algorithm for solving separable convex integer programming problems |
Abstract | ||
|---|---|---|
This paper proposes a branch and bound method that solves a class of nonlinear integer programming problems. A separable convex objective function is minimized over a feasible region defined by the constraints which are separable and convex. The “traditional branch and bound approach” has been to relax integrality restrictions on the decision variables and solve hard nonlinear continuous subproblems. In contrast, the algorithm presented in this paper linearizes all nonlinear functions to form a linear programming problem at each node, which can be solved efficiently by the simplex method. Appropriate branching, bounding, fathoming, partitioning, and reoptimizing schemes are developed. In the computational study, our “linear subproblem approach” is compared with the “traditional nonlinear subproblem approach”. For the test problems randomly generated, our algorithm is shown to be better than the nonlinear subproblem approach. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0305-0548(94)90072-8 | Computers & OR |
Keywords | DocType | Volume |
separable convex integer programming,bound algorithm | Journal | 21 |
Issue | ISSN | Citations |
9 | Computers and Operations Research | 4 |
PageRank | References | Authors |
0.75 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Won J. Lee | 1 | 44 | 5.06 |
| A. Victor Cabot | 2 | 10 | 1.87 |
| M. A. Venkataramanan | 3 | 245 | 20.52 |