Lattice-free sets,multi-branch split disjunctions,and mixed-integer programming

In this paper we study the relationship between valid inequalities for mixed-integer sets, lattice-free sets associated with these inequalities and the multi-branch split cuts introduced by Li and Richard (Discret Optim 5:724–734, 2008). By analyzing $n$ -dimensional lattice-free sets, we prove that for every integer $n$ there exists a positive integer $t$ such that every facet-defining inequality of the convex hull of a mixed-integer polyhedral set with $n$ integer variables is a $t$ -branch split cut. We use this result to give a finite cutting-plane algorithm to solve mixed-integer programs. We also show that the minimum value $t$ , for which all facets of polyhedral mixed-integer sets with $n$ integer variables can be generated as $t$ -branch split cuts, grows exponentially with $n$ . In particular, when $n=3$ , we observe that not all facet-defining inequalities are 6-branch split cuts.     

Minkowski Decomposition of Associahedra and Related Combinatorics

Realisations of associahedra with linear non-isomorphic normal fans can be obtained by alteration of the right-hand sides of the facet-defining inequalities from a classical permutahedron. These polytopes can be expressed as Minkowski sums and differences of dilated faces of a standard simplex as described by Ardila et al. (Discret Comput Geom, 43:841–854, 2010). The coefficients $y_I$ of such a Minkowski decomposition can be computed by Möbius inversion if tight right-hand sides $z_I$ are known not just for the facet-defining inequalities of the associahedron but also for all inequalities of the permutahedron that are redundant for the associahedron. We show for certain families of these associahedra: (1) How to compute the tight value $z_I$ for any inequality that is redundant for an associahedron but facet-defining for the classical permutahedron. More precisely, each value $z_I$ is described in terms of tight values $z_J$ of facet-defining inequalities of the corresponding associahedron determined by combinatorial properties of $I$ . (2) The computation of the values $y_I$ of Ardila, Benedetti & Doker can be significantly simplified and depends on at most four values $z_{a(I)},\,z_{b(I)},\,z_{c(I)}$ and $z_{d(I)}$ . (3) The four indices $a(I),\,b(I),\,c(I)$ and $d(I)$ are determined by the geometry of the normal fan of the associahedron and are described combinatorially. (4) A combinatorial interpretation of the values $y_I$ using a labeled $n$ -gon. This result is inspired from similar interpretations for vertex coordinates originally described by Loday and well-known interpretations for the $z_I$ -values of facet-defining inequalities.     

Fixed-charge transportation on a path: optimization, LP formulations and separation

In the fixed-charge transportation problem, the goal is to optimally transport goods from depots to clients when there is a fixed cost associated to transportation or, equivalently, to opening an arc in the underlying bipartite graph. We further motivate its study by showing that it is both a special case and a strong relaxation of the big-bucket multi-item lot-sizing problem, and a generalization of a simple variant of the single-node flow set. This paper is essentially a polyhedral analysis of the polynomially solvable special case in which the associated bipartite graph is a path. We give a $\mathcal O (n^3)$ -time optimization algorithm and a $\mathcal O (n^2)$ -size linear programming extended formulation. We describe a new class of inequalities that we call “path-modular” inequalities. We give two distinct proofs of their validity. The first one is direct and crucially relies on sub- and super-modularity of an associated set function. The second proof is by showing that the projection of the extended linear programming formulations onto the original variable space yields exactly the polyhedron described by the path-modular inequalities. Thus we also show that these inequalities suffice to describe the convex hull of the set of feasible solutions.     

On the partial order polytope of a digraph

We introduce the partial order polytope of a digraphD, defined as the convex hull of the incidence vectors of all transitive acyclic arc sets ofD. For this polytope we prove some classes of inequalities to be facet-defining and show that there is a polynomial separation algorithm for each of these classes. The results imply a polynomial separation algorithm for a class of valid inequalities of the clique partitioning polytope that includes the two-chorded odd cycle inequalities. The polyhedral results concerning the partial order polytope are of interest since a cutting plane based algorithm to solve the maximum weighted transitive acyclic subdigraph problem can be used to solve the maximum weighted acyclic subdigraph problem, the maximum weighted linear ordering problem and a flexible manufacturing problem. For the acyclic subdigraph polytope we show that the separation of simplet-reinforcedk-fence-inequalities is -complete.     

On the $${\mathcal {}}$$-free extension complexity of the TSP

