
We explore the lifting question in the context of cutgenerating functions.
Most of the prior literature on this question focuses on cutgenerating
functions that have the unique lifting property. We develop a general theory
for understanding the lifting question for cutgenerating functions that do not
necessarily have the unique lifting property.

While many classes of cuttingplanes are at the disposal of integer
programming solvers, our scientific understanding is far from complete with
regards to cuttingplane selection, i.e., the task of selecting a portfolio of
cuttingplanes to be added to the LP relaxation at a given node of the
branchandbound tree. In this paper we review the different classes of
cuttingplanes available, known theoretical results about their relative
strength, important issues pertaining to cut selection, and discuss some
possible new directions to be pursued in order to accomplish cuttingplane
selection in a more principled manner. Finally, we review some lines of work
that we undertook to provide a preliminary theoretical underpinning for some of
the issues related to cut selection.

In this paper, we present lower bounds on the rank of the split closure, the
multibranch closure and the latticefree closure for packing sets as a
function of the integrality gap. We also provide a similar lower bound on the
split rank of covering polyhedra. These results indicate that whenever the
integrality gap is high, these classes of cutting planes must necessarily be
applied for many rounds in order to obtain the integer hull.

A bipartite bilinear program (BBP) is a quadratically constrained quadratic
optimization problem where the variables can be partitioned into two sets such
that fixing the variables in any one of the sets results in a linear program.
We propose a new second order cone representable (SOCP) relaxation for BBP,
which we show is stronger than the standard SDP relaxation intersected with the
boolean quadratic polytope. We then propose a new branching rule inspired by
the construction of the SOCP relaxation. We describe a new application of BBP
called as the finite element model updating problem, which is a fundamental
problem in structural engineering. Our computational experiments on this
problem class show that the new branching rule together with an polyhedral
outer approximation of the SOCP relaxation outperforms a stateoftheart
commercial global solver in obtaining dual bounds.

The floor layout problem (FLP) tasks a designer with positioning a collection
of rectangular boxes on a fixed floor in such a way that minimizes total
communication costs between the components. While several mixed integer
programming (MIP) formulations for this problem have been developed, it remains
extremely challenging from a computational perspective. This work takes a
systematic approach to constructing MIP formulations and valid inequalities for
the FLP that unifies and recovers all known formulations for it. In addition,
the approach yields new formulations that can provide a significant
computational advantage and can solve previously unsolved instances. While the
construction approach focuses on the FLP, it also exemplifies generic
formulation techniques that should prove useful for broader classes of
problems.

For many mixedinteger programming (MIP) problems, highquality dual bounds
can be obtained either through advanced formulation techniques coupled with a
stateoftheart MIP solver, or through semidefinite programming (SDP)
relaxation hierarchies. In this paper, we introduce an alternative bounding
approach that exploits the "combinatorial implosion" effect by solving portions
of the original problem and aggregating this information to obtain a global
dual bound. We apply this technique to the onedimensional and twodimensional
floor layout problems and compare it with the bounds generated by both
stateoftheart MIP solvers and by SDP relaxations. Specifically, we prove
that the bounds obtained through the proposed technique are at least as good as
those obtained through SDP relaxations, and present computational results that
these bounds can be significantly stronger and easier to compute than these
alternative strategies, particularly for very difficult problem instances.

Alternating current optimal power flow (AC OPF) is one of the most
fundamental optimization problems in electrical power systems. It can be
formulated as a semidefinite program (SDP) with rank constraints. Solving AC
OPF, that is, obtaining near optimal primal solutions as well as high quality
dual bounds for this nonconvex program, presents a major computational
challenge to today's power industry for the realtime operation of largescale
power grids. In this paper, we propose a new technique for reformulation of the
rank constraints using both principal and nonprincipal 2by2 minors of the
involved Hermitian matrix variable and characterize all such minors into three
types. We show the equivalence of these minor constraints to the physical
constraints of voltage angle differences summing to zero over three and
fourcycles in the power network. We study secondorder conic programming
(SOCP) relaxations of this minor reformulation and propose strong cutting
planes, convex envelopes, and bound tightening techniques to strengthen the
resulting SOCP relaxations. We then propose an SOCPbased spatial
branchandcut method to obtain the global optimum of AC OPF. Extensive
computational experiments show that the proposed algorithm significantly
outperforms the stateoftheart SDPbased OPF solver and on a simple personal
computer is able to obtain on average a 0.71% optimality gap in no more than
720 seconds for the most challenging power system instances in the literature.

