Cutting Planes for Low-Rank-Like Concave Minimization Problems

Marcus Porembski ()
Additional contact information
Marcus Porembski: Department of Mathematics, University of Marburg, 35032 Marburg, Germany

Operations Research, 2004, vol. 52, issue 6, 942-953

Abstract: Concavity cuts play an important role in several algorithms for concave minimization, such as pure cutting plane algorithms, conical algorithms, and branch-and-bound algorithms. For concave quadratic minimization problems Konno et al. (1998) have demonstrated that the lower the rank of the problem, i.e., the smaller the number of nonlinear variables, the deeper the concavity cuts usually turn out to be. In this paper we examine the case where the number of nonlinear variables of a concave minimization problem is large, but most of the objective value of a good solution is determined by a small number of variables only. We will discuss ways to exploit such a situation to derive deep cutting planes. To this end we apply concepts usually applied for efficiently solving low-rank concave minimization problems.

Keywords: programming; nonlinear; algorithms (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1040.0151 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:52:y:2004:i:6:p:942-953

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().