Please use this identifier to cite or link to this item:
https://ruomo.lib.uom.gr/handle/7000/253
Title: | A dual exterior point simplex type algorithm for the minimum cost network flow problem |
Authors: | Geranis, George Paparrizos, Konstantinos Sifaleras, Angelo |
Type: | Article |
Subjects: | FRASCATI::Natural sciences::Mathematics::Applied Mathematics FRASCATI::Natural sciences::Computer and information sciences |
Keywords: | Operations research Combinatorial optimization Minimum cost network flow problem |
Issue Date: | 2009 |
Source: | Yugoslav Journal of Operations Research |
Volume: | 19 |
Issue: | 1 |
First Page: | 157 |
Last Page: | 170 |
Abstract: | A new dual simplex type algorithm for the Minimum Cost Network Flow Problem (MCNFP) is presented. The proposed algorithm belongs to a special 'exterior- point simplex type' category. Similarly to the classical network dual simplex algorithm (NDSA), this algorithm starts with a dual feasible tree-solution and reduces the primal infeasibility, iteration by iteration. However, contrary to the NDSA, the new algorithm does not always maintain a dual feasible solution. Instead, the new algorithm might reach a basic point (tree-solution) outside the dual feasible area (exterior point - dual infeasible tree). |
URI: | https://doi.org/10.2298/YJOR0901157G https://ruomo.lib.uom.gr/handle/7000/253 |
ISSN: | 0354-0243 |
Other Identifiers: | 10.2298/YJOR0901157G |
Appears in Collections: | Department of Applied Informatics |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
A dual exterior point simplex type algorithm for the minimum cost network flow problem.pdf | 231,38 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.