Augmented Simplex: A Modified and Parallel Version of Simplex Method Based on Multiple Objective and Subdifferential Optimization Approach

Wierzbicki AP (1993). Augmented Simplex: A Modified and Parallel Version of Simplex Method Based on Multiple Objective and Subdifferential Optimization Approach. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-93-059

[img]
Preview
Text
WP-93-059.pdf

Download (1MB) | Preview

Abstract

In the perspective of parallel computations, new versions of basic optimization algorithms are needed. The paper presents a concept of such coarse-grained parallelization, based on a parametric imbedding into a family of problems or parametrically diversified algorithms. This general idea is exemplified for the case of the simplex algorithm of linear programming, where a linear optimization problem can be imbedded into a multiple-objective family which introduces diversified directions of search cutting through the interior of original admissible set. To improve the effectiveness of such algorithms, an initial phase of directional feasibility search by subdifferential optimization is added. The resulting augmented simplex algorithm, even without parallelization, might be competitive with interior point methods for a certain, broad class of linear programming problems. Necessary theoretical foundations, some algorithmic details and results of preliminary tests are presented.

Item Type: Monograph (IIASA Working Paper)
Research Programs: Methodology of Decision Analysis (MDA)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 02:02
Last Modified: 21 Jul 2016 06:12
URI: http://pure.iiasa.ac.at/3755

Actions (login required)

View Item View Item

International Institute for Applied Systems Analysis (IIASA)
Schlossplatz 1, A-2361 Laxenburg, Austria
Phone: (+43 2236) 807 0 Fax:(+43 2236) 71 313