Projection with a Minimal System of Inequalities

Projection of a polyhedron involves the use of a cone whose extreme rays induce the inequalities defining the projection. These inequalities need not be facet defining. We introduce a transformation that produces a cone whose extreme rays induce facets of the projection.     

Generalized intersection cuts and a new cut generating paradigm

Intersection cuts are generated from a polyhedral cone and a convex set S whose interior contains no feasible integer point. We generalize these cuts by replacing the cone with a more general polyhedron C. The resulting generalized intersection cuts dominate the original ones. This leads to a new cutting plane paradigm under which one generates and stores the intersection points of the extreme rays of C with the boundary of S rather than the cuts themselves. These intersection points can then be used to generate in a non-recursive fashion cuts that would require several recursive applications of some standard cut generating routine. A procedure is also given for strengthening the coefficients of the integer-constrained variables of a generalized intersection cut. The new cutting plane paradigm yields a new characterization of the closure of intersection cuts and their strengthened variants. This characterization is minimal in the sense that every one of the inequalities it uses defines a facet of the closure.     

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.     

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

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

On the monotonization of polyhedra

In polyhedral combinatorics one often has to analyze the facial structure of less than full dimensional polyhedra. The presence of implicit or explicit equations in the linear system defining such a polyhedron leads to technical difficulties when analyzing its facial structure. It is therefore customary to approach the study of such a polytopeP through the study of one of its (full dimensional) relaxations (monotonizations) known as the submissive and the dominant ofP. Finding sufficient conditions for an inequality that induces a facet of the submissive or the dominant of a polyhedron to also induce a facet of the polyhedron itself has been posed in the literature as an important research problem. Our paper goes a long way towards solving this problem. We address the problem in the framework of a generalized monotonization of a polyhedronP, g-mon(P), that subsumes both the submissive and the dominant, and give a sufficient condition for an inequality that defines a facet of g-mon(P) to define a facet ofP. For the important cases of the traveling salesman (TS) polytope in both its symmetric and asymmetric variants, and of the linear ordering polytope, we give sufficient conditions trivially easy to verify, for a facet of the monotone completion to define a facet of the original polytope itself. Research supported by grant DMI-9201340 of the National Science Foundation and contract N00014-89-J-1063 of the Office of Naval Research. Research supported by MURST, Italy.     

A new approach for solving linear bilevel problems using genetic algorithms

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. This paper develops a genetic algorithm for the linear bilevel problem in which both objective functions are linear and the common constraint region is a polyhedron. Taking into account the existence of an extreme point of the polyhedron which solves the problem, the algorithm aims to combine classical extreme point enumeration techniques with genetic search methods by associating chromosomes with extreme points of the polyhedron. The numerical results show the efficiency of the proposed algorithm. In addition, this genetic algorithm can also be used for solving quasiconcave bilevel problems provided that the second level objective function is linear.     

Equivalence between intersection cuts and the corner polyhedron

Intersection cuts were introduced by Balas and the corner polyhedron by Gomory. Balas showed that intersection cuts are valid for the corner polyhedron. In this paper we show that, conversely, every nontrivial facet-defining inequality for the corner polyhedron is an intersection cut.     

The Representation Polyhedron of a Semiorder

Let a finite semiorder, or unit interval order, be given. When suitably defined, its numerical representations are the solutions of a system of linear inequalities. They thus form a convex polyhedron. We show that the facets of the representation polyhedron correspond to the noses and hollows of the semiorder. Our main result is to prove that the system defining the polyhedron is totally dual integral. As a consequence, the coordinates of the vertices and the components of the extreme rays of the polyhedron are all integral multiples of a common value. Total dual integrality is in turn derived from a particular property of the oriented cycles in the directed graph of noses and hollows of a strictly upper diagonal step tableau. Our approach delivers also a new proof for the existence of the minimal representation of a semiorder, a concept originally discovered by Pirlot (Theory Decis 28:109–141, 1990). Finding combinatorial interpretations of the vertices and extreme rays of the representation polyhedron is left for future work.     

Facet inequalities from simple disjunctions in cutting plane theory

The duality between facets of the convex hull of disjunctive sets and the extreme points of reverse polars of these sets is utilized to establish simple rules for the derivation of all facet cuts for simple disjunctions, namely, elementary disjunctions in nonnegative variables. These rules generalize the cut generation procedure underlying polyhedral convexity cuts with negative edge extensions. The latter are also shown to possess some interesting properties with respect to a biextremal problem that maximizes the distance, from the origin, of the nearest point feasible to the cut. A computationally inexpensive procedure is given to generate facet cuts for simple disjunctions which are dominant with respect to any specified preemptive ordering of variables.     

Extreme point linear fractional functional programming

This paper deals with the optimization of the ratio of two linear functions subject to a set of linear constraints with the additional restriction that the optimal solution is to be an extreme point of another convex polyhedron. In this paper, an enumerative procedure for solving such type of problems is developed. For an illustration, a numerical example is also provided.     

The split closure of a strictly convex body