It is known that the extension complexity of the TSP polytope for the complete graph \(K_n\) is exponential in n even if the subtour inequalities are excluded. In this article we study the polytopes formed by removing other subsets \({\mathcal {H}}\) of facet-defining inequalities of the TSP polytope. In particular, we consider the case when \({\mathcal {H}}\) is either the set of blossom inequalities or the simple comb inequalities. These inequalities are routinely used in cutting plane algorithms for the TSP. We show that the extension complexity remains exponential even if we exclude these inequalities. In addition we show that the extension complexity of polytope formed by all comb inequalities is exponential. For our proofs, we introduce a subclass of comb inequalities, called (h, t)-uniform inequalities, which may be of independent interest.     

On the sharpness of Bruen’s bound for intersection sets in Desarguesian affine spaces

In this note we investigate the sharpness of Bruen’s bound on the size of a t-fold blocking set in \(AG(n,q)\) with respect to the hyperplanes. We give a construction for t-fold blocking sets meeting Bruen’s bound with \(t=q-n+2\) . This construction is used further to find the minimal size of a t-fold affine blocking set with \(t=q-n+1\) . We prove that for blocking sets in the geometries \(AG(n,2)\) the difference between the size of an optimal t-fold blocking set and tn exceeds any given number. In particular, we deviate infinitely from Bruen’s bound as n goes to infinity. We conclude with a construction that gives t-fold blocking sets with \(t=q-n+3\) whose size is close to the lower bounds known so far.     

The triangle closure is a polyhedron

Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by Andersen et al. (Math Oper Res 35(1):233–256, 2010) and Averkov (Discret Optimiz 9(4):209–215, 2012), some basic questions have remained unresolved. For example, maximal lattice-free triangles are the natural family to study beyond the family of splits and it has been a standing open problem to decide whether the triangle closure is a polyhedron. In this paper, we show that when the number of integer variables $m=2$ the triangle closure is indeed a polyhedron and its number of facets can be bounded by a polynomial in the size of the input data. The techniques of this proof are also used to give a refinement of necessary conditions for valid inequalities being facet-defining due to Cornuéjols and Margot (Math Program 120:429–456, 2009) and obtain polynomial complexity results about the mixed integer hull.     

Non-ergodic \mathbb{Z}-periodic billiards and infinite translation surfaces

We give a criterion which proves non-ergodicity for certain infinite periodic billiards and directional flows on \(\mathbb{Z}\) -periodic translation surfaces. Our criterion applies in particular to a billiard in an infinite band with periodically spaced vertical barriers and to the Ehrenfest wind-tree model, which is a planar billiard with a \(\mathbb{Z}^{2}\) -periodic array of rectangular obstacles. We prove that, in these two examples, both for a full measure set of parameters of the billiard tables and for tables with rational parameters, for almost every direction the corresponding directional billiard flow is not ergodic and has uncountably many ergodic components. As another application, we show that for any recurrent \(\mathbb{Z}\) -cover of a square tiled surface of genus two the directional flow is not ergodic and has no invariant sets of finite measure for a full measure set of directions. In the language of essential values, we prove that the skew-products which arise as Poincaré maps of the above systems are associated to non-regular \(\mathbb{Z}\) -valued cocycles for interval exchange transformations.     

A projection subgradient method for solving optimization with variational inequality constraints

In this paper, we propose a projection subgradient method for solving some classical variational inequality problem over the set of solutions of mixed variational inequalities. Under the conditions that $T$ is a $\Theta $ -pseudomonotone mapping and $A$ is a $\rho $ -strongly pseudomonotone mapping, we prove the convergence of the algorithm constructed by projection subgradient method. Our algorithm can be applied for instance to some mathematical programs with complementarity constraints.     

Planar Point Sets With Large Minimum Convex Decompositions

We show the existence of sets with $n$ points ( $n\ge 4$ ) for which every convex decomposition contains more than $\frac{35}{32}n-\frac{3}{2}$ polygons, which refutes the conjecture that for every set of $n$ points there is a convex decomposition with at most $n+C$ polygons. For sets having exactly three extreme points we show that more than $n+\sqrt{2(n-3)}-4$ polygons may be necessary to form a convex decomposition.     

Branch-and-cut approaches for chance-constrained formulations of reliable network design problems

