This paper considers a family of cutting planes, recently developed for mixed 0-1 polynomial programs and shows that they define facets for the maximum edge-weighted clique problem. There exists a polynomial time exact separation algorithm for these in- equalities. The result of this paper may contribute to the development of more efficient algorithms for the … Read more
We focus on a class of nonconvex cooperative optimization problems that involve multiple participants. We study the duality framework and provide geometric and analytic character- izations of the duality gap. The dual problem is related to a market setting in which each participant pursuits self interests at a given price of common goods. The duality … Read more
We present pure-integer Gomory cuts in a way so that they are derived with respect to a “dual form” pure-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. The input integer problem is not in standard form, and so the cuts are derived a bit differently. In … Read more
A key step in solving minimax distributionally robust optimization (DRO) problems is to reformulate the inner maximization w.r.t. probability measure as a semiinfinite programming problem through Lagrange dual. Slater type conditions have been widely used for zero dual gap when the ambiguity set is defined through moments. In this paper, we investigate effective ways for … Read more
This paper proposes three strong second order cone programming (SOCP) relaxations for the AC optimal power flow (OPF) problem. These three relaxations are incomparable to each other and two of them are incomparable to the standard SDP relaxation of OPF. Extensive computational experiments show that these relaxations have numerous advantages over existing convex relaxations in … Read more
Given a mixed-integer set defined by linear inequalities and integrality requirements on some of the variables, we consider extended formulations of its continuous (LP) relaxation and study the effect of adding cutting planes in the extended space. In terms of optimization, extended LP formulations do not lead to better bounds as their projection onto the … Read more
Motivated by stochastic 0-1 integer programming problems with an expected utility objective, we study the mixed-integer nonlinear set: $P = \cset{(w,x)\in \reals \times \set{0,1}^N}{w \leq f(a’x + d), b’x \leq B}$ where $N$ is a positive integer, $f:\reals \mapsto \reals$ is a concave function, $a, b \in \reals^N$ are nonnegative vectors, $d$ is a real … Read more
It is well-known that optimizing network topology by switching on and off transmission lines improves the efficiency of power delivery in electrical networks. In fact, the USA Energy Policy Act of 2005 (Section 1223) states that the U.S. should “encourage, as appropriate, the deployment of advanced transmission technologies” including “optimized transmission line configurations”. As such, … Read more
Split cuts form a well-known class of valid inequalities for mixed-integer programming problems. Cook, Kannan and Schrijver (1990) showed that the split closure of a rational polyhedron $P$ is again a polyhedron. In this paper, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We … Read more
Bansal and Kianfar introduced continuous multi-mixing set where the coefficients satisfy the so-called n-step MIR conditions and developed facet-defining inequalities for this set. In this paper, we first generalize their inequalities for the continuous multi-mixing set with general coefficients (where no conditions are imposed on the coefficients) and show that they are facet-defining in many … Read more