polytope

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

  • Linfeng Yang
  • Shifei Chen
  • Zhaoyang Dong
    • Categories (Mixed) Integer Nonlinear Programming, Applications - OR and Management Sciences, Polyhedra Tags , , , , , , ,

    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

  • Muhammad Abid Dar
  • Andreas Fischer
  • John Martinovic
  • Guntram Scheithauer
    • Categories (Mixed) Integer Linear Programming, Polyhedra Tags , , , ,

    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 graded lexicographic orders

  • Akshay Gupte
  • Svetlana Poznanovic
    • Categories Integer Programming, Polyhedra Tags , , , ,

    We construct two families of Dantzig figures, which are $d$-dimensional polytopes with $2d$ facets and an antipodal vertex pair, from convex hulls of initial subsets for the graded lexicographic (grlex) and graded reverse lexicographic (grevlex) orders on $\mathbb{Z}^{d}_{\geq 0}$. These polytopes have the same number of vertices $O(d^2)$ and the same number of edges $O(d^3)$, … Read more

    A Study of Three-Period Ramp-Up Polytope

  • Deepak Rajan
  • Liu Sheng
    • Categories (Mixed) Integer Linear Programming, Scheduling Tags ,

    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 Systems, … Read more

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

  • Frauke Liers
  • Alexander Martin
  • Susanne Pape
    • Categories Branch and Cut Algorithms, Polyhedra Tags , , , ,

    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

  • Tomonari Kitahara
  • Noriyoshi Sukegawa
    • Categories Linear Programming Tags , ,

    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

  • Murat Mut
  • Tamás Terlaky
    • Categories Linear Programming Tags , , , , ,

    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?

  • João Gouveia
  • Volker Kaibel
  • R. Grappe
  • K. Pashkovich
  • Richard Z. Robinson
  • Rekha R. Thomas
    • Categories Linear Programming, Polyhedra Tags , , ,

    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. CitationApril 2013ArticleDownload View PDF

    Polytopes of Minimum Positive Semidefinite Rank

  • João Gouveia
  • Richard Z. Robinson
  • Rekha R. Thomas
    • Categories Polyhedra, Semi-definite Programming Tags , , , ,

    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

  • Kai Kellner
  • Thorsten Theobald
  • Christian Trabandt
    • Categories Polyhedra, Semi-definite Programming Tags , , , , ,

    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