A Network Simplex Method for the Budget-Constrained Minimum Cost Flow Problem

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...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2016-09
Main Authors: Holzhauser, Michael, Krumke, Sven O, Thielen, Clemens
Format: Article
Language:English
Subjects:
Algorithms
Budgeting
Budgets
Combinatorial analysis
Cost engineering
Costs
Minimum cost
Optimality criteria
Polynomials
Run time (computers)
Simplex method
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422
DOI:10.48550/arxiv.1607.02284