Klein polyhedra and relative minima of lattices

We prove that in ?³, the relative minima of almost any lattice belong to the surface of the corresponding Klein polyhedron. We also prove, for almost any lattice in ?³, that the set of relative minima with nonnegative coordinates coincides with the union of the set of extremal points of the Klein polyhedron and a set of special points belonging to the triangular faces of the Klein polyhedron.     

Some properties of convex hulls of integer points contained in general convex sets

In this paper, we study properties of general closed convex sets that determine the closedness and polyhedrality of the convex hull of integer points contained in it. We first present necessary and sufficient conditions for the convex hull of integer points contained in a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the convex hull of integer points in general convex sets to be a polyhedron. This result generalizes the well-known result due to Meyer (Math Program 7:223–225, 1974). Under a simple technical assumption, we show that these sufficient conditions are also necessary for the convex hull of integer points contained in general convex sets to be a polyhedron.     

Complexity of linear relaxations in integer programming

Mathematical Programming - For a set X of integer points in a polyhedron, the smallest number of facets of any polyhedron whose set of integer points coincides with X is called the...     

A multidimensional generalization of Lagrange’s theorem on continued fractions

A multidimensional geometric analog of Lagrange’s theorem on continued fractions is proposed. The multidimensional generalization of the geometric interpretation of a continued fraction uses the notion of a Klein polyhedron, that is, the convex hull of the set of nonzero points in the lattice ? ⁿ contained inside some n-dimensional simplicial cone with vertex at the origin. A criterion for the semiperiodicity of the boundary of a Klein polyhedron is obtained, and a statement about the nonempty intersection of the boundaries of the Klein polyhedra corresponding to a given simplicial cone and to a certain modification of this cone is proved.     

Sails and Hilbert bases

A Klein polyhedron is the convex hull of the nonzero integral points of a simplicial coneC⊂ ℝⁿ. There are relationships between these polyhedra and the Hilbert bases of monoids of integral points contained in a simplicial cone. In the two-dimensional case, the set of integral points lying on the boundary of a Klein polyhedron contains a Hilbert base of the corresponding monoid. In general, this is not the case if the dimension is greater than or equal to three (e.g., [2]). However, in the three-dimensional case, we give a characterization of the polyhedra that still have this property. We give an example of such a sail and show that our criterion does not hold if the dimension is four. CEREMADE, University Paris 9. Translated from Funktsional'nyi Analiz i Ego Prilozheniya, Vol. 34, No. 2, pp. 43–49, April–June, 2000. Translated by J.-O. Moussafir     

DETERMINING THE DISCRIMINATING DOMAIN FOR HYBRID LINEAR DIFFERENTIAL GAME WITH TWO PLAYERS AND TWO TARGETS

This paper studies a bounded discriminating domain for hybrid linear differential game with two players and two targets using viability theory. First of all,we prove that the convex hull of a closed set is also a discriminating domain if the set is a discriminating domain.Secondly,in order to determine that a bounded polyhedron is a discriminating domain,we give a result that it only needs to verify that the extreme points of the polyhedron meet the viability conditions. The difference between our result and the existing ones is that our result just needs to verify the finite points(extreme points) and the existing ones need to verify all points in the bounded polyhedron.     

Local minima of lattices and vertices of Klein polyhedra

We prove that each vertex of a Klein polyhedron of a lattice is a local minimum.     

Some insight into characterizations of minimally nonideal matrices

Lehman (Polyhedral combinatorics 1 of DIMACS series in discrete math. and theoretical computer science, pp 101–105, 1990) described some conditions regular minimally nonideal (mni) matrices must satisfy. Although, there are few results on sufficient conditions for mni matrices. In most of these results, the covering polyhedron must have a unique fractional extreme point. This condition corresponds to ask the matrix to be the blocker of a near-ideal matrix, defined by the authors in a previous work (2006). In this paper we prove that, having the blocker of a near-ideal matrix, only a few very easy conditions have to be checked in order to decide if the matrix is regular mni. In doing so, we define the class of quasi mni matrices, containing regular mni matrices, and we find a generalization on the number of integer extreme points adjacent to the fractional extreme point in the covering polyhedron. We also give a relationship between the covering and stability number of regular mni matrices which allows to prove when a regular mni matrix can be a proper minor of a quasi mni. Partially supported by CONICET Grant PIP 2807/2000 (Argentina) and by CNPq/PROSUL Grant 490333/2004-4 (Brasil).     

Master corner polyhedron: Vertices

We focus on the vertices of the master corner polyhedron (MCP), a fundamental object in the theory of integer linear programming. We introduce two combinatorial operations that transform vertices to their neighbors. This implies that each MCP can be defined by the initial vertices regarding these operations; we call them support vertices. We prove that the class of support vertices of all MCPs over a group is invariant under automorphisms of this group and describe MCP vertex bases. Among other results, we characterize its irreducible points, establish relations between a vertex and the nontrivial facets that pass through it, and prove that this polyhedron is of diameter 2.     

