Zeynep Şuvak (Bogazici University)

A Branch-and Bound Algorithm to Solve Minimum Cost Flow Problem with Conflicts
Tuesday 1 October 2019 at 11.10pm, JCMB 5323

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.

Seminars by year

Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996