The Chvátal-Gomory closure and the split closure of a rational polyhedron are rational polyhedra. It has been recently shown that the Chvátal-Gomory closure of a strictly convex body is also a rational polytope. In this note, we show that the split closure of a strictly convex body is defined by a finite number of split disjunctions, but is not necessarily polyhedral. We also give a closed form expression in the original variable space of a split cut for full-dimensional ellipsoids.     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

Generating facets for the cut polytope of a graph by triangular elimination

The cut polytope of a graph arises in many fields. Although much is known about facets of the cut polytope of the complete graph, very little is known for general graphs. The study of Bell inequalities in quantum information science requires knowledge of the facets of the cut polytope of the complete bipartite graph or, more generally, the complete k-partite graph. Lifting is a central tool to prove certain inequalities are facet inducing for the cut polytope. In this paper we introduce a lifting operation, named triangular elimination, applicable to the cut polytope of a wide range of graphs. Triangular elimination is a specific combination of zero-lifting and Fourier–Motzkin elimination using the triangle inequality. We prove sufficient conditions for the triangular elimination of facet inducing inequalities to be facet inducing. The proof is based on a variation of the lifting lemma adapted to general graphs. The result can be used to derive facet inducing inequalities of the cut polytope of various graphs from those of the complete graph. We also investigate the symmetry of facet inducing inequalities of the cut polytope of the complete bipartite graph derived by triangular elimination.      

On structures of bisubmodular polyhedra

A bisubmodular polyhedron is defined in terms of a so-called bisubmodular function on a family of ordered pairs of disjoint subsets of a finite set. We examine the structures of bisubmodular polyhedra in terms of signed poset and exchangeability graph. We give a characterization of extreme points together with an O(n ²) algorithm for discerning whether a given point is an extreme point, wheren is the cardinality of the underlying set, and we assume a function evaluation oracle for the bisubmodular function. The algorithm also determines the signed posetructure associated with the given point if it is an extreme point. We reveal the adjacency relation of extreme points by means of the Hasse diagrams of the associated signed posets. Moreover, we investigate the connectivity and the decomposition of a bisubmodular system into its connected components.     

A finite concave minimization algorithm using branch and bound and neighbor generation

In this article we present a new finite algorithm for globally minimizing a concave function over a compact polyhedron. The algorithm combines a branch and bound search with a new process called neighbor generation. It is guaranteed to find an exact, extreme point optimal solution, does not require the objective function to be separable or even analytically defined, requires no nonlinear computations, and requires no determinations of convex envelopes or underestimating functions. Linear programs are solved in the branch and bound search which do not grow in size and differ from one another in only one column of data. Some preliminary computational experience is also presented.     

A stabilized structured Dantzig–Wolfe decomposition method

We discuss an algorithmic scheme, which we call the stabilized structured Dantzig–Wolfe decomposition method, for solving large-scale structured linear programs. It can be applied when the subproblem of the standard Dantzig–Wolfe approach admits an alternative master model amenable to column generation, other than the standard one in which there is a variable for each of the extreme points and extreme rays of the corresponding polyhedron. Stabilization is achieved by the same techniques developed for the standard Dantzig–Wolfe approach and it is equally useful to improve the performance, as shown by computational results obtained on an application to the multicommodity capacitated network design problem.     

Maillage simplicial d'un polyèdre arbitraire

Issues related to the existence of a triangulation of an arbitrary polyhedron are addressed. Given a boundary surface mesh (a set of triangular facets), the problem to decide whether or not a triangulation (with no internal points apart from the Steiner points) exists is reported to be NP-hard. In this paper, an algorithm to triangulate a general polyhedron is used which makes use of a classical Delaunay triangulation algorithm, a phase for recovering the missing boundary facets by means of facet partitioning and a final phase that makes it possible to remove the additional (non-Steiner) points previously defined so as to recover the initial boundary mesh thus resulting in a mesh of the given polyhedron. To cite this article: P.-L. George, H. Borouchaki, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

Packing Steiner trees: polyhedral investigations

LetG=(V, E) be a graph andT⊆V be a node set. We call an edge setS a Steiner tree forT ifS connects all pairs of nodes inT. In this paper we address the following problem, which we call the weighted Steiner tree packing problem. Given a graphG=(V, E) with edge weightsw _e , edge capacitiesc _e ,e∈E, and node setT ₁,…,T _N , find edge setsS ₁,…,S _N such that eachS _k is a Steiner tree forT _k , at mostc _e of these edge sets use edgee for eache∈E, and the sum of the weights of the edge sets is minimal. Our motivation for studying this problem arises from a routing problem in VLSI-design, where given sets of points have to be connected by wires. We consider the Steiner tree packing problem from a polyhedral point of view and define an associated polyhedron, called the Steiner tree packing polyhedron. The goal of this paper is to (partially) describe this polyhedron by means of inequalities. It turns out that, under mild assumptions, each inequality that defines a facet for the (single) Steiner tree polyhedron can be lifted to a facet-defining inequality for the Steiner tree packing polyhedron. The main emphasis of this paper lies on the presentation of so-called joint inequalities that are valid and facet-defining for this polyhedron. Inequalities of this kind involve at least two Steiner trees. The classes of inequalities we have found form the basis of a branch & cut algorithm. This algorithm is described in our companion paper (in this issue).