Dual row modules and polyhedra of blocking group problems

Corresponding to every group problem is a row module. Duality for group problems is developed using the duality or orthogonality of the corresponding row modules. The row module corresponding to a group problem is shown to include Gomory's fractional cuts for the group polyhedron and all the vertices of the polyhedron of the blocking group problem. The polyhedra corresponding to a pair of blocking group problems are shown to have a blocking nature i.e. the vertices of one include some of the facets of the other and mutatis mutandis. The entire development is constructive. The notions of contraction, deletion, expansion and extension are defined constructively and related to homomorphic liftings and suproblems in a dual setting. Roughly speaking a homomorphic lifting is dual to forming a subproblem. A proof of the Gastou-Johnson generalization of Gomory's homomorphic lifting theorem is given, and dual constructions are discussed. A generalization of Gomory's subadditive characterization to subproblems is given. In the binary case, it is closely related to the work of Seymour on cones arising from binary matroids.     

Binary group and Chinese postman polyhedra

A new proof of the characterization of the Chinese postman polyhedra is given. In developing this proof, a theorem of Gomory about homomorphic lifting of facets for group polyhedra is generalized to subproblems. Some results for the Chinese postman problem are generalized to binary group problems. In addition, a connection is made between Fulkerson's blocking polyhedra and a blocking pair of binary group problems. A connection is also developed between minors and lifting of facets for group problems.     

Cyclic networks with general blocking and starvation

We introducegeneral starvation and consider cyclic networks withgeneral blocking and starvation (GBS). The mechanism of general blocking allows the server to process a limited number of jobs when the buffer downstream is full, and that of general starvation allows the server to perform a limited number of services in anticipation of jobs that are yet to arrive. The two main goals of this paper are to investigate how the throughput of cyclic GBS networks is affected by varying (1) the total number of jobsJ, and (2) the buffer allocationk=(k₁..., k_m) subject to a fixed total buffer capacityK=k ₁ +... + k_m. In particular, we obtain sufficient conditions for the throughput to be symmetric inJ and to be maximized whenJ=K/2. We also show that the equal buffer allocation is optimal under the two regimes of light or heavy usage. In order to establish these results, we obtain several intermediate structural properties of the throughput, using duality, reversibility, and concavity, which are of independent interest.Research supported in part by NSF Grant No. ECS-8919818.     

Cyclic job shop scheduling problems with blocking

A tabu search algorithm for a cyclic job shop problem with blocking is presented. Operations are blocking if they must stay on a machine after finishing when the next machine is occupied by another job. During this stay the machine is blocked for other jobs. For this problem traditional tabu search moves often lead to infeasible solutions. Recovering procedures are developed which construct nearby feasible solutions. Computational results are presented for the approach.     

Cyclic group and knapsack facets

 Any integer program may be relaxed to a group problem. We define the master cyclic group problem and several master knapsack problems, show the relationship between the problems, and give several classes of facet-defining inequalities for each problem, as well as a set of mappings that take facets from one type of master polyhedra to another. Received: May 24, 2001 / Accepted: August 2002 Published online: March 21, 2003 Mathematics Subject Classification (1991): 20E28, 20G40, 20C20     

Valid inequalities for MIPs and group polyhedra from approximate liftings

In this paper, we present an approximate lifting scheme to derive valid inequalities for general mixed integer programs and for the group problem. This scheme uses superadditive functions as the building block of integer and continuous lifting procedures. It yields a simple derivation of new and known families of cuts that correspond to extreme inequalities for group problems. This new approximate lifting approach is constructive and potentially efficient in computation. J.-P. P. Richard was supported by NSF grant DMI-348611.     

Generalized mixed integer rounding inequalities: facets for infinite group polyhedra

We present a generalization of the mixed integer rounding (MIR) approach for generating valid inequalities for (mixed) integer programming (MIP) problems. For any positive integer n, we develop n facets for a certain (n + 1)-dimensional single-constraint polyhedron in a sequential manner. We then show that for any n, the last of these facets (which we call the n-step MIR facet) can be used to generate a family of valid inequalities for the feasible set of a general (mixed) IP constraint, which we refer to as the n-step MIR inequalities. The Gomory Mixed Integer Cut and the 2-step MIR inequality of Dash and günlük  (Math Program 105(1):29–53, 2006) are the first two families corresponding to n = 1,2, respectively. The n-step MIR inequalities are easily produced using periodic functions which we refer to as the n-step MIR functions. None of these functions dominates the other on its whole period. Finally, we prove that the n-step MIR inequalities generate two-slope facets for the infinite group polyhedra, and hence are potentially strong.      

Cyclic group actions on polynomial rings

We consider a cyclic group of order pⁿ, acting on a module incharacteristic p, and show how to reduce the calculation ofthe symmetric algebra to that of the exterior algebra.     

Cyclic group actions on odd-dimensional spheres

We show that for any simple (2q−1)-knotk, q>1, and any positive integern, the knot # ₁ ⁿ k is the fixed-point set of aZ _n -action onS ^2q+1. Further, we show that for many values ofn there are examples of (2q−1)-knots,q≥2, which are the fixed-point sets of inequivalentZ _n -actions. This paper was written whilst the first author was in receipt of a Research Grant from the Science Research Council of Great Britain.     

Graphs of polyhedra; polyhedra as graphs

Relations between graph theory and polyhedra are presented in two contexts. In the first, the symbiotic dependence between 3-connected planar graphs and convex polyhedra is described in detail. In the second, a theory of nonconvex polyhedra is based on a graph-theoretic foundation. This approach eliminates the vagueness and inconsistency that pervade much of the literature dealing with polyhedra more general than the convex ones.     

Greedoid polyhedra

Greedoids can be viewed as relaxations of matroids. As a subclass, APS-greedoids cover many combinatorial problems. This paper deals with APS-greedoid polyhedra. These polyhedra are similar in properties to matroid polyhedra. That is, the vertices of an APS-greedoid polyhedron are precisely the incidence vectors of the members of an APS-greedoid.Graduate School of USTC     

A combinatorial theory of Grünbaum's new regular polyhedra,part I: Grünbaum's new regular polyhedra and their automorphism group

The new regular polyhedra, defined and investigated by Branko Grünbaum in [4], and theirn-dimensional generalizations are classified in terms of their symmetry group.     

Interior Klein polyhedra

The convex hull of all integer points of a noncompact polyhedron is closed and is a generalized polyhedron only under certain conditions. It is proved that if only the integer points in the interior of the polyhedron are taken, then most of the conditions can be dropped. Moreover, the object thus obtained has properties resembling those of a Klein polyhedron, and it is a Klein polyhedron in the case of an irrational simplicial cone.     

Duality of polyhedra

Everyone is familiar with the concept that the cube and octahedron, dodecahedron and icosahedron are dual pairs, with the tetrahedron being self-dual. On the face of it, the concept seems straightforward; however, in all but the most symmetrical cases it is far from clear. By using the computer and three-dimensional graphics programs, it is possible to clarify the concept and explore new ideas. Moreover, it is an ideal topic for teaching clear logical thinking.     

Vertex-faithful regular polyhedra

We study the abstract regular polyhedra with automorphism groups that act faithfully on their vertices, and show that each non-flat abstract regular polyhedron covers a “vertex-faithful” polyhedron with the same number of vertices. We then use this result and earlier work on flat polyhedra to study abstract regular polyhedra based on the size of their vertex set. In particular, we classify all regular polyhedra where the number of vertices is prime or twice a prime. We also construct the smallest regular polyhedra with a prime squared number of vertices.     

Solution of polyhedra

The paper is an exposition of the authors talk on the Seminar on Differential Geometry in IMPA in Rio de Janeiro. It presents a short survey of some recent results in the metric theory of polyhedra in 3-space. Namely we emphasize on some applicatons of the theorem which is a vast generalization of the Herons formule for the area of a triangle to volumes of polyhedra.*The author is partially supported by grants of RFBR No. 02-01-00101 and Russian Ministry of Education E02-1.0-43.