A direct simplex algorithm for network flow problems with convex piecewise linear costs

Autor:	Richard V. Helgason, Rajluxmi V. Murthy
Rok vydání:	1994
Předmět:	Piecewise linear function Mathematical optimization Control and Optimization Optimization problem Simplex algorithm Applied Mathematics Piecewise linear manifold Piecewise Function (mathematics) Minimum-cost flow problem Flow network Software Mathematics
Zdroj:	Optimization Methods and Software. 4:191-207
ISSN:	1029-4937 1055-6788
DOI:	10.1080/10556789408805587
Popis:	Minimum cost network flow problems with a piecewise linear convex cost function are used to model various optimization problems. They are also used extensively to approximate nonlinear cost functions which may otherwise be difficult to handle. Solving the piecewise linear problems using a reformulation approach is possible but may be inefficient. In thispaper we discuss a specialized direct approach and its implementation for solving such problems. The direct approach handles the piecewise linear structure of the cost function by allowing each arc to have varying costs on different segments. Computational results havel been reported, from which we conclude that using such an approach has adistinct advantage over using a reformulation approach.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::a00dbdab0f21dae109983a5ce9efae94 https://doi.org/10.1080/10556789408805587 Zobrazit plný text záznamu