Revisiting the fixed charge transportation problem
| Autor: | Schrenk, Susann, Cung, Van-Dat, Finke, Gerd |
|---|---|
| Přispěvatelé: | Optimisation Combinatoire (G-SCOP_OC), Laboratoire des sciences pour la conception, l'optimisation et la production (G-SCOP), Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS)-Université Joseph Fourier - Grenoble 1 (UJF)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National Polytechnique de Grenoble (INPG)-Centre National de la Recherche Scientifique (CNRS), Recherche Opérationnelle pour les Systèmes de Production (G-SCOP_ROSP), Cung, Van-Dat |
| Jazyk: | angličtina |
| Rok vydání: | 2009 |
| Předmět: | |
| Zdroj: | European Chapter on Combinatorial Optimization (ECCO) XXII European Chapter on Combinatorial Optimization (ECCO) XXII, May 2009, Jerusalem, Israel. pp.19 |
| Popis: | International audience; We analyze degeneracy characterizations for two classical problems: the transportation paradox in linear transportation problems and the pure fixed charge transportation problem. Solving the pure constant fixed charge problem is equivalent to finding a basic tree solution with maximum degree of degeneracy. Problems possess degenerate solutions if the equal subsum property is satisfied for the supplies and demands. To determine the existence of degeneracy is an NP-complete problem. But this NP-hardness remains even if all equal-subsums are known in advance. Finally, the paradox is linked to overshipment solutions, which belong to supply and demand configurations that tend to have a high degree of degeneracy. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|