We develop an algorithmic framework for linear programming guided by dual optimality considerations. The solution process moves from one feasible solution to the next according to an exchange mechanism that is defined...
详细信息
We develop an algorithmic framework for linear programming guided by dual optimality considerations. The solution process moves from one feasible solution to the next according to an exchange mechanism that is defined by a direction and a resulting step size. Part of the direction is obtained via a pricing problem devised in primal and dual forms. From the dual perspective, one maximizes the minimum reduced cost that can be achieved from splitting the set of dual variables in two subsets: one being fixed while the other is optimized. From the primal perspective, this amounts to selecting a nonnegative combination of variables entering the basis. The direction is uniquely complemented by identifying the affected basic variables, if any. The framework is presented in a generic format motivated by and alluding to concepts from network flow problems. It specializes to a variety of algorithms, several of which are well known. The most prominent is the primal simplex algorithm where all dual variables are fixed: this results in the choice of a single entering variable commonly leading to degenerate pivots. At the other extreme, we find an algorithm for which all dual variables are optimized at every iteration. Somewhere in between these two extremes lies the improved primal simplex algorithm for which one fixes the dual variables associated with the nondegenerate basic variables and optimizes the remaining ones. The two last variants both bestow a pricing problem providing necessary and sufficient optimality conditions. As a result, directions yielding strictly positive step sizes at every iteration are also issued from these pricing steps. These directions move on the edges of the polyhedron for the latter while the former can also identify interior directions.
Since its appearance in 1947, the primal simplex algorithm has been one of the most popular algorithms for solving linear programs. It is often very efficient when there is very little degeneracy, but it often struggl...
详细信息
Since its appearance in 1947, the primal simplex algorithm has been one of the most popular algorithms for solving linear programs. It is often very efficient when there is very little degeneracy, but it often struggles in the presence of high degeneracy, executing many pivots without improving the objective function value. In this paper, we propose an improved primal simplex algorithm that deals with this issue. This algorithm is based on new theoretical results that shed light on how to reduce the negative impact of degeneracy. In particular, we show that, from a nonoptimal basic solution with p positive-valued variables, there exists a sequence of at most m - p + 1 simplex pivots that guarantee the improvement of the objective value, where m is the number of constraints in the linear program. These pivots can be identified by solving an auxiliary linear program. Finally, we briefly summarize computational results that show the effectiveness of the proposed algorithm on degenerate linear programs.
We present a version of GMI (Gomory mixed-integer) cuts in a way so that they are derived with respect to a "dual form" mixed-integer optimization problem and applied on the standard-form primal side as colu...
详细信息
We present a version of GMI (Gomory mixed-integer) cuts in a way so that they are derived with respect to a "dual form" mixed-integer optimization problem and applied on the standard-form primal side as columns, using the primal simplex algorithm. This follows the general scheme of He and Lee, who did the case of Gomory pure-integer cuts. Our input mixed-integer problem is not in standard form, and so our cuts are derived rather differently from how they are normally derived. A convenient way to develop GMI cuts is from MIR (mixed-integer rounding) cuts, which are developed from 2-dimensional BMI (basic mixed-integer) cuts, which involve a nonnegative continuous variable and an integer variable. The non-negativity of the continuous variable is not the right tool for us, as our starting point (the "dual form" mixed-integer optimization problem) has no non-negativity. So we work out a different 2-dimensional starting point, a pair of somewhat arbitrary inequalities in one continuous and one integer variable. In the end, we follow the approach of He and Lee, getting now a finitely converging primalsimplex column-generation algorithm for mixed-integer optimization problems.
作者：
Ebrahimnejad, AliTavana, MadjidIslamic Azad Univ
Dept Math Qaemshahr Branch Qaemshahr Iran La Salle Univ
Business Syst & Analyt Dept Lindback Distinguished Chair Informat Syst & Deci Philadelphia PA 19141 USA Univ Paderborn
Fac Business Adm & Econ Business Informat Syst Dept D-33098 Paderborn Germany
Linear programming (LP) is a widely used optimization method for solving real-life problems because of its efficiency. Although precise data are fundamentally indispensable in conventional LP problems, the observed va...
详细信息
Linear programming (LP) is a widely used optimization method for solving real-life problems because of its efficiency. Although precise data are fundamentally indispensable in conventional LP problems, the observed values of the data in real-life problems are often imprecise. Fuzzy sets theory has been extensively used to represent imprecise data in LP by formalizing the inaccuracies inherent in human decision-making. The fuzzy LP (FLP) models in the literature generally either incorporate the imprecisions related to the coefficients of the objective function, the values of the right-hand-side, and/or the elements of the coefficient matrix. We propose a new method for solving FLP problems in which the coefficients of the objective function and the values of the right-hand-side are represented by symmetric trapezoidal fuzzy numbers while the elements of the coefficient matrix are represented by real numbers. We convert the FLP problem into an equivalent crisp LP problem and solve the crisp problem with the standard primalsimplex method. We show that the method proposed in this study is simpler and computationally more efficient than two competing FLP methods commonly used in the literature. (C) 2014 Elsevier Inc. All rights reserved.
In this paper, we propose a new Dantzig-Wolfe decomposition for degenerate linear programs with the non degenerate constraints in the master problem and the degenerate ones in the subproblem. We propose three algorith...
详细信息
In this paper, we propose a new Dantzig-Wolfe decomposition for degenerate linear programs with the non degenerate constraints in the master problem and the degenerate ones in the subproblem. We propose three algorithms. The first one, where some set of variables of the original problem are added to the master problem, corresponds to the Improved primal simplex algorithm (IPS) presented recently by Elhallaoui et al. [7]. In the second one, some extreme points of the subproblem are added as columns in the master problem. The third algorithm is a mixed implementation that adds some original variables and some extreme points of a subproblem to the master problem. Experimental results on some degenerate instances show that the proposed algorithms yield computational times that are reduced by an average factor ranging from 3.32 to 13.16 compared to the primalsimplex of CPLEX. (C) 2010 Elsevier B.V. All rights reserved.
In this paper, we propose two new perturbation simplex variants. Solving linear programming problems without introducing artificial variables, each of the two uses the dual pivot rule to achieve primal feasibility, an...
详细信息
In this paper, we propose two new perturbation simplex variants. Solving linear programming problems without introducing artificial variables, each of the two uses the dual pivot rule to achieve primal feasibility, and then the primal pivot rule to achieve optimality. The second algorithm, a modification of the first, is designed to handle highly degenerate problems more efficiently. Some interesting results concerning merit of the perturbation are established. Numerical results from preliminary tests are also reported. [ABSTRACT FROM AUTHOR]
暂无评论