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
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
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
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
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
We provide a polynomial time cutting plane algorithm based on split cuts to solve integer programs in the plane. We also prove that the split closure of a polyhedron in the plane has polynomial size. Article Download View Split cuts in the plane
\(\) 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 … Read more
Cutting planes accelerate branch-and-bound search primarily by cutting off fractional solutions of the linear programming (LP) relaxation, resulting in tighter bounds for pruning the search tree. Yet cutting planes can also reduce backtracking by excluding inconsistent partial assignments that occur in the course of branching. A partial assignment is inconsistent with a constraint set when … Read more
We consider non-convex mixed-integer quadratic programs in which all variables are explicitly bounded. Many exact methods for such problems use additional variables, representing products of pairs of original variables. We study the convex hull of feasible solutions in this extended space. Some other approaches use bit representation to convert bounded integer variables into binary variables. … Read more
We describe the automatic Benders decomposition implemented in the commercial solver IBM CPLEX. We propose several improvements to the state-of-the-art along two lines: making a numerically robust method able to deal with the general case and improving the efficiency of the method on models amenable to decomposition. For the former, we deal with: unboundedness, failures … Read more