Multiple-Periods Locally-Facet-Based MIP Formulations for the Unit Commitment Problem

The thermal unit commitment (UC) problem has historically been formulated as a mixed integer quadratic programming (MIQP), which is difficult to solve efficiently, especially for large-scale systems. The tighter characteristic reduces the search space, therefore, as a natural consequence, significantly reduces the computational burden. In literatures, many tightened formulations for a single unit with parts … Read more

Integer linear programming formulations for the minimum connectivity inference problem and model reduction principles

The minimum connectivity inference (MCI) problem represents an NP-hard generalization of the well-known minimum spanning tree problem. Given a set of vertices and a finite collection of subsets (of this vertex set), the MCI problem requires to find an edge set of minimal cardinality so that the vertices of each subset are connected. Although the … Read more

On Dantzig figures from lexicographic orders

We consider two families of $d$-polytopes defined as convex hulls of initial subsets for the graded lexicographic (grlex) and graded reverse lexicographic (grevlex) orders on $\mathbb{Z}^{d}_{\geq 0}$. Our considerations are motivated by the nice properties of the lex polytopes which were studied in relation to optimization problems. We show that the grlex and grevlex polytopes … Read more

A Study of Three-Period Ramp-Up Polytope

We study the polyhedron of the unit commitment problem, and consider a relaxation involving the ramping constraints. We study the three-period ramp-up polytope, and describe the convex-hull using a new class of inequalities. Citation [1] J. Ostrowski, M. F. Anjos, and A. Vannelli, \Tight mixed integer linear programming formulations for the unit commitment problem,” Power … Read more

Steiner Trees with Degree Constraints: Structural Results and an Exact Solution Approach

In this paper we study the Steiner tree problem with degree constraints. Motivated by an application in computational biology we first focus on binary Steiner trees in which all node degrees are required to be at most three. We then present results for general degree-constrained Steiner trees. It is shown that finding a binary Steiner … Read more

Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

Recently, Todd got a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the … Read more

A tight iteration-complexity upper bound for the MTY predictor-corrector algorithm via redundant Klee-Minty cubes

It is an open question whether there is an interior-point algorithm for linear optimization problems with a lower iteration-complexity than the classical bound $\mathcal{O}(\sqrt{n} \log(\frac{\mu_1}{\mu_0}))$. This paper provides a negative answer to that question for a variant of the Mizuno-Todd-Ye predictor-corrector algorithm. In fact, we prove that for any $\epsilon >0$, there is a redundant … Read more

Which Nonnegative Matrices Are Slack Matrices?

In this paper we characterize the slack matrices of cones and polytopes among all nonnegative matrices. This leads to an algorithm for deciding whether a given matrix is a slack matrix. The underlying decision problem is equivalent to the polyhedral verifi cation problem whose complexity is unknown. Citation April 2013 Article Download View Which Nonnegative Matrices … Read more

Polytopes of Minimum Positive Semidefinite Rank

The positive semidefinite (psd) rank of a polytope is the smallest $k$ for which the cone of $k \times k$ real symmetric psd matrices admits an affine slice that projects onto the polytope. In this paper we show that the psd rank of a polytope is at least the dimension of the polytope plus one, … Read more

Containment problems for polytopes and spectrahedra

We study the computational question whether a given polytope or spectrahedron $S_A$ (as given by the positive semidefiniteness region of a linear matrix pencil $A(x)$) is contained in another one $S_B$. First we classify the computational complexity, extending results on the polytope/poly\-tope-case by Gritzmann and Klee to the polytope/spectrahedron-case. For various restricted containment problems, NP-hardness … Read more