In this paper, we study cut generating functions for conic sets. Our first
main result shows that if the conic set is bounded, then cut generating
functions for integer linear programs can easily be adapted to give the integer
hull of the conic integer program. Then we introduce a new class of cut
generating functions which are nondecreasing with respect to secondorder
cone. We show that, under some minor technical conditions, these functions
together with integer linear programmingbased functions are sufficient to
yield the integer hull of intersections of conic sections in $\mathbb{R}^2$.

Feasibility pump (FP) is a successful primal heuristic for mixedinteger
linear programs (MILP). The algorithm consists of three main components:
rounding fractional solution to a mixedinteger one, projection of infeasible
solutions to the LP relaxation, and a randomization step used when the
algorithm stalls. While many generalizations and improvements to the original
Feasibility Pump have been proposed, they mainly focus on the rounding and
projection steps.
We start a more indepth study of the randomization step in Feasibility Pump.
For that, we propose a new randomization step based on the WalkSAT algorithm
for solving SAT instances. First, we provide theoretical analyses that show the
potential of this randomization step; to the best of our knowledge, this is the
first time any theoretical analysis of runningtime of Feasibility Pump or its
variants has been conducted. Moreover, we also conduct computational
experiments incorporating the proposed modification into a stateoftheart
Feasibility Pump code that reinforce the practical value of the new
randomization step.

In this paper, we study the strength of ChvatalGomory (CG) cuts and more
generally aggregation cuts for packing and covering integer programs (IPs).
Aggregation cuts are obtained as follows: Given an IP formulation, we first
generate a single implied inequality using aggregation of the original
constraints, then obtain the integer hull of the set defined by this single
inequality with variable bounds, and finally use the inequalities describing
the integer hull as cuttingplanes. Our first main result is to show that for
packing and covering IPs, the CG and aggregation closures can be 2approximated
by simply generating the respective closures for each of the original
formulation constraints, without using any aggregations. On the other hand, we
use computational experiments to show that aggregation cuts can be arbitrarily
stronger than cuts from individual constraints for general IPs. The proof of
the above stated results for the case of covering IPs with bounds require the
development of some new structural results, which may be of independent
interest. Finally, we examine the strength of cuts based on k different
aggregation inequalities simultaneously, the socalled multirow cuts, and show
that every packing or covering IP with a large integrality gap also has a large
kaggregation closure rank. In particular, this rank is always at least of the
order of the logarithm of the integrality gap.

We investigate how well the graph of a bilinear function
$b:[0,1]^n\to\mathbb{R}$ can be approximated by its McCormick relaxation. In
particular, we are interested in the smallest number $c$ such that the
difference between the concave upper bounding and convex lower bounding
functions obtained from the McCormick relaxation approach is at most $c$ times
the difference between the concave and convex envelopes. Answering a question
of Luedtke, Namazifar and Linderoth, we show that this factor $c$ cannot be
bounded by a constant independent of $n$. More precisely, we show that for a
random bilinear function $b$ we have asymptotically almost surely
$c\geqslant\sqrt n/4$. On the other hand, we prove that $c\leqslant
600\sqrt{n}$, which improves the linear upper bound proved by Luedtke,
Namazifar and Linderoth. In addition, we present an alternative proof for a
result of Misener, Smadbeck and Floudas characterizing functions $b$ for which
the McCormick relaxation is equal to the convex hull.

