Tropical polar cones, hypergraph transversals, and mean payoff games

We discuss the tropical analogues of several basic questions of convex duality. In particular, the polar of a tropical polyhedral cone represents the set of linear inequalities that its elements satisfy. We characterize the extreme rays of the polar in terms of certain minimal set covers which may be thought of as weighted generalizations of minimal transversals in hypergraphs. We also give a tropical analogue of Farkas lemma, which allows one to check whether a linear inequality is implied by a finite family of linear inequalities. Here, the certificate is a strategy of a mean payoff game. We discuss examples, showing that the number of extreme rays of the polar of the tropical cyclic polyhedral cone is polynomially bounded, and that there is no unique minimal system of inequalities defining a given tropical polyhedral cone.     

Facets of the balanced (acyclic) induced subgraph polytope

A signed graph is a graph whose edges are labelled positive or negative. A signed graph is said to be balanced if the set of negative edges form a cut. The balanced induced subgraph polytopeP(G) of a graphG is the convex hull of the incidence vectors of all node sets that induce balanced subgraphs ofG. In this paper we exhibit various (rank) facet defining inequalities. We describe several methods with which new facet defining inequalities ofP(G) can be constructed from known ones. Finding a maximum weighted balanced induced subgraph of a series parallel graph is a polynomial problem. We show that for this class of graphsP(G) may have complicated facet defining inequalities. We derive analogous results for the polytope of acyclic induced subgraphs.Research supported in part by the Natural Sciences and Engineering Research Council of Canada; the second author has also been supported by C.P. Rail.     

Projection onto polyhedra in outer representation

The projection of the origin onto an n-dimensional polyhedron defined by a system of m inequalities is reduced to a sequence of projection problems onto a one-parameter family of shifts of a polyhedron with at most m + 1 vertices in n + 1 dimensions. The problem under study is transformed into the projection onto a convex polyhedral cone with m extreme rays, which considerably simplifies the solution to an equivalent problem and reduces it to a single projection operation. Numerical results obtained for random polyhedra of high dimensions are presented.     

An algorithm for determining redundant inequalities and all solutions to convex polyhedra

Given a system of linear inequalities that define a polyhedral cone, we develop a simple technique for finding redundant inequalities. We thus insure that only the cone's extreme rays are calculated. The general solution for the system is developed in terms of the extreme rays. The method leads directly to the general solution for either bounded or unbounded polyhedra.     

Generating Convex Polynomial Inequalities for Mixed 0–1 Programs

We develop a method for generating valid convex quadratic inequalities for mixed0–1 convex programs. We also show how these inequalities can be generated in the linear case by defining cut generation problems using a projection cone. The basic results for quadratic inequalities are extended to generate convex polynomial inequalities.     

Primal and polar approach for computing the symmetric diagonally dominant projection

We solve the problem of minimizing the distance from a given matrix to the cone of symmetric and diagonally dominant matrices with positive diagonal (SDD⁺). Using the extreme rays of the polar cone we project onto the supporting hyperplanes of the faces of SDD⁺ and then, applying the cyclic Dykstra's algorithm, we solve the problem. Similarly, using the extreme rays of SDD⁺ we characterize the projection onto the polar cone, which also allows us to obtain the projection onto SDD⁺ by means of the orthogonal decomposition theorem for convex cones. In both cases the symmetry and the sparsity pattern of the given matrix are preserved. Preliminary numerical experiments indicate that the polar approach is a promising one. Copyright © 2002 John Wiley & Sons, Ltd.     

Geometry of the copositive and completely positive cones

The copositive cone, and its dual the completely positive cone, have useful applications in optimisation, however telling if a general matrix is in the copositive cone is a co-NP-complete problem. In this paper we analyse some of the geometry of these cones. We discuss a way of representing all the maximal faces of the copositive cone along with a simple equation for the dimension of each one. In doing this we show that the copositive cone has faces which are isomorphic to positive semidefinite cones. We also look at some maximal faces of the completely positive cone and find their dimensions. Additionally we consider extreme rays of the copositive and completely positive cones and show that every extreme ray of the completely positive cone is also an exposed ray, but the copositive cone has extreme rays which are not exposed rays.     

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.     

Extreme positive operators on minimal and almost minimal cones

Fiedler and Pták called a cone minimal if it is n-dimensional and has n+1 extremal rays. We call a cone almost minimal if it is n-dimensional and has n+2 extremal rays. Duality properties stemming from the use of Gale pairs lead to a general technique for identifying the extreme cone-preserving (positive) operators between polyhedral cones. This technique is most effective for cones with dimension not much smaller than the number of their extreme rays. In particular, the Fiedler-Pták characterization of extreme positive operators between minimal cones is extended to the following cases: (i) operators from a minimal cone to an arbitrary polyhedral cone, (ii) operators from an almost minimal cone to a minimal cone.     

Benders,metric and cutset inequalities for multicommodity capacitated network design

Solving multicommodity capacitated network design problems is a hard task that requires the use of several strategies like relaxing some constraints and strengthening the model with valid inequalities. In this paper, we compare three sets of inequalities that have been widely used in this context: Benders, metric and cutset inequalities. We show that Benders inequalities associated to extreme rays are metric inequalities. We also show how to strengthen Benders inequalities associated to non-extreme rays to obtain metric inequalities. We show that cutset inequalities are Benders inequalities, but not necessarily metric inequalities. We give a necessary and sufficient condition for a cutset inequality to be a metric inequality. Computational experiments show the effectiveness of strengthening Benders and cutset inequalities to obtain metric inequalities.     

Solving a class of matrix minimization problems by linear variational inequality approaches

A class of matrix optimization problems can be formulated as a linear variational inequalities with special structures. For solving such problems, the projection and contraction method (PC method) is extended to variational inequalities with matrix variables. Then the main costly computational load in PC method is to make a projection onto the semi-definite cone. Exploiting the special structures of the relevant variational inequalities, the Levenberg-Marquardt type projection and contraction method is advantageous. Preliminary numerical tests up to 1000×1000 matrices indicate that the suggested approach is promising.     

Isotonicity of the Metric Projection by Lorentz Cone and Variational Inequalities

In this paper, we first discuss the geometric properties of the Lorentz cone and the extended Lorentz cone. The self-duality and orthogonality of the Lorentz cone are obtained in Hilbert spaces. These properties are fundamental for the isotonicity of the metric projection with respect to the order, induced by the Lorentz cone. According to the Lorentz cone, the quasi-sublattice and the extended Lorentz cone are defined. We also obtain the representation of the metric projection onto cones in Hilbert quasi-lattices. As an application, solutions of the classic variational inequality problem and the complementarity problem are found by the Picard iteration corresponding to the composition of the isotone metric projection onto the defining closed and convex set and the difference in the identity mapping and the defining mapping. Our results generalize and improve various recent results obtained by many others.     

Isotone functions,dual cones,and networks

If the collection of all real-valued functions defined on a finite partially ordered set S of n elements is identified in the natural way with Rⁿ, it is obvious that the subset of functions that are isotone or order preserving with respect to the given partial order constitutes a closed, convex, polyhedral cone K in Rⁿ. The dual cone K^* of K is the set of all linear functionals that are nonpositive of K. This article identifies the important geometric properties of K, and characterizes a nonredundant set of defining equations and inequalities for K^* in terms of a special class of partitions of S into upper and lower sets. These defining constraints immediately imply a set of extreme rays spanning K and K^*. One of the characterizations of K^* involves feasibility conditions on flows in a network. These conditions are also used as a tool in analysis.     

On the geometry of complete intersection toric varieties

In this paper we give a geometric characterization of the cones of toric varieties that are complete intersections. In particular, we prove that the class of complete intersection cones is the smallest class of cones which is closed under direct sum and contains all simplex cones. Further, we show that the number of the extreme rays of such a cone, which is less than or equal to 2n − 2, is exactly 2n − 2 if and only if the cone is a bipyramidal cone, where n > 1 is the dimension of the cone. Finally, we characterize all toric varieties whose associated cones are complete intersection cones. Received: 4 July 2005     

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.     

A new framework for the solution of DEA models

We provide an alternative framework for solving data envelopment analysis (DEA) models which, in comparison with the standard linear programming (LP) based approach that solves one LP for each decision making unit (DMU), delivers much more information. By projecting out all the variables which are common to all LP runs, we obtain a formula into which we can substitute the inputs and outputs of each DMU in turn in order to obtain its efficiency number and all possible primal and dual optimal solutions. The method of projection, which we use, is Fourier–Motzkin (F–M) elimination. This provides us with the finite number of extreme rays of the elimination cone. These rays give the dual multipliers which can be interpreted as weights which will apply to the inputs and outputs for particular DMUs. As the approach provides all the extreme rays of the cone, multiple sets of weights, when they exist, are explicitly provided. Several applications are presented. It is shown that the output from the F–M method improves on existing methods of (i) establishing the returns to scale status of each DMU, (ii) calculating cross-efficiencies and (iii) dealing with weight flexibility. The method also demonstrates that the same weightings will apply to all DMUs having the same comparators. In addition it is possible to construct the skeleton of the efficient frontier of efficient DMUs. Finally, our experiments clearly indicate that the extra computational burden is not excessive for most practical problems.     

Polyhedral analysis for the two-item uncapacitated lot-sizing problem with one-way substitution

We consider a production planning problem for two items where the high quality item can substitute the demand for the low quality item. Given the number of periods, the demands, the production, inventory holding, setup and substitution costs, the problem is to find a minimum cost production and substitution plan. This problem generalizes the well-known uncapacitated lot-sizing problem. We study the projection of the feasible set onto the space of production and setup variables and derive a family of facet defining inequalities for the associated convex hull. We prove that these inequalities together with the trivial facet defining inequalities describe the convex hull of the projection if the number of periods is two. We present the results of a computational study and discuss the quality of the bounds given by the linear programming relaxation of the model strengthened with these facet defining inequalities for larger number of periods.     

On the cut polytope

The cut polytopeP _C (G) of a graphG=(V, E) is the convex hull of the incidence vectors of all edge sets of cuts ofG. We show some classes of facet-defining inequalities ofP _C (G). We describe three methods with which new facet-defining inequalities ofP _C (G) can be constructed from known ones. In particular, we show that inequalities associated with chordless cycles define facets of this polytope; moreover, for these inequalities a polynomial algorithm to solve the separation problem is presented. We characterize the facet defining inequalities ofP _C (G) ifG is not contractible toK ₅. We give a simple characterization of adjacency inP _C (G) and prove that for complete graphs this polytope has diameter one and thatP _C (G) has the Hirsch property. A relationship betweenP _C (G) and the convex hull of incidence vectors of balancing edge sets of a signed graph is studied.     

关于两个非线性算子的一个分裂方法(英文)

<正>This paper generalizes a class of projection type methods for monotone variational inequalities to general monotone inclusion.It is shown that when the normal cone operator in projection is replaced by any maximal monotone operator,the resulting method inherits all attractive convergence properties of projection type methods,and allows an adjusting step size rule.Weaker convergence assumption entails an extra projection at each iteration.Moreover,this paper also addresses applications of the resulting method to convex programs and monotone variational inequalities.     

On the solitaire cone and its relationship to multi-commodity flows

The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to the 1960s, when the solitaire cone was first described by Boardman and Conway. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper we study the extremal structure of solitaire cones for a variety of boards, and relate their structure to the well studied metric cone. In particular we give:?1. an equivalence between the multicommodity flow problem with associated dual metric cone and a generalized peg game with associated solitaire cone;?2. a related NP-completeness result;?3. a method of generating large classes of facets;?4. a complete characterization of 0-1 facets;?5. exponential upper and lower bounds (in the dimension) on the number of facets;?6. results on the number of facets, incidence and adjacency relationships and diameter for small rectangular, toric and triangular boards;?7. a complete characterization of the adjacency of extreme rays, diameter, number of 2-faces and edge connectivity for rectangular toric boards. Received: July 1996 / Accepted: February 2000?Published online February 22, 2001