We study solution approaches for the design of reliably connected networks. Specifically, given a network with arcs that may fail at random, the goal is to select a minimum cost subset of arcs such the probability that a connectivity requirement is satisfied is at least $1 - \epsilon $ , where $\epsilon $ is a risk tolerance. We consider two types of connectivity requirements. We first study the problem of requiring an $s$ - $t$ path to exist with high probability in a directed graph. Then we consider undirected graphs, where we require the graph to be fully connected with high probability. We model each problem as a stochastic integer program with a joint chance constraint, and present two formulations that can be solved by a branch-and-cut algorithm. The first formulation uses binary variables to represent whether or not the connectivity requirement is satisfied in each scenario of arc failures and is based on inequalities derived from graph cuts in individual scenarios. We derive additional valid inequalities for this formulation and study their facet-inducing properties. The second formulation is based on probabilistic graph cuts, an extension of graph cuts to graphs with random arc failures. Inequalities corresponding to probabilistic graph cuts are sufficient to define the set of feasible solutions and violated inequalities in this class can be found efficiently at integer solutions, allowing this formulation to be solved by a branch-and-cut algorithm. Computational results demonstrate that the approaches can effectively solve instances on large graphs with many failure scenarios. In addition, we demonstrate that, by varying the risk tolerance, our model yields a rich set of solutions on the efficient frontier of cost and reliability.     

The Kakeya problem: a gap in the spectrum and classification of the smallest examples

Kakeya sets in the affine plane $\mathrm AG (2,q)$ are point sets that are the union of lines, one through every point on the line at infinity. The finite field Kakeya problem asks for the size of the smallest Kakeya sets and the classification of these Kakeya sets. In this article we present a new example of a small Kakeya set and we give the classification of the smallest Kakeya sets up to weight $\frac{q(q+2)}{2}+\frac{q}{4}$ , both in case $q$ even.     

New inequalities for q-ary constant-weight codes

Using double counting, we prove Delsarte inequalities for \(q\) -ary codes and their improvements. Applying the same technique to \(q\) -ary constant-weight codes, we obtain new inequalities for \(q\) -ary constant-weight codes.     

Triangle-Free Geometric Intersection Graphs with Large Chromatic Number

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $X$ X in $\mathbb{R }^2$ R 2 that is not an axis-aligned rectangle and for any positive integer $k$ k produces a family $\mathcal{F }$ F of sets, each obtained by an independent horizontal and vertical scaling and translation of $X$ X , such that no three sets in $\mathcal{F }$ F pairwise intersect and $\chi (\mathcal{F })>k$ χ ( F ) > k . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.     

A study of saturated tensor cone for symmetrizable Kac–Moody algebras

Let \(\mathfrak {g}\) be a symmetrizable Kac-Moody Lie algebra with the standard Cartan subalgebra \(\mathfrak {h}\) and the Weyl group \(W\) . Let \(P_+\) be the set of dominant integral weights. For \(\lambda \in P_+\) , let \(L(\lambda )\) be the integrable, highest weight (irreducible) representation of \(\mathfrak {g}\) with highest weight \(\lambda \) . For a positive integer \(s\) , define the saturated tensor semigroup as $$\begin{aligned} \Gamma _s:= \{(\lambda _1, \dots , \lambda _s,\mu )\in P_+^{s+1}: \exists \, N\ge 1 \,\text {with}\,L(N\mu )\subset L(N\lambda _1)\otimes \dots \otimes L(N\lambda _s)\}. \end{aligned}$$ The aim of this paper is to begin a systematic study of \(\Gamma _s\) in the infinite dimensional symmetrizable Kac-Moody case. In this paper, we produce a set of necessary inequalities satisfied by \(\Gamma _s\) . These inequalities are indexed by products in \(H^*(G^{\mathrm{min }}/B; \mathbb {Z})\) for \(B\) the standard Borel subgroup, where \(G^{\mathrm{min }}\) is the ‘minimal’ Kac-Moody group with Lie algebra \(\mathfrak {g}\) . The proof relies on the Kac-Moody analogue of the Borel-Weil theorem and Geometric Invariant Theory (specifically the Hilbert-Mumford index). In the case that \(\mathfrak {g}\) is affine of rank 2, we show that these inequalities are necessary and sufficient. We further prove that any integer \(d>0\) is a saturation factor for \(A^{(1)}_1\) and 4 is a saturation factor for \(A^{(2)}_2\) .     

Weighted Dunkl transform inequalities and application on radial Besov spaces

In Dunkl theory on $\mathbb R ^d$ which generalizes classical Fourier analysis, we prove first weighted inequalities for certain Hardy-type averaging operators. In particular, we deduce for specific choices of the weights the $d$ -dimensional Hardy inequalities whose constants are sharp and independent of $d$ . Second, we use the weight characterization of the Hardy operator to prove weighted Dunkl transform inequalities. As consequence, we obtain Pitt’s inequality which gives an integrability theorem for this transform on radial Besov spaces.