Semi-Simultaneous Flows and Binary Constrained (Integer) Linear Programs

In: Networks. Available at http://kluedo.ub.uni-kl.de/volltexte/2006/1971/, Submitted, 2006

Authors

• Alexander Engau
• Horst W. Hamacher

Abstract

Linear and integer programs are considered whose coefficient matrices can be partitioned into K consecutive ones matrices. Mimicking the special case of K=1 which is well-known to be equivalent to a network flow problem we show that these programs can be transformed to a generalized network flow problem which we call semi-simultaneous (se-sim) network flow problem. Feasibility conditions for se-sim flows are established and methods for finding initial feasible se-sim flows are derived. Optimal se-sim flows are characterized by a generalization of the negative cycle theorem for the minimum cost flow problem. The issue of improving a given flow is addressed both from a theoretical and practical point of view. The paper concludes with a summary and some suggestions for possible future work in this area.

BibTeX

 
@Article{ EngauHamacher:SemiSimultaneousFlow2006, 
   title = { Semi-Simultaneous Flows and Binary Constrained (Integer) Linear Programs }, 
   author = { Alexander Engau and Horst W. Hamacher },    
   journal = { Networks },           
   note = { Available at http://kluedo.ub.uni-kl.de/volltexte/2006/1971/ },  
   year = 2006, 
} 

---

This publication belongs to the project DeNDeMA.