A polynomial relaxation-type algorithm for linear programming
The paper proposes a polynomial algorithm for solving systems of linear inequalities. The algorithm uses a polynomial relaxation-type procedure which either finds a solution for Ax = b, 0
linear programming
On the Number of Solutions Generated by the Dual Simplex Method
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
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
New developments in the primal-dual column generation technique
The classical column generation is based on optimal solutions of the restricted master problems. This strategy frequently results in an unstable behaviour and may require an unnecessarily large number of iterations. To overcome this weakness, variations of the classical approach use interior points of the dual feasible set, instead of optimal solutions. In this paper, … Read more
A Bound for the Number of Different Basic Solutions Generated by the Simplex Method
In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the … Read more
Klee-Minty’s LP and Upper Bounds for Dantzig’s Simplex Method
Kitahara and Mizuno (2010) get two upper bounds for the number of different basic feasible solutions generated by Dantzig’s simplex method. The size of the bounds highly depends on the ratio between the maximum and minimum values of all the positive elements of basic feasible solutions. In this paper, we show some relations between the … Read more
The central curve in linear programming
The central curve of a linear program is an algebraic curve specified by linear and quadratic constraints arising from complementary slackness. It is the union of the various central paths for minimizing or maximizing the cost function over any region in the associated hyperplane arrangement. We determine the degree, arithmetic genus and defining prime ideal … Read more
A Polynomial Arc-Search Interior-Point Algorithm for Linear Programming
In this paper, ellipse is used to approximate the central path of the linear programming. An interior-point algorithm is devised to search the optimizers along the ellipse. The algorithm is proved to be polynomial with the complexity bound $O(n^{\frac{1}{2}}\log(1/\epsilon))$. Numerical test is conducted for problems in Netlib. For most tested Netlib problems, the result shows … Read more
Computational and Economic Limitations of Dispatch Operations in the Next-Generation Power Grid
We study the interactions between computational and economic performance of dispatch operations under highly dynamic environments. In particular, we discuss the need for extending the forecast horizon of the dispatch formulation in order to anticipate steep variations of renewable power and highly elastic loads. We present computational strategies to solve the increasingly larger optimization problems … Read more
On the Equivalencey of Linear Programming Problems and Zero-Sum Games
In 1951, Dantzig showed the equivalence of linear programming and two-person zero-sum games. However, in the description of his reduction from linear programming to zero-sum games, he noted that there was one case in which his reduction does not work. This also led to incomplete proofs of the relationship between the Minmax Theorem of game … Read more