Ankan Mitra

Ankan Mitra

Critical thinker!

Research

My current research focuses on large scale optimization of network models using combinatorial algorithms. I study four large scale combinatorial problems in different domain applications with a common network structure. In particular, the focus is on problems in wireless sensor networks, wastewater networks and transportation networks. I propose models and algorithmic enhancements include modeling of valid inequalities which exploit the underlying network structure, solution building algorithms as branch-and-bound node heuristics, network size reduction techniques. I will keep this page posted with any and all developments!

    Maximum Capacity Path Interdiction Problem

    Abstract

    This paper studies the continuous maximum capacity path interdiction problem, where two players, user and interdictor, compete in a capacitated network. The user wants to send the maximum possible amount of flow through a path, whose capacity is given by the minimum capacity among its arcs. The budget-constrained interdictor decreases arc capacities by any continuous amount to reduce the quality of the user’s chosen path. We present an efficient algorithm based on a discrete version of the Newton’s method, which helps us solve the problem in polynomial time. We also prove that the problem can be transformed into a zero-sum game, which has always a pure Nash equilibrium point. We demonstrate the performance of our algorithm over a set of randomly generated networks.

    Read more here