Events

ERGO seminar: Zeynep Şuvak (Bogazici University)

Location: Room 5323 - James Clerk Maxwell Building, Edinburgh EH9 3JZ, UK

Description: A Branch-and Bound Algorithm to Solve Minimum Cost Flow Problem with Conflicts Abstract:The focus of this work is on an extension of the minimum cost flow problem in connected networks. Arc flows must satisfy a compatibility restriction in addition to flow balance and capacity constraints: at most one of the conflicting arcs is allowed to have positive flow on it. This variant of the minimum cost flow problem, which we call the minimum cost flow problem with conflicts, can be used to model scheduling problems in container terminals, online event-based social networks or sensor networks. After discussing the difficulty of the problem, a set of pre-processing procedures to reduce the problem size are introduced and integer linear programming formulations of the problem are given. Also, a branch-and-bound algorithm with several combinatorial branching rules and a “strong branching” scheme is described. The algorithm is implemented using efficient data structures and the results of computational experiments reveal that the proposed exact solution method is more successful than solving the underlying integer linear programming formulations with a commercial solver.Joint work with İ. Kuban Altınela and Necati Aras.