linear programming

Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization

  • Pierre-Antoine Absil
  • Luke Winternitz
  • André L. Tits
    • Categories Linear Programming Tags , , ,

    In earlier work (Tits et al., SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints … Read more

    Robust Rankings for College Football

  • Samuel Burer
    • Categories Applications - OR and Management Sciences, Linear Programming, Robust Optimization Tags , ,

    We investigate the sensitivity of the Colley Matrix (CM) rankings—one of six computer rankings used by the Bowl Championship Series—to (hypothetical) changes in the outcomes of (actual) games. Specifically, we measure the shift in the rankings of the top 25 teams when the win-loss outcome of, say, a single game between two teams, each with … Read more

    A Proof by the Simplex Method for the Diameter of a (0,1)-Polytope

  • Tomonari Kitahara
  • Shinji Mizuno
    • Categories Graphs and Matroids, Linear Programming Tags , , , ,

    Naddef shows that the Hirsch conjecture is true for (0,1)-polytopes by proving that the diameter of any $(0,1)$-polytope in $d$-dimensional Euclidean space is at most $d$. In this short paper, we give a simple proof for the diameter. The proof is based on the number of solutions generated by the simplex method for a linear … Read more

    Implementing the simplex method as a cutting-plane method

  • Krisztian Eretnek
  • Csaba I. Fábián
  • Olga Papp
    • Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , ,

    We show that the simplex method can be interpreted as a cutting-plane method, assumed that a special pricing rule is used. This approach is motivated by the recent success of the cutting-plane method in the solution of special stochastic programming problems. We compare the classic Dantzig pricing rule and the rule that derives from the … Read more

    A Simple Variant of the Mizuno-Todd-Ye Predictor-Corrector Algorithm and its Objective-Function-Free Complexity

  • Tomonari Kitahara
  • Takashi Tsuchiya
    • Categories Linear Programming Tags , , , ,

    In this paper, we propose a simple variant of the Mizuno-Todd-Ye predictor-corrector algorithm for linear programming problem (LP). Our variant executes a natural finite termination procedure at each iteration and it is easy to implement the algorithm. Our algorithm admits an objective-function free polynomial-time complexity when it is applied to LPs whose dual feasible region … Read more

    Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture

  • Edward D. Kim
    • Categories Polyhedra Tags , ,

    We introduce a new combinatorial abstraction for the graphs of polyhedra. The new abstraction is a flexible framework defined by combinatorial properties, with each collection of properties taken providing a variant for studying the diameters of polyhedral graphs. One particular variant has a diameter which satisfies the best known upper bound on the diameters of … Read more

    Interior-Point Algorithms for a Generalization of Linear Programming and Weighted Centering

  • Kurt M. Anstreicher
    • Categories Convex Optimization, Linear Programming Tags , , ,

    We consider an extension of ordinary linear programming (LP) that adds weighted logarithmic barrier terms for some variables. The resulting problem generalizes both LP and the problem of finding the weighted analytic center of a polytope. We show that the problem has a dual of the same form and give complexity results for several different … Read more

    On the Number of Solutions Generated by the Dual Simplex Method

  • Tomonari Kitahara
  • Shinji Mizuno
    • Categories Linear Programming Tags , , ,

    In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the dual simplex method with the most negative pivoting rule for LP. The bound is comparable with the bound given by Kitahara and Mizuno (2010) for the primal simplex method. We apply the result to the … Read more

    On the Number of Solutions Generated by Dantzig’s Simplex Method for LP with Bounded Variables

  • Tomonari Kitahara
  • Tomomi Matsui
  • Shinji Mizuno
    • Categories Linear Programming Tags , , , , ,

    We give an upper bound for the number of different basic feasible solutions generated by Dantzig’s simplex method (the simplex method with the most negative pivoting rule) for LP with bounded variables by extending the result of Kitahara and Mizuno (2010). We refine the analysis by them and improve an upper bound for a standard … Read more