Cutting Plane Approaches

Closing the Gap in Linear Bilevel Optimization: A New Valid Primal-Dual Inequality

Categories (Mixed) Integer Linear Programming, Complementarity and Variational Inequalities, Cutting Plane Approaches Tags , , ,

Linear bilevel optimization problems are often tackled by replacing the linear lower-level problem with its Karush–Kuhn–Tucker (KKT) conditions. The resulting single-level problem can be solved in a branch-and-bound fashion by branching on the complementarity constraints of the lower-level problem’s optimality conditions. While in mixed-integer single-level optimization branch- and-cut has proven to be a powerful extension … Read more

On the exact separation of cover inequalities of maximum depth

Categories 0-1 Programming, Cutting Plane Approaches, Dynamic Programming

We investigate the problem of exactly separating cover inequalities of maximum depth and we develop a pseudo-polynomial-time algorithm for this purpose. Compared to the standard method based on the maximum violation, computational experiments carried out on knapsack and multi-dimensional knapsack instances show that, with a cutting-plane method based on the maximum-depth criterion, we can optimize … Read more

Submodular maximization of concave utility functions composed with a set-union operator with applications to maximal covering location problems

Categories Cutting Plane Approaches, Integer Programming, Nonlinear Optimization Tags , ,

We study a family of discrete optimization problems asking for the maximization of the expected value of a concave, strictly increasing, and differentiable function composed with a set-union operator. The expected value is computed with respect to a set of coefficients taking values from a discrete set of scenarios. The function models the utility function … Read more

The Star Degree Centrality Problem: A Decomposition Approach

Categories 0-1 Programming, Cutting Plane Approaches, Network Optimization Tags , ,

We consider the problem of identifying the induced star with the largest cardinality open neighborhood in a graph. This problem, also known as the star degree centrality (SDC) problem, has been shown to be 𝒩𝒫-complete. In this work, we first propose a new integer programming (IP) formulation, which has a fewer number of constraints and … Read more

Strong Relaxations for Continuous Nonlinear Programs Based on Decision Diagrams

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Global Optimization

Over the past decade, Decision Diagrams (DDs) have risen as a powerful modeling tool to solve discrete optimization problems. The extension of this emerging concept to continuous problems, however, has remained a challenge, posing a limitation on its applicability scope. In this paper, we introduce a novel framework that utilizes DDs to model continuous programs. … Read more

A Combinatorial Cut-and-Lift Procedure with an Application to 0-1 Chance Constraints

Categories 0-1 Programming, Cutting Plane Approaches, Second-Order Cone Programming Tags , , ,

Cut generation and lifting are key components for the performance of state-of-the-art mathematical programming solvers. This work proposes a new general cut-and-lift procedure that exploits the combinatorial structure of 0-1 problems via a binary decision diagram (BDD) encoding of their constraints. We present a general framework that can be applied to a large range of … Read more

A Polyhedral Approach to Bisubmodular Function Minimization

Categories 0-1 Programming, Cutting Plane Approaches, Polyhedra

We consider minimization problems with bisubmodular objective functions. We propose a class of valid inequalities, which we call the poly-bimatroid inequalities and prove that these inequalities, along with trivial bound constraints, fully describe the convex hull of the epigraph of a bisubmodular function. We develop a cutting plane algorithm for general bisubmodular minimization problems using … Read more

Complexity of cutting planes and branch-and-bound in mixed-integer optimization

Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms, Cutting Plane Approaches Tags , ,

We investigate the theoretical complexity of branch-and-bound (BB) and cutting plane (CP) algorithms for mixed-integer optimization. In particular, we study the relative efficiency of BB and CP, when both are based on the same family of disjunctions. We extend a result of Dash to the nonlinear setting which shows that for convex 0/1 problems, CP … Read more

A Finitely Convergent Disjunctive Cutting Plane Algorithm for Bilinear Programming

Categories (Mixed) Integer Nonlinear Programming, Cutting Plane Approaches, Quadratic Programming Tags , , , ,

In this paper we present and analyze a finitely-convergent disjunctive cutting plane algorithm to obtain an \(\epsilon\)-optimal solution or detect infeasibility of a general nonconvex continuous bilinear program. While the cutting planes are obtained in a manner similar to Saxena, Bonami, and Lee [Math. Prog. 130: 359–413, 2011] and Fampa and Lee [J. Global Optim. … Read more