Many interesting properties of polynomials are closely related to the geometry of their Newton polytopes. In this article we analyze the coercivity on $\mathbb{R}^n$ of multivariate polynomials $f\in \mathbb{R}[x]$ in terms of their Newton polytopes. In fact, we introduce the broad class of so-called gem regular polynomials and characterize their coercivity via conditions imposed on … Read more
In this paper, we describe the circuit polytope on series-parallel graphs. We first show the existence of a compact extended formulation. Though not being explicit, its construction process helps us to inductively provide the description in the original space. As a consequence, using the link between bonds and circuits in planar graphs, we also describe … Read more
Steplength thresholds for invariance preserving of three types of discretization methods on a polyhedron are considered. For Taylor approximation type discretization methods we prove that a valid steplength threshold can be obtained by finding the first positive zeros of a finite number of polynomial functions. Further, a simple and efficient algorithm is proposed to numerically … Read more
This paper provides a study of integer linear programming formulations for the diameter constrained spanning tree problem (DMSTP) in the natural space of edge design variables. After presenting a straightforward model based on the well known jump inequalities a new stronger family of circular-jump inequalities is introduced. These inequalities are further generalized in two ways: … Read more
This note studies compact representations of linear on/off constraints in mixed-integer linear optimization. A characterization of the convex hull of linear disjunctions is given in the space of original variables. This result can improve formulations of mixed-integer linear programs featuring on/off constraints by reducing the integrality gap in a Branch and Bound approach. Citation @article{, … Read more
Infeasible network flow problems with supplies and demands can be characterized via violated cut-inequalities of the classical Gale-Hoffman theorem. Written as a linear program, irreducible infeasible subsystems (IISs) provide a different means of infeasibility characterization. In this article, we answer a question left open in the literature, by showing a one-to-one correspondence between IISs and … Read more
We consider the natural generalizations of blocking and anti-blocking polyhedra in infinite dimensions, and study issues related to duality and integrality of extreme points for these sets. Using appropriate finite truncations, we give conditions under which complementary slackness holds for primal-dual pairs of the infi nite linear programming problems associated with infi nite blocking and anti-blocking polyhedra. … Read more
We present an exact method, based on an arc-flow formulation with side constraints, for solving bin packing and cutting stock problems — including multi-constraint variants — by simply representing all the patterns in a very compact graph. Our method includes a graph compression algorithm that usually reduces the size of the underlying graph substantially without … Read more
A recurrent task in mathematical programming requires optimizing polytopes with prohibitively-many constraints, e.g., the primal polytope in cutting-plane methods or the dual polytope in Column Generation (CG). This paper is devoted to the ray projection technique for optimizing such polytopes: start from a feasible solution and advance on a given ray direction until intersecting a … Read more
In this work, we introduce and study the forbidden-vertices 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 k-best basic solutions to a linear … Read more