article

Solving the Fixed Charge Problem by Ranking the Extreme Points

Pages 268 - 279

https://doi.org/10.1287/opre.16.2.268

Published: 01 April 1968 Publication History

Abstract

<P>An algorithm for ranking the basic feasible solutions corresponding to a linear programming problem in increasing order of the linear objective function is described. An application of this algorithm for obtaining the minimal cost solution to a fixed charge problem is given. This algorithm can be applied in general to solve any fixed charge problem. However, the algorithm works efficiently when the problem is nondegenerate and the range in the values of the variable costs is large compared to the fixed charges. This algorithm can also be applied when the fixed charge part of the cost function is replaced by a concave function.</P>

References

[1]

W. M. HIESCH AND G. B. DANTZIG, "Notes on Linear Programming: Part XIX, The Fixed Charge Problem," Rand Research Memorandum No. 1383, Santa Monica, Calif., (1954).

Google Scholar

[2]

W. M. HIESCH AND A. J. HOFFMAN, "Extreme Varieties, Concave Functions and the Fixed Charge Problem," Communications on Pure and Applied Mathematics, Vol. XIV, No. 3 (August 1961).

Google Scholar

[3]

M. L. BALINSKI, "Fixed Cost Transportation Problems," Naval Res. Log. Quart. 8, No. 1 (1961).

Google Scholar

[4]

H. W. KUHN AND W. J. BAUMOL, "An Approximate Algorithm for the Fixed Charges Transportation Problem," Naval Res. Log. Quart. 9 (1962).

Google Scholar

[5]

A. S. MANNE, "Plant Location under Economies of Scale Decentralization and Computation," Management Sci. 11, No. 2 (1964).

Google Scholar

[6]

D. GATE, The Theory of Linear Economic Models, McGraw-Hill, New York, 1960.

Google Scholar

Cited By

View all

Zhao YLarsson TRönnberg EPardalos P(2018)The fixed charge transportation problemJournal of Global Optimization10.1007/s10898-018-0661-y72:3(517-538)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s10898-018-0661-y
Upmanyu MSaxena R(2016)On solving a multiobjective fixed charge problem with imprecise fractional objectivesApplied Soft Computing10.1016/j.asoc.2015.10.00840:C(64-69)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.asoc.2015.10.008
Roberti RBartolini EMingozzi A(2015)The Fixed Charge Transportation ProblemManagement Science10.1287/mnsc.2014.194761:6(1275-1291)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1287/mnsc.2014.1947
Show More Cited By

Recommendations

The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation

The fixed charge transportation problem generalizes the well-known transportation problem where the cost of sending goods from a source to a sink is composed of a fixed cost and a continuous cost proportional to the amount of goods sent. In this paper, ...
LP extreme points and cuts for the fixed-charge network design problem

Many design decisions in transporation, communication, and manufacturing planning can be modeled as problems of routing multiple commodities between various origin and destination nodes of a directed network. Each arc of the network is uncapacitated and ...
Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem

This paper addresses the multicommodity capacitated fixed-charge network design problem with nonbifurcated flows and hop constraints. We present and compare mathematical programming formulations for this problem and we study different relaxations: ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Operations Research Volume 16, Issue 2

April 1968

233 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 April 1968

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhao YLarsson TRönnberg EPardalos P(2018)The fixed charge transportation problemJournal of Global Optimization10.1007/s10898-018-0661-y72:3(517-538)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.1007/s10898-018-0661-y
Upmanyu MSaxena R(2016)On solving a multiobjective fixed charge problem with imprecise fractional objectivesApplied Soft Computing10.1016/j.asoc.2015.10.00840:C(64-69)Online publication date: 1-Mar-2016
https://dl.acm.org/doi/10.1016/j.asoc.2015.10.008
Roberti RBartolini EMingozzi A(2015)The Fixed Charge Transportation ProblemManagement Science10.1287/mnsc.2014.194761:6(1275-1291)Online publication date: 1-Jun-2015
https://dl.acm.org/doi/10.1287/mnsc.2014.1947
Adlakha VKowalski K(2015)Fractional Polynomial Bounds for the Fixed Charge ProblemJournal of Optimization Theory and Applications10.1007/s10957-013-0437-y164:3(1026-1038)Online publication date: 1-Mar-2015
https://dl.acm.org/doi/10.1007/s10957-013-0437-y
Buson ERoberti RToth P(2014)A Reduced-Cost Iterated Local Search Heuristic for the Fixed-Charge Transportation ProblemOperations Research10.1287/opre.2014.128862:5(1095-1106)Online publication date: 1-Oct-2014
https://dl.acm.org/doi/10.1287/opre.2014.1288
Adlakha VKowalski K(2014)On lower bounds for the fixed charge problemComputers and Operations Research10.1016/j.cor.2014.07.00952:PA(105-112)Online publication date: 1-Dec-2014
https://dl.acm.org/doi/10.1016/j.cor.2014.07.009
Sorokin ABoginski VNahapetyan APardalos P(2013)Computational risk management techniques for fixed charge network flow problems with uncertain arc failuresJournal of Combinatorial Optimization10.1007/s10878-011-9422-225:1(99-122)Online publication date: 1-Jan-2013
https://dl.acm.org/doi/10.1007/s10878-011-9422-2
Agarwal YAneja Y(2012)Fixed-Charge Transportation ProblemOperations Research10.1287/opre.1120.104160:3(638-654)Online publication date: 1-May-2012
https://dl.acm.org/doi/10.1287/opre.1120.1041
Xie FJia R(2012)Nonlinear fixed charge transportation problem by minimum cost flow-based genetic algorithmComputers and Industrial Engineering10.1016/j.cie.2012.04.01663:4(763-778)Online publication date: 1-Dec-2012
https://dl.acm.org/doi/10.1016/j.cie.2012.04.016
Jawahar NBalaji N(2012)A genetic algorithm based heuristic to the multi-period fixed charge distribution problemApplied Soft Computing10.1016/j.asoc.2011.09.01912:2(682-699)Online publication date: 1-Feb-2012
https://dl.acm.org/doi/10.1016/j.asoc.2011.09.019
Show More Cited By

Abstract

References

Cited By

Recommendations

The Fixed Charge Transportation Problem: An Exact Algorithm Based on a New Integer Programming Formulation

LP extreme points and cuts for the fixed-charge network design problem

Formulations for the nonbifurcated hop-constrained multicommodity capacitated fixed-charge network design problem

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media