Shuvomoy Das Gupta
Home
Papers
Talks
Teaching
Blog

Shuvomoy Das Gupta

sdg2019 

Shuvomoy Das Gupta
Ph.D. Student
Operations Research Center
Massachusetts Institute of Technology
Email: sdgupta@mit.edu
Google Scholar

About Me

Hello world! I am a second 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.

Preprint

  • Shuvomoy Das Gupta, Bartolomeo Stellato, and Bart Van Parys, “Exterior-point Operator Splitting for Nonconvex Learning”, 2020. [pdf] [NExOS.jl Julia package]

    • Abstract: In this paper, we present the nonconvex exterior-point operator splitting (NExOS) algorithm, a novel linearly convergent first-order algorithm tailored for constrained nonconvex learning problems. We consider the problem of minimizing a convex cost function over a nonconvex constraint set, where projection onto the constraint set is single-valued around local minima. A wide range of nonconvex learning problems have this structure including (but not limited to) sparse and low-rank optimization problems. By exploiting the underlying geometry of the constraint set, NExOS finds a locally optimal point by solving a sequence of penalized problems with strictly decreasing penalty parameters. NExOS solves each penalized problem by applying an outer iteration operator splitting algorithm, which converges linearly to a local minimum of the corresponding penalized formulation under regularity conditions. Furthermore, the local minima of the penalized problems converge to a local minimum of the original problem as the penalty parameter goes to zero. We implement NExOS in the open-source Julia package NExOS.jl, which has been extensively tested on many instances from a wide variety of learning problems. We study several examples of well-known nonconvex learning problems, and we show that in spite of being general purpose, NExOS is able to compute high quality solutions very quickly and is competitive with specialized algorithms.

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] [presentation]

    • 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] [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.

Talks

Teaching

  • Optimization Methods (Fall 2020)
    • Teaching assistant for a course that aims to provide masters students with a unified overview of the main algorithms and areas of application in optimization.
    • Duties: Assisting students, leading recitations, writing and marking assignments and exams.

MASc Thesis

Optimization Models for Energy-efficient Railway Timetables. (Grade: A+) [pdf] [html presentation]

Miscellaneous

Notes on Splitting Algorithms