Premium
An algorithm and new penalties for concave integer minimization over a polyhedron
Author(s) -
Bretthauer Kurt M.,
Victor Cabot A.,
Venkataramanan M. A.
Publication year - 1994
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/1520-6750(199404)41:3<435::aid-nav3220410309>3.0.co;2-6
Subject(s) - cutting plane method , integer (computer science) , branch and bound , polyhedron , mathematical optimization , branch and cut , integer programming , mathematics , function (biology) , minification , branch and price , algorithm , upper and lower bounds , linear programming , computer science , combinatorics , mathematical analysis , evolutionary biology , biology , programming language
We present a branch‐and‐bound algorithm for globally minimizing a concave function over linear constraints and integer variables. Concave cost functions and integer variables arise in many applications, such as production planning, engineering design, and capacity expansion. To reduce the number of subproblems solved during the branch‐and‐bound search, we also develop a framework for computing new and existing penalties. Computational testing indicates that penalties based on the Tuy cutting plane provide large decreases in solution time for some problems. A combination of Driebeek‐Tomlin and Tuy penalties can provide further decreases in solution time. © 1994 John Wiley & Sons, Inc.