 A network simplex method for the budget-constrained minimum cost flow problemMichael Holzhauser, Sven O. Krumke and Clemens Thielen European Journal of Operational Research, 2017, vol. 259, issue 3, 864-872 Abstract: We present a specialized network simplex algorithm for the budget-constrained minimum cost flow problem, which is an extension of the traditional minimum cost flow problem by a second kind of costs associated with each edge, whose total value in a feasible flow is constrained by a given budget B. We present a fully combinatorial description of the algorithm that is based on a novel incorporation of two kinds of integral node potentials and three kinds of reduced costs. We prove optimality criteria and combine two methods that are commonly used to avoid cycling in traditional network simplex algorithms into new techniques that are applicable to our problem. With these techniques and our definition of the reduced costs, we are able to prove a pseudo-polynomial running time of the overall procedure, which can be further improved by incorporating Dantzig’s pivoting rule. Moreover, we present computational results that compare our procedure with Gurobi (2016). Keywords: Combinatorial optimization; Algorithms; Network flow; Minimum cost flow; Network simplex (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:259:y:2017:i:3:p:864-872 DOI: 10.1016/j.ejor.2016.11.024 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.