On the Number of Irreducible Points in Polyhedra

An integer point in a polyhedron is called irreducible iff it is not the midpoint of two other integer points in the polyhedron. We prove that the number of irreducible integer points in n-dimensional polytope P is at most \(O(m^{\lfloor \frac{n}{2}\rfloor }\log ^{n-1}\gamma )\), where n is fixed and P is given by a system of m linear inequalities with integer coefficients not exceeding (by absolute value) \(\gamma \). This bound is tight. Using this result we prove the conjecture asserting that the teaching dimension in the class of threshold functions of k-valued logic in n variables is \(\varTheta (\log ^{n-2} k)\) for any fixed \(n\ge 2\).     

Symmetry-breaking constraints for packing identical rectangles within polyhedra

Two problems related to packing identical rectangles within a polyhedron are tackled in the present work. Rectangles are allowed to differ only by horizontal or vertical translations and possibly 90° rotations. The first considered problem consists in packing as many identical rectangles as possible within a given polyhedron, while the second problem consists in finding the smallest polyhedron of a given type that accommodates a fixed number of identical rectangles. Both problems are modeled as mixed integer programming problems. Symmetry-breaking constraints that facilitate the solution of the MIP models are introduced. Numerical results are presented.     

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.     

基于生存理论的线性微分博弈系统识别域的判别

利用生存性理论, 研究线性微分博弈系统的一个有界识别域问题. 采用生存性理论来研究线性微分博弈系统的有界多面体\,(有限点集的凸包)\,的识别域问题, 给定的方法只需要检验该多面体在极点处是否满足生存性条件. 进而, 利用生存性与识别域的关系, 即可判断此多面体是否是系统的识别域, 简便易行.     

On the characterization of noninteger vertices of the relaxation polyhedron in the multi-index axial assignment problem

Theorems about the characterization and exponential growth of the denominators of fractional components of noninteger vertices of the relaxation polyhedron in the multi-index axial assignment problem are proved. They made it possible to obtain new lower bounds on the number of noninteger vertices of this polyhedron and to refute the conjecture on the estimate of the ratio of the number of integer vertices to the number of all vertices of the multi-index axial transportation polyhedron determined by integer vectors.     

On the facets of the mixed–integer knapsack polyhedron

We study the mixed–integer knapsack polyhedron, that is, the convex hull of the mixed–integer set defined by an arbitrary linear inequality and the bounds on the variables. We describe facet–defining inequalities of this polyhedron that can be obtained through sequential lifting of inequalities containing a single integer variable. These inequalities strengthen and/or generalize known inequalities for several special cases. We report computational results on using the inequalities as cutting planes for mixed–integer programming.Supported, in part, by NSF grants DMII–0070127 and DMII–0218265.Mathematics Subject Classification (2000): 90C10, 90C11, 90C57     

Maximizing a submodular function by integer programming: Polyhedral results for the quadratic case

We give a new mixed integer programming (MIP) formulation for the quadratic cost partition problem that is derived from a MIP formulation for maximizing a submodular function. Several classes of valid inequalities for the convex hull of the feasible solutions are derived using the valid inequalities for the node packing polyhedron. Facet defining conditions and separation algorithms are discussed and computational results are reported.     

Total dual integrality and b-matchings

Schrijver has shown that any rational polyhedron is the solution set of a unique minimal integer TDI linear system. We characterize this system for the case of b-matchings, one of the few known cases for which such a system is strictly larger than a minimal linear system sufficient to define the polyhedron.     

Polyhedra related to a lattice

Without using the l.p. duality theorem, we give a new and direct proof that Hoffman's lattice polyhedra, polyhedra from problems of Edmonds and Giles, and others, are integer. These polyhedra are intersections of more simple polyhedra such that every vertex of the initial polyhedron is a vertex of some simple polyhedron. In many cases encountered in combinatorics the simple polyhedra have a totally unimodular constraint matrix. This implies that all vertices of the initial polyhedron are integral. The proof is based on a theorem on submodular functions, which was not known earlier. The method of this paper can be applied to the consideration of the matching polyhedron.     

A combinatorial formula for affine Hall–Littlewood functions via a weighted Brion theorem

We present a new combinatorial formula for Hall–Littlewood functions associated with the affine root system of type \({{\tilde{A}}}_{n-1}\), i.e., corresponding to the affine Lie algebra \({{\widehat{\mathfrak {sl}}}}_n\). Our formula has the form of a sum over the elements of a basis constructed by Feigin, Jimbo, Loktev, Miwa and Mukhin in the corresponding irreducible representation. Our formula can be viewed as a weighted sum of exponentials of integer points in a certain infinite-dimensional convex polyhedron. We derive a weighted version of Brion’s theorem and then apply it to our polyhedron to prove the formula.