Contributed Session Thu.1.H 2036

Thursday, 10:30 - 12:00 h, Room: H 2036

Cluster 4: Conic programming [...]

Linear programming: Theory and algorithms


Chair: Tomonari Kitahara



Thursday, 10:30 - 10:55 h, Room: H 2036, Talk 1

André L. Tits
The power of constraint reduction in interior-point methods

Coauthors: Pierre-Antoine Absil, Meiyun Y. He, Ming-Tse P. Laiu, Dianne P. O'Leary, Sungwoo Park, Luke B. Winternitz


Constraint reduction is a technique by which, within an interior-point method, each search direction is computed based only on a small subset of the inequality constraints, containing those deemed most likely to be active at the solution. A dramatic reduction in computing time may result for severely imbalanced problems, such as fine discretizations of semi-infinite problems.
In this talk, we survey recent advances by the authors, including an algorithm with polynomial complexity. The power of constraint reduction is demonstrated on real-world applications, including filter design. Numerical comparison with both simplex and "unreduced'' interior point is reported.



Thursday, 11:00 - 11:25 h, Room: H 2036, Talk 2

Barbara Abdessamad
Strict quasi-concavity and the differential barrier property of gauges in linear programming


Concave gauge functions were introduced to give an analytical representation to cones. In particular, they give a simple and a practical representation of the positive orthant.
The purpose of the present paper is to present another approach to penalizing the positivity constraints of a linear program by using an arbitrary strictly quasi-concave gauge representation. Throughout the paper, we generalize the concept of the central path and the analytic center in terms of these gauges, introduce the differential barrier concept and establish its relationship with strict quasi-concavity.



Thursday, 11:30 - 11:55 h, Room: H 2036, Talk 3

Tomonari Kitahara
A proof by the simplex method for the diameter of a (0,1)-polytope

Coauthor: Shinji Mizuno


Naddef (1989) showed 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 programming problem.
Our work is motivated by Kitahara and Mizuno (2011), in which they got upper bounds for the number of different solutions
generated by the simplex method.


  cash loans . You can buy Levitra Super Force profitably on our web-site; we offer the medications only of the highest quality and at reasonable prices.