Shuvomoy Das Gupta
 |
Shuvomoy Das Gupta |
About Me
Hello world! I am a first year Ph.D. student at the Operations Research Center at MIT, advised by Professor Bart Van Parys.
I obtained my M.A.Sc. (GPA 4.00/4.00) from the ECE Department, University of Toronto in 2016.
After that, I worked as a researcher at the Research & Technology
Department of Thales
Canada for more than two and a half years. My M.A.Sc.
research work on optimization models to compute
energy-efficient railway timetables has
been integrated with the largest installed base of communication based
train control systems worldwide. Previously, I obtained my B.Sc. in
Electrical and Electronic Engineering from Bangladesh University of Engineering and
Technology.
Peer-reviewed Papers
-
Shuvomoy Das Gupta and Lacra Pavel, “On seeking efficient Pareto optimal points in multi-player minimum cost flow problems with application to transportation systems”, in the Journal of Global Optimization 74 (2019): 523-548. [pdf]
- Abstract: In this paper, we propose a multi-player extension of the minimum cost flow problem inspired by a transportation problem that arises in modern transportation industry. We associate one player with each arc of a directed network, each trying to minimize its cost function subject to the network flow constraints. In our model, the cost function can be any general nonlinear function, and the flow through each arc is an integer. We present algorithms to compute efficient Pareto optimal point(s), where the maximum possible number of players (but not all) minimize their cost functions simultaneously. The computed Pareto optimal points are Nash equilibriums if the problem is transformed into a finite static game in normal form.
-
Shuvomoy Das Gupta, “On Convergence of Heuristics Based on Douglas-Rachford Splitting and ADMM to Minimize Convex Functions over Nonconvex Sets”, in the proceedings of the 56th Allerton Conference on Communication, Control, and Computing, University of Illinois at Urbana-Champaign, IL, USA, October 2018. [pdf] [presentation]
- Abstract: Recently, heuristics based on the Douglas-Rachford splitting algorithm and the alternating direction method of multipliers (ADMM) have found empirical success in minimizing convex functions over nonconvex sets, but not much has been done to improve the theoretical understanding of them. In this paper, we investigate convergence of these heuristics. First, we characterize optimal solutions of minimization problems involving convex cost functions over nonconvex constraint sets. We show that these optimal solutions are related to the fixed point set of the underlying nonconvex Douglas-Rachford operator. Next, we establish sufficient conditions under which the Douglas-Rachford splitting heuristic either converges to a point or its cluster points form a nonempty compact connected set. In the case where the heuristic converges to a point, we establish sufficient conditions for that point to be an optimal solution. Then, we discuss how the ADMM heuristic can be constructed from the Douglas-Rachford splitting algorithm. We show that, unlike in the convex case, the algorithms in our nonconvex setup are not equivalent to each other and have a rather involved relationship between them. Finally, we comment on convergence of the ADMM heuristic and compare it with the Douglas-Rachford splitting heuristic.
-
Shuvomoy Das Gupta and Lacra Pavel, “Multi-player minimum cost flow problems with nonconvex costs and integer flows”, in the proceedings of the 55th IEEE Conference on Decision and Control, Las Vegas, USA, December 12-14, 2016. [pdf] [longer version with proofs] [presentation]
- Abstract: In this paper, we consider a variant of the well known minimum cost flow problem in a directed network with nonconvex costs and integer flows. We formulate the problem in a multi-player setup, whereby we associate one player with each arc of the network. The goal of each player is to minimize its nonconvex cost that depends on the integer flow through the arc subject to the network flow constraints. In this multi-player setup, a Pareto optimal point is justified to be an efficient solution concept. We propose an algorithm to compute a Pareto optimal point. We show that, although the problem in its original form has coupled constraints binding every player, there exists an equivalent variable transformation that decouples the optimization problems for a number of players. Each of the decoupled players can solve its optimization problem in a decentralized manner. We use the solutions of those decoupled players to transform the optimization problems for the rest of the players using consensus constraints. Then we present algorithms based on algebraic geometry to find a Pareto optimal point.
-
Shuvomoy Das Gupta, J. Kevin Tobin and Lacra Pavel, “A two-step linear programming model for energy-efficient timetables in metro railway networks”, in Transportation Research Part B: Methodological 93 (2016): 57–74. [pdf]
- Abstract: In this paper, we propose a novel two-step linear optimization model to calculate energy-efficient timetables in metro railway networks. The resultant timetable minimizes the total energy consumed by all trains and maximizes the utilization of regenerative energy produced by braking trains, subject to the constraints in the railway network. In contrast to other existing models, which are N P-hard, our model is computationally the most tractable one being a linear program. We apply our optimization model to different instances of service PES2-SFM2 of line 8 of Shanghai Metro network spanning a full service period of one day (18 h) with thousands of active trains. For every instance, our model finds an optimal timetable very quickly (largest runtime being less than 13 s) with significant reduction in effective energy consumption (the worst case being 19.27%). Code based on the model has been integrated with Thales Timetable Compiler - the industrial timetable compiler of Thales Inc that has the largest installed base of communication based train control systems worldwide.
- Code based on the optimization model has been incorporated into the railway timetable compiler of Thales Inc, which is a major provider of communication-based train control software worldwide. It is available to all of their customers as a product and has been deployed around the world in cities such as London, Paris, Hong Kong, Singapore, Kuala Lumpur, Shanghai, Beijing, San Francisco, New York and Vancouver. For more information regarding the implementation, please see my M.A.Sc. thesis.
-
Shuvomoy Das Gupta, Lacra Pavel and J. Kevin Tobin, “An Optimization Model to Utilize Regenerative Braking Energy in a Railway Network”, in the proceedings of 2015 American Control Conference (ACC), Chicago, IL, USA, July 2015. [pdf] [longer version with proofs] [html presentation]
- Abstract: In this paper, we study the railway timetabling problem to utilize regenerative braking energy produced by trains in a railway network. An electric train produces regenerative energy while braking, which is often lost in present technology. A positive overlapping time between braking and accelerating phases of a suitable train pair makes it possible to save electrical energy by transferring the regenerative energy of the braking train to the accelerating one. We propose a novel optimization model to determine a timetable that saves energy by maximizing the total overlapping time of all suitable train pairs. We apply our optimization model to different instances of a railway network for a time horizon spanning six hours. For each instance, our model finds an optimal or near-optimal timetable within an acceptable running time. We observe significant increase in the final overlapping time compared to the existing timetable for every instance, thus making it possible to save the associated electrical energy.
- The paper was featured as one of the top four research projects from Canada at 2015 International Research Days on Ground Transportation, Palaiseau, France.
MASc Thesis
Optimization Models for Energy-efficient Railway Timetables. (Grade: A+) [pdf] [html presentation]
Miscellaneous
Notes on Splitting Algorithms