×

Cutting planes for low-rank-like concave minimization problems. (English) Zbl 1165.90595

Summary: 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, H. Konno [J. Glob. Optim. 13, No. 3, 225–240 (1998; Zbl 0912.90229)] 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.

MSC:

90C26 Nonconvex programming, global optimization
90C30 Nonlinear programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Citations:

Zbl 0912.90229
PDFBibTeX XMLCite
Full Text: DOI