Optimization Online


Combinatorial Acyclicity Models for Potential-based Flows

Oliver Habeck(habeck***at***mathematik.tu-darmstadt.de)
Marc E. Pfetsch(pfetsch***at***mathematik.tu-darmstadt.de)

Abstract: Potential-based flows constitute a basic model to represent physical behavior in networks. Under natural assumptions, the flow in such networks must be acyclic. The goal of this paper is to exploit this property for the solution of corresponding optimization problems. To this end, we introduce several combinatorial models for acyclic flows, based on binary variables for flow directions. We compare these models and introduce a particular model that tries to capture acyclicity together with the supply/demand behavior. We analyze properties of this model, including variable fixing rules. Our computational results show that the usage of the corresponding constraints speeds up solution times by about a factor of 3 on average and a speed-up of a factor of almost 5 for the time to prove optimality.

Keywords: Potential-based flows, network optimization, potential networks, acyclic flows

Category 1: Network Optimization

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: TU Darmstadt, Department of Mathematics, Research Group Optimization, Dolivostr. 15, 64293 Darmstadt, April 2020

Download: [PDF]

Entry Submitted: 04/21/2020
Entry Accepted: 04/21/2020
Entry Last Modified: 04/21/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society