Shuvomoy Das Gupta
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.
-
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.
-
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.
- 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
|