In this paper, we present an interactive fuzzy satisficing method for large-scale multiobjective linearprogramming problems with the block angular structure. By considering the vague nature of human judgements, we as...
详细信息
In this paper, we present an interactive fuzzy satisficing method for large-scale multiobjective linearprogramming problems with the block angular structure. By considering the vague nature of human judgements, we assume that the decision maker (DM) may have a fuzzy goal for each of the objective functions. Having elicited the corresponding linear membership functions, if the DM specifies the reference membership levels for all the membership functions, the corresponding Pareto optimal solution which is, in the minimax sense, nearest to the requirement or better than that if the reference membership levels are attainable can be obtained by solving the minimax problem. Here it is shown that the formulated minimax problem can be reduced to one master problem and a number of linear subproblems and the Pareto optimal solution together with the trade-off rate information between the membership functions can be obtained by applying the Dantzig-Wolfe decomposition method. In this way, the satisficing solution for the DM can be derived from Pareto optimal solutions by updating the current reference membership levels on the basis of the current levels of the membership functions together with the trade-off rates between the membership functions.
This paper documents the results of an experimental computer code that implements a parallel decomposition algorithm for staircase linear programs. The tests were conducted on an IBM 3090/600E computer, which has 6 pr...
详细信息
This paper documents the results of an experimental computer code that implements a parallel decomposition algorithm for staircase linear programs. The tests were conducted on an IBM 3090/600E computer, which has 6 processors. This type of linear program represents a worst-case example for measuring the performance of parallel decomposition. Indeed, one may find it interesting that there is any opportunity for speedup under these conditions, but experiments on 13 small- to medium-sized ''real world'' test problems show that in addition to speedups of from 2 to 10 provided by decomposition alone, there are speedups of up to 3.3 provided by using 4 processors. On average, the speedup provided by 4 processors over the faster of the 2 single processor algorithms is about 2. These results can be extrapolated to situations with larger problems and/or more processors with a fair degree of confidence.
This paper describes a method and the corresponding algorithms for simplification of large-scale linear programming models. It consists of the elimination of the balance constraints (i.e. constraints with zero RHS ter...
详细信息
We present several new steepest-edge simplex algorithms for solving linearprogramming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in w...
详细信息
We present several new steepest-edge simplex algorithms for solving linearprogramming problems, including variants of both the primal and the dual simplex method. These algorithms differ depending upon the space in which the problem is viewed as residing, and include variants in which this space varies dynamically. We present computational results comparing steepest-edge simplex algorithms and approximate versions of them against simplex algorithms that use standard pivoting rules on truly large-scale real-world linear programs with as many as tens of thousands of rows and columns. These results demonstrate unambiguously the superiority of steepest-edge pivot selection criteria to other pivot selection criteria in the simplex method.
An interior point method for block angular optimization is developed and the convergence properties of the method are described. A major motivation for such a method is that most of the computation is easily paralleli...
详细信息
An interior point method for block angular optimization is developed and the convergence properties of the method are described. A major motivation for such a method is that most of the computation is easily parallelized. Computational results are presented for a class of large-scale linear programming models. These models are multicommodity flow problems that arise from an Air Force (Military Airlift Command) application and generate problems as large as 100,000 rows and 300,000 columns.
This paper is concerned with linearprogramming problems in which many of the constraints are handled implicitly by requiring that the vector of decision variables lie in a polyhedronX. It is shown that the simplex me...
详细信息
This paper is concerned with linearprogramming problems in which many of the constraints are handled implicitly by requiring that the vector of decision variables lie in a polyhedronX. It is shown that the simplex method can be implemented using a working basis whose size is the number of explicit constraints as long as the local structure ofX around the current point is known. Various ways of describing this local structure lead to known implementations whenX is defined by generalized or variable upper bounds or flow conservation constraints. In the general case a decomposition principle can be used to generate this local structure. We also show how to update factorizations of the working basis.
This is a comparison of two state-of-the-art large-scale nonlinear optimization systems exhibiting unprecedented problem solution capabilities both in size of problem handled and method of solution. These codes are MI...
详细信息
This is a comparison of two state-of-the-art large-scale nonlinear optimization systems exhibiting unprecedented problem solution capabilities both in size of problem handled and method of solution. These codes are MINOS, developed by B. A. Murtagh and M. A. Saunders, and XS, developed by G. G. Brown and G. W. Graves. The codes are evaluated with respect to their problem solving capabilities and potential for practical applica- tion by analysts. Computational results are presented for thirteen nonlinear and nonlinear mixed integer test problems with from two to 793 variables (12 to 100 integer variables) and one to 401 constraints. Portions of this work were presented at the CORS/ORSA/TIMS joint meeting in Toronto, May 1981.
暂无评论