Which equipment should be bought for a given sum to increase the profit of an industrial enterprize with a known specification of production within given limits? This problem is described as a large-scalelinear progr...
详细信息
Which equipment should be bought for a given sum to increase the profit of an industrial enterprize with a known specification of production within given limits? This problem is described as a large-scalelinear program (LP) of a specific structure. An effective preliminary analysis for this structure was proposed in Ioslovich and Makarenkov [On methods of dimensionality reduction in linearprogramming, Econ. Math. Methods Moscow (in Russian) 11(3) (1975) 316-324] which aimed to reduce the size of the problem by detection of the redundant and active constraints. In this paper a robust system is considered, dealing with box-constrained uncertainties in the input coefficients. The analysis is based on robust evaluations of bounds for primal and dual constraints. A robust evaluation of uncertain duals presented in [I. Ioslovich, P.-O. Gutman, Robust redundancy determination and evaluation of the dual variables of linearprogramming problems in the presence of uncertainty, 1, in, V. Kucera, M. Sebek (Eds.), Proceedings of 3rd IFAC Symposium on Robust Control Design (ROCOND 2000), IFAC, Prague, Czech Republic, Elsevier Science, Amsterdam, 2000, paper 115] is essentially used. (C) 2007 The Franklin Institute. Published by Elsevier Ltd. All rights reserved.
We propose a new pivot rule for the simplex algorithm, which is demonstrative in the dual space intuitively. Although it is based on normalized reduced costs, like the steepest-edge rule and its variants, the rule is ...
详细信息
We propose a new pivot rule for the simplex algorithm, which is demonstrative in the dual space intuitively. Although it is based on normalized reduced costs, like the steepest-edge rule and its variants, the rule is much simpler and cheaper than the latter. We report computational results obtained with the 47 largest Netlib problems in terms of the number of rows and columns, all of the 16 Kennington problems, and the 17 largest BPMPD problems. Over the total 80 problems, a variant of the rule outperformed the Devex rule with iterations and time ratio 1.43 and 3.24, respectively. (c) 2007 Elsevier B.V. All rights reserved.
We revise the dual projective pivot algorithm using sparse rectangular LU factors. In each iteration, the proposed algorithm solves at most three triangular systems, while simplex algorithms solve four. Instead of the...
详细信息
We revise the dual projective pivot algorithm using sparse rectangular LU factors. In each iteration, the proposed algorithm solves at most three triangular systems, while simplex algorithms solve four. Instead of the classical basis, it uses a so-called pseudobasis ( a rectangular matrix having fewer columns than rows), thereby solving smaller linear systems with a potentially improved stability compared to simplex algorithms. Most importantly, it generates good search directions at a low cost. We report encouraging computational results on a set of 50 Netlib standard test problems as well as a set of 15 much larger real-world problems. A code named RDPPA 1.10 based on the proposed algorithm outperformed MINOS 5.51 significantly in terms of both iterations and run time. In particular, it appears that a high proportion of degenerate iterations need not imply many total iterations ( contradicting the common belief).
A set of new tests for linearprogramming presolving analysis is described. These tests are applicable for linear programs with box constraints and positive or zero coefficients. Partial applicability to general linea...
详细信息
A set of new tests for linearprogramming presolving analysis is described. These tests are applicable for linear programs with box constraints and positive or zero coefficients. Partial applicability to general linearprogramming (LP) problems is discussed in a special section. The aim is to detect and remove redundant rows and columns. The tests are based on the solution of some auxiliary LP problems with one constraint and upper bounds on the variables. A comparison with the Klein-Holm numerical test is presented. The tests are applied iteratively to the primal and dual LP problems. The method is also applicable to LP problems with coefficients belonging to some range of uncertainty, providing a robust procedure for scale reduction. A detailed numerical example and results of numerical experiments are presented.
An algorithm incorporating the Logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage stochastic programs. Basic properties concerning the existence and uniqueness of the soluti...
详细信息
An algorithm incorporating the Logarithmic barrier into the Benders decomposition technique is proposed for solving two-stage stochastic programs. Basic properties concerning the existence and uniqueness of the solution and the underlying path are studied. When applied to problems with a finite number of scenarios, the algorithm is shown to converge globally and to run in polynomial-time.
This paper deals with an algorithm incorporating the interior-point method into the Dantzig-Wolfe decomposition technique for solving large-scale linear programming problems, The algorithm decomposes a linear program ...
详细信息
This paper deals with an algorithm incorporating the interior-point method into the Dantzig-Wolfe decomposition technique for solving large-scale linear programming problems, The algorithm decomposes a linear program into a main problem and a subproblem. The subproblem is solved approximately. Hence, inexact Newton directions are used in solving the main problem. We show that the algorithm is globally linearly convergent and has polynomial-time complexity.
In this paper, we focus on large-scale multiobjective linearprogramming problems with the block angular structure. By considering the imprecise nature of human judgements, we assume that the decision maker may have a...
详细信息
In this paper, we focus on large-scale multiobjective linearprogramming problems with the block angular structure. By considering the imprecise nature of human judgements, we assume that the decision maker may have a fuzzy goal for each of the objective functions. Having elicited the corresponding linear membership functions through the interaction with the decision maker, we adopt the fuzzy decision for aggregating them. Then it is shown that the formulated problem can be reduced to one master problem and a number of linear subproblems and the satisficing solution for the decision maker can be obtained by directly applying the Dantzig-Wolfe decomposition method.
In this paper, we focus on large-scale linear programming problems with block angular structure for which the Dantzig-Wolfe decomposition method has been successfully applied. By considering the vague nature of human ...
详细信息
In this paper, we focus on large-scale linear programming problems with block angular structure for which the Dantzig-Wolfe decomposition method has been successfully applied. By considering the vague nature of human judgements, we assume that the decision maker may have a fuzzy goal for the objective function and fuzzy constraints for the coupling constraints. Having elicited the corresponding linear membership functions through the interaction with the decision maker, if we adopt the convex fuzzy decision for combining them, it is shown that, under some appropriate conditions, the formulated problem can be reduced to a number of independent linear subproblems and the overall satisficing solution for the decision maker is directly obtained just only solving the subproblems.
In this paper, by considering the experts' imprecise or fuzzy understanding of the nature of the parameters in the problem-formulation process, large-scale multiobjective block-angular linearprogramming problems ...
详细信息
In this paper, by considering the experts' imprecise or fuzzy understanding of the nature of the parameters in the problem-formulation process, large-scale multiobjective block-angular linearprogramming problems involving fuzzy numbers are formulated. Through the use of the alpha-level sets of fuzzy numbers, an extended Pareto optimality concept, called the alpha-Pareto optimality is introduced. To generate a candidate for the satisficing solution which is also alpha-Pareto optimal, decision maker is asked to specify the degree alpha and the reference objective values. It is shown that the corresponding alpha-Pareto optimal solution can be easily obtained by solving the minimax problems for which the Dantzig-Wolfe decomposition method is applicable. Then a linearprogramming-based interactive decision-making method for deriving a satisficing solution for the decision maker efficiently from an alpha-Pareto optimal solution set is presented. (C) 1997 Elsevier Science B.V.
In this paper, a large-scale multiobjective block-angular linearprogramming problem involving fuzzy parameters is formulated by considering the experts' vague understanding of the nature of the parameters in the ...
详细信息
In this paper, a large-scale multiobjective block-angular linearprogramming problem involving fuzzy parameters is formulated by considering the experts' vague understanding of the nature of the parameters in the problem-formulation process. Using the α-level sets of fuzzy numbers, the corresponding nonfuzzy α-programming problem is introduced and the fuzzy goals of the decision maker are quantified by eliciting the membership functions. Through the introduction of an extended Pareto optimality concept, if the decision maker specifies the degree a and the reference membership values, the corresponding extended Pareto optimal solution can be obtained by solving the minimax problems for which the Dantzig-Wolfe decomposition method is applicable. Then a linearprogramming-based interactive fuzzy satisficing method for deriving a satisficing solution for the decision maker from an extended Pareto optimal solution set is presented.
暂无评论