As the modern transmission control and relay technologies evolve,
transmission line switching has become an important option in power system
operators' toolkits to reduce operational cost and improve system reliability.
Most recent research has relied on the DC approximation of the power flow model
in the optimal transmission switching problem. However, it is known that DC
approximation may lead to inaccurate flow solutions and also overlook stability
issues. In this paper, we focus on the optimal transmission switching problem
with the full AC power flow model, abbreviated as AC OTS. We propose a new
exact formulation for AC OTS and its mixedinteger secondorder conic
programming (MISOCP) relaxation. We improve this relaxation via several types
of strong valid inequalities inspired by the recent development for the closely
related AC Optimal Power Flow (AC OPF) problem. We also propose a practical
algorithm to obtain high quality feasible solutions for the AC OTS problem.
Extensive computational experiments show that the proposed formulation and
algorithms efficiently solve IEEE standard and congested instances and lead to
significant cost benefits with provably tight bounds.

In this paper, we present an analysis of the strength of sparse
cuttingplanes for mixed integer linear programs (MILP) with sparse
formulations. We examine three kinds of problems: packing problems, covering
problems, and more general MILPs with the only assumption that the objective
function is nonnegative. Given a MILP instance of one of these three types,
assume that we decide on the support of cuttingplanes to be used and the
strongest inequalities on these supports are added to the linear programming
relaxation. Call the optimal objective function value of the linear programming
relaxation together with these cuts as $z^{cut}$. We present bounds on the
ratio of $z^{cut}$ and the optimal objective function value of the MILP that
depends only on the sparsity structure of the constraint matrix and the support
of sparse cuts selected, that is, these bounds are completely data independent.
These results also shed light on the strength of scenariospecific cuts for two
stage stochastic MILPs.

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 the literature: (i) their solution quality is extremely close to
that of the SDP relaxations (the best one is within 99.96% of the SDP
relaxation on average for all the IEEE test cases) and consistently outperforms
previously proposed convex quadratic relaxations of the OPF problem, (ii) the
solutions from the strong SOCP relaxations can be directly used as a warm start
in a local solver such as IPOPT to obtain a high quality feasible OPF solution,
and (iii) in terms of computation times, the strong SOCP relaxations can be
solved an order of magnitude faster than standard SDP relaxations. For example,
one of the proposed SOCP relaxations together with IPOPT produces a feasible
solution for the largest instance in the IEEE test cases (the 3375bus system)
and also certifies that this solution is within 0.13% of global optimality, all
this computed within 157.20 seconds on a modest personal computer. Overall, the
proposed strong SOCP relaxations provide a practical approach to obtain
feasible OPF solutions with extremely good quality within a time framework that
is compatible with the realtime operation in the current industry practice.

It is wellknown 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, many authors have studied the problem of determining
an optimal set of transmission lines to switch off to minimize the cost of
meeting a given power demand under the direct current (DC) model of power flow.
This problem is known in the literature as the DirectCurrent Optimal
Transmission Switching Problem (DCOTS). Most research on DCOTS has focused on
heuristic algorithms for generating quality solutions or on the application of
DCOTS to crucial operational and strategic problems such as contingency
correction, realtime dispatch, and transmission expansion. The mathematical
theory of the DCOTS problem is less welldeveloped. In this work, we formally
establish that DCOTS is NPHard, even if the power network is a
seriesparallel graph with at most one load/demand pair. Inspired by Kirchoff's
Voltage Law, we give a cyclebased formulation for DCOTS, and we use the new
formulation to build a cycleinduced relaxation. We characterize the convex
hull of the cycleinduced relaxation, and the characterization provides strong
valid inequalities that can be used in a cuttingplane approach to solve the
DCOTS. We give details of a practical implementation, and we show promising
computational results on standard benchmark instances.

It is wellknown that the intersection of the matching polytope with a
cardinality constraint is integral [8]. We prove a similar result for the
polytope corresponding to the transportation problem with market choice (TPMC)
(introduced in [4]) when the demands are in the set $\{1,2\}$. This result
generalizes the result regarding the matching polytope and also implies that
some special classes of minimum weight perfect matching problem with a
cardinality constraint on a subset of edges can be solved in polynomial time.

It has been recently proven that the semidefinite programming (SDP)
relaxation of the optimal power flow problem over radial networks is exact
under technical conditions such as not including generation lower bounds or
allowing load oversatisfaction. In this paper, we investigate the situation
where generation lower bounds are present. We show that even for a twobus
onegenerator system, the SDP relaxation can have all possible approximation
outcomes, that is (1) SDP relaxation may be exact or (2) SDP relaxation may be
inexact or (3) SDP relaxation may be feasible while the OPF instance may be
infeasible. We provide a complete characterization of when these three
approximation outcomes occur and an analytical expression of the resulting
optimality gap for this twobus system. In order to facilitate further
research, we design a library of instances over radial networks in which the
SDP relaxation has positive optimality gap. Finally, we propose valid
inequalities and variable bound tightening techniques that significantly
improve the computational performance of a global optimization solver. Our work
demonstrates the need of developing efficient global optimization methods for
the solution of OPF even in the simple but fundamental case of radial networks.

Motivated by the need to better understand the properties of sparse
cuttingplanes used in mixed integer programming solvers, the paper [2] studied
the idealized problem of how well a polytope is approximated by the use of
sparse valid inequalities. As an extension to this work, we study the following
less idealized questions in this paper: (1) Are there integer programs, such
that sparse inequalities do not approximate the integer hull well even when
added to a linear programming relaxation? (2) Are there polytopes, where the
quality of approximation by sparse inequalities cannot be significantly
improved by adding a budgeted number of arbitrary (possibly dense) valid
inequalities? (3) Are there polytopes that are difficult to approximate under
every rotation? (4) Are there polytopes that are difficult to approximate in
all directions using sparse inequalities? We answer each of the above questions
in the positive.

Mixedinteger quadratic programming is the problem of optimizing a quadratic
function over points in a polyhedral set where some of the components are
restricted to be integral. In this paper, we prove that the decision version of
mixedinteger quadratic programming is in NP, thereby showing that it is
NPcomplete. This is established by showing that if the decision version of
mixedinteger quadratic programming is feasible, then there exists a solution
of polynomial size. This result generalizes and unifies classical results that
quadratic programming is in NP and integer linear programming is in NP.

Sparse cuttingplanes are often the ones used in mixedinteger programing
(MIP) solvers, since they help in solving the linear programs encountered
during branch&bound more efficiently. However, how well can we approximate
the integer hull by just using sparse cuttingplanes? In order to understand
this question better, given a polyope $P$ (e.g. the integer hull of a MIP), let
$P^k$ be its best approximation using cuts with at most $k$ nonzero
coefficients. We consider $d(P, P^k) = \max_{x \in P^k} \left(min_{y \in P} \
x  y\\right)$ as a measure of the quality of sparse cuts.
In our first result, we present general upper bounds on $d(P, P^k)$ which
depend on the number of vertices in the polytope and exhibits three phases as
$k$ increases. Our bounds imply that if $P$ has polynomially many vertices,
using half sparsity already approximates it very well. Second, we present a
lower bound on $d(P, P^k)$ for random polytopes that show that the upper bounds
are quite tight. Third, we show that for a class of hard packing IPs, sparse
cuttingplanes do not approximate the integer hull well, that is $d(P, P^k)$ is
large for such instances unless $k$ is very close to $n$. Finally, we show that
using sparse cuttingplanes in extended formulations is at least as good as
using them in the original polyhedron, and give an example where the former is
actually much better.

In this work, we introduce and study the forbiddenvertices problem. Given a
polytope P and a subset X of its vertices, we study the complexity of linear
optimization over the subset of vertices of P that are not contained in X. This
problem is closely related to finding the kbest basic solutions to a linear
problem. We show that the complexity of the problem changes significantly
depending on the encoding of both P and X. We provide additional tractability
results and extended formulations when P has binary vertices only. Some
applications and extensions to integral polytopes are discussed.

In this paper, we show that the ChvatalGomory closure of a compact convex
set is a rational polytope. This resolves an open question discussed in
Schrijver [Schrijver 80'] and generalizes the same result for the case of
rational polytopes [Schrijver 80'], rational ellipsoids [DeyVielma 10'] and
strictly convex sets [DadushDeyVielma 10']. In particular, it shows that the
CG closure of an irrational polytope is a rational polytope, which was the open
question in [Schrijver 80'].