A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming

 We establish a precise correspondence between lift-and-project cuts for mixed 0-1 programs, simple disjunctive cuts (intersection cuts) and mixed-integer Gomory cuts. The correspondence maps members of one family onto members of the others. It also maps bases of the higher-dimensional cut generating linear program (CGLP) into bases of the linear programming relaxation. It provides new bounds on the number of facets of the elementary closure, and on the rank, of the standard linear programming relaxation of the mixed 0-1 polyhedron with respect to the above families of cutting planes. Based on the above correspondence, we develop an algorithm that solves (CGLP) without explicitly constructing it, by mimicking the pivoting steps of the higher dimensional (CGLP) simplex tableau by certain pivoting steps in the lower dimensional (LP) simplex tableau. In particular, we show how to calculate the reduced costs of the big tableau from the entries of the small tableau and based on this, how to identify a pivot in the small tableau that corresponds to one or several improving pivots in the big tableau. The overall effect is a much improved lift-and-project cut generating procedure, which can also be interpreted as an algorithm for a systematic improvement of mixed integer Gomory cuts from the small tableau. Received: October 5, 2000 / Accepted: March 19, 2002 Published online: September 5, 2002 Research was supported by the National Science Foundation through grant #DMI-9802773 and by the Office of Naval Research through contract N00014-97-1-0196.     

Tableau method for residuated logic

Residuated logic is a generalization of intuitionistic logic, which does not assume the idempotence of the conjunction operator. Such generalized conjunction operators have proved important in expert systems (in the area of Approximate Reasoning) and in some areas of Theoretical Computer Science. Here we generalize the intuitionistic tableau procedure and prove that this generalized tableau method is sound for the semantics (the class of residuated algebras) of residuated propositional calculus (RPC). Since the axioms of RPC are complete for the semantics we may conclude that whenever a formula 0 is tableau provable, it is deducible in RPC. We present two different approaches for constructing residuated algebras which give us countermodels for some formulas φ which are not tableau provable. The first uses the fact that the theory of residuated algebras is equational, to construct quotients of free algebras. The second uses finite algebras. We end by discussing a number of open questions.     

The Distributions of the Entries of Young Tableaux

Let T be a standard Young tableau of shape λ⊢k. We show that the probability that a randomly chosen Young tableau of n cells contains T as a subtableau is, in the limit n→∞, equal to f^λ/k!, where f^λ is the number of all tableaux of shape λ. In other words, the probability that a large tableau contains T is equal to the number of tableaux whose shape is that of T, divided by k!. We give several applications, to the probabilities that a set of prescribed entries will appear in a set of prescribed cells of a tableau, and to the probabilities that subtableaux of given shapes will occur. Our argument rests on a notion of quasirandomness of families of permutations, and we give sufficient conditions for this to hold.     

The Flagged Double Schur Function

The double Schur function is a natural generalization of the factorial Schur function introduced by Biedenharn and Louck. It also arises as the symmetric double Schubert polynomial corresponding to a class of permutations called Grassmannian permutations introduced by A. Lascoux. We present a lattice path interpretation of the double Schur function based on a flagged determinantal definition, which readily leads to a tableau interpretation similar to the original tableau definition of the factorial Schur function. The main result of this paper is a combinatorial treatment of the flagged double Schur function in terms of the lattice path interpretations of divided difference operators. Finally, we find lattice path representations of formulas for the symplectic and orthogonal characters for sp(2n) and so(2n + 1) based on the tableau representations due to King and El-Shakaway, and Sundaram. Based on the lattice path interpretations, we obtain flagged determinantal formulas for these characters.     

Bijective proofs of formulae for the number of standard Yound tableaux

We give a bijective proof of a formula due independently to Frobenius and Young for the number of standard Young tableau of shape λ for λ any partition. Frame, Robinson, and Thrall derived their hook formula for the number of standard Young tableau from the Frobenius-Young formula. As a corollary to our bijective proof of the Frobenius-Young formula, we also give a bijective proof of the Frame-Robinson-Thrall hook formula.     

Strukturen geometrischer Ornamente

We consider double-periodic tilings of the whole plane from the view of graph theory, not with respect to symmetry groups. We suppose that the graph is planar and connected and that the fundamental domain contains a finite number of vertices and edges. We assign to every tiling a tableau. There exists a fundamental formula connecting the number of all numbers of the tableau with the sum of the reciprocals of all these numbers and with the number p of lines in the tableau; the formula is proved even if multiple edges or loops occur. By this way we get a graph-theoretic classification of the tilings. We introduce families F of tilings and their ranks. The family F={k₁,k₂...,k_s} (with k₁>k₂>...>k_s>O) is the set of all tilings, the tableau of which contains all the numbers k_j and no others. The smallest number p of lines (which occur for the tilings of the family F) is the rank of F and has special geometric interest. Some open questions are mentioned at the end.

---

---

Herrn Helmut Karzel zum 60. Geburtstag gewidmet     

如何利用单纯形表上的信息

本文分析了求解线性规划的基本方法－－单纯形法所使用的单纯形表，将表中所提供的信息分为直接信息和间接信息两类，论述了如何充分利用这些信息的方法。例如如何由最终表求原问题、如何利用表中的数据互相推演和校正等。这是一篇教学经验的总结，对初学者可能有一定的帮助。     

On characterizations of classical polynomials

It is well known that the classical families of Jacobi, Laguerre, Hermite, and Bessel polynomials are characterized as eigenvectors of a second order linear differential operator with polynomial coefficients, Rodrigues formula, etc. In this paper we present a unified study of the classical discrete polynomials and q-polynomials of the q-Hahn tableau by using the difference calculus on linear-type lattices. We obtain in a straightforward way several characterization theorems for the classical discrete and q-polynomials of the “q-Hahn tableau”. Finally, a detailed discussion of a characterization by Marcellán et al. is presented.     

On the Mosaic Method for Many-Dimensional Modal Logics: A Case Study Combining Tense and Modal Operators

We present an extension of the mosaic method aimed at capturing many-dimensional modal logics. As a proof-of-concept, we define the method for logics arising from the combination of linear tense operators with an “orthogonal” S5-like modality. We show that the existence of a model for a given set of formulas is equivalent to the existence of a suitable set of partial models, called mosaics, and apply the technique not only in obtaining a proof of decidability and a proof of completeness for the corresponding Hilbert-style axiomatization, but also in the development of a mosaic-based tableau system. We further consider extensions for dealing with the case when interactions between the two dimensions exist, thus covering a wide class of bundled Ockhamist branching-time logics, and present for them some partial results, such as a non-analytic version of the tableau system.     

互补基解性质的应用研究

对线性规划互补基解性质进行了研究,得到了由线性规划问题最优基对应的单纯形表直接获得对偶线性规划问题最优基对应的单纯形表的一个有效方法,给出了应用实例.     

Practical strategies for generating rank-1 split cuts in mixed-integer linear programming

In this paper we propose practical strategies for generating split cuts, by considering integer linear combinations of the rows of the optimal simplex tableau, and deriving the corresponding Gomory mixed-integer cuts; potentially, we can generate a huge number of cuts. A key idea is to select subsets of variables, and cut deeply in the space of these variables. We show that variables with small reduced cost are good candidates for this purpose, yielding cuts that close a larger integrality gap. An extensive computational evaluation of these cuts points to the following two conclusions. The first is that our rank-1 cuts improve significantly on existing split cut generators (Gomory cuts from single tableau rows, MIR, Reduce-and-Split, Lift-and-Project, Flow and Knapsack cover): on MIPLIB instances, these generators close 24% of the integrality gap on average; adding our cuts yields an additional 5%. The second conclusion is that, when incorporated in a Branch-and-Cut framework, these new cuts can improve computing time on difficult instances.     

An insertion algorithm for catabolizability

Our recent work in Blasiak (2011) [1] exhibits a canonical basis of the Garsia-Procesi module R_λ with cells labeled by standard tableaux of catabolizability ?λ. Through our study of the Kazhdan-Lusztig preorder on this basis, we found a way to transform a standard word labeling a basis element into a word inserting to the unique tableau of shape λ. This led to an algorithm that computes the catabolizability of the insertion tableau of a standard word. We deduce from this a characterization of catabolizability as the statistic on words invariant under Knuth transformations, certain (co)rotations, and a new set of transformations we call catabolism transformations. We further deduce a Greene’s Theorem-like characterization of catabolizability and a result about how cocyclage changes catabolizability, strengthening a similar result in Shimozono and Weyman (2000) [8].     

Solving Bilevel Linear Programs Using Multiple Objective Linear Programming

We present an algorithm for solving bilevel linear programs that uses simplex pivots on an expanded tableau. The algorithm uses the relationship between multiple objective linear programs and bilevel linear programs along with results for minimizing a linear objective over the efficient set for a multiple objective problem. Results in multiple objective programming needed are presented. We report computational experience demonstrating that this approach is more effective than a standard branch-and-bound algorithm when the number of leader variables is small.     

A step toward probabilistic analysis of simplex method convergence

Probability distributions are assumed for the coefficients in simplex tableaus. A probability of success in one simplex iteration is then derived; for example, the probability of a tableau which satisfies the criteria for optimality except in one row becoming fully optimal in one iteration. Such results are expressed in terms of tableau size parameters.     

The skew Schubert polynomials

We obtain a tableau definition of the skew Schubert polynomials named by Lascoux, which are defined as flagged double skew Schur functions. These polynomials are in fact Schubert polynomials in two sets of variables indexed by 321-avoiding permutations. From the divided difference definition of the skew Schubert polynomials, we construct a lattice path interpretation based on the Chen–Li–Louck pairing lemma. The lattice path explanation immediately leads to the determinantal definition and the tableau definition of the skew Schubert polynomials. For the case of a single variable set, the skew Schubert polynomials reduce to flagged skew Schur functions as studied by Wachs and by Billey, Jockusch, and Stanley. We also present a lattice path interpretation for the isobaric divided difference operators, and derive an expression of the flagged Schur function in terms of isobaric operators acting on a monomial. Moreover, we find lattice path interpretations for the Giambelli identity and the Lascoux–Pragacz identity for super-Schur functions. For the super-Lascoux–Pragacz identity, the lattice path construction is related to the code of the partition which determines the directions of the lines parallel to the y-axis in the lattice.     

Aggregation of preferences: a review

This paper presents a review and a classification of the main theoretical results obtained up to now in the important field of the aggregation of preferences. (Let us mention that multicriteria analysis is not considered here, as it essentially consists of methods for the aggregation of preferences).Section 1 describes a tableau, each square of which corresponds to a particular type of preference aggregation problem, and gives, for each of them, a list of references. The different types of problems are obtained by considering the various kinds of informations which can be obtained concerning the global preferences of a committee and the preferences of the individual members.Sections 2, 3 and 4 present some comments respectively on Arrow's problem (three first columns of the tableau), on the theory of choice functions (fourth column) and voting procedures (fifth column).In the bibliography, each reference is associated, in terms of its subject, to one particular square of the tableau.