PhD in Applied Mathematics
PROJECTS
In this paper we propose a branch, price and remember algorithm to solve the U shaped assembly line balancing problem. Our proposed algorithm uses a column generation approach to obtain tight lower bounds for this problem. It also stores generated columns in memory to enhance the speed of column generation approach. We also develop a modification of Hoffman algorithm to obtain high quality upper bounds. Our computational results show that our proposed algorithm is able to optimally solve 255 of Scholl's well-known 269 benchmark problems. Previous best known exact algorithm, ULINO, is able to solve 233 of the 269 benchmark problems. We also examined our algorithm on a new data set and the results show that our algorithm is able to solve 96.48 percent of all available benchmark problems.
The paper is available here.
In this paper a new model is proposed for the integrated problem of supply chain network designing and
assembly line balancing under demand uncertainty. In this problem there are three types of entities:
manufacturers, assemblers and customers. Manufacturers provide assemblers with components and
assemblers use these components to produce the final products and satisfy the demand of the customers.
This problem involves determining the location of manufacturers and assemblers in the network,
balancing the assembly lines, and transportation of materials and products throughout the network. A
mixed integer nonlinear programming formulation based on two stage stochastic programming method
is developed to solve this problem to optimality. Moreover, an outer approximation (OA) method is
proposed to efficiently solve this problem. The computational results show efficiency of the proposed
OA method.
The paper is available here.
Image courtesy of Sven Torfinn.
Motivated by the control of invasive biological populations, we consider a class of optimization problems for moving sets
t↦ Ω (t)⊂ IR2. Given an initial set Ω0, the goal is to minimize the area of the contaminated set Ω(t) over time, plus a cost related to the control effort. Here the control function is the inward normal speed along the boundary ∂Ω(t). We prove the existence of optimal solutions, within a class of sets with finite perimeter. Necessary conditions for optimality are then derived, in the form of a Pontryagin maximum principle. Additional optimality conditions show that the sets Ω(t) cannot have certain types of outward or inward corners. Finally, some explicit solutions are presented.
The detailed results are available here.
Image courtesy of Sven Torfinn.
We consider a controlled reaction-diffusion equation, motivated by a pest eradication problem. Our goal is to derive a simpler model, describing the controlled evolution of a contaminated set. In this direction, the first part of the paper studies the optimal control of 1-dimensional traveling wave profiles. Using Stokes' formula, explicit solutions are obtained, which in some cases require measure-valued optimal controls. In the last section we introduce a family of optimization problems for a moving set. We show how these can be derived from the original parabolic problems, by taking a sharp interface limit.
This research is available as a paper here.
Image courtesy of Wikipedia.
Well-posedness of the models
Model Validation with Data
We investigate the performance of our proposed models with data. We use artificially generated data from a microsimulator called SUMO to validate our models. SUMO is a free, open, microscopic and space-continuous road traffic simulation suite designed to handle large road networks. We use the data generated by SUMO as a proxy for real traffic and consider it as the ground truth in our experiments. We use the car-following model developed by Krauss.
We consider three macroscopic models: FIFO, non-FIFO, and our proposed FIFOQ model. In order to produce the time evolution of the solutions of these models, we use a highly resolved Godunov/CTM discretization. Note that, for the FIFOQ model a proper queue treatment has been applied.
To be able to use the results of the microsimulator to validate and compare the macroscopic models, we need to convert the data from the microsimulator into a form that is compatible with the results of these models. In other words, we need to extract the macroscopic quantities, such as vehicle density and queue length, from the microsimulator.
The extraction of vehicle densities is done via a kernel density estimation (KDE) approach with a customized treatment of the boundary points to alleviate the underestimation of vehicle densities due to lack of data in these areas.
Regarding the extraction of the queue length, we use a rule-based approach that mainly uses the vehicle's speed and distance from the leading vehicle. Specifically, if both of the following conditions are satisfied, then the vehicle, regardless of the lane it occupies, is considered to be in the queue:
-
The speed of the vehicle is less than a threshold speed.
-
The distance of the vehicle from its leader is smaller than a threshold distance.
We also assume that once a vehicle enters the queue, it is considered to be in the queue until it enters the off-ramp.
The video to the left shows the performance of various macroscopic models in comparison with SUMO. For more information, please refer to my dissertation available here.
Traffic Flow Modelling With Lego Robots
In this project, we use mathematical models to represent physics of movements of a Lego robot. A PID controller is used to control both the Lego robot and the Matlab simulation. We plan to design smarter controllers that can work for any type of path at high speeds. The eventual purpose of this project is to simulate vehicles and study the events on the road.
Duckiebots
Autonomous Vehicle Simulation Using Duckiebots
In this project, we use duckiebots to simulate autonomous vehicles.
Raspberry Pi Robot
Raspberry Pi Robot
In this project, we design a robot based on Raspberry Pi with a camera and ultrasonic distance sensors. We plan to design the robot so that it can autonomously move on a miniature road network using image processing. We expect this robot to be able to move faster than the ones with two wheels.
Off-Ramp Coupling Conditions
Off-Ramp Coupling Conditions Devoid of Spurious Blocking and Re-Routing
When modeling vehicular traffic flow on highway networks via macroscopic models, suitable coupling conditions at the network nodes are crucial. Frequently, the evolution of traffic flow on each network edge is described in a lane-averaged fashion using a single-class Lighthill-Whitham-Richards model. At off-ramps, split ratios (i.e., what percentage of traffic exits the highway) are prescribed that can be drawn from historical data. In this situation, classic FIFO coupling conditions yield unrealistic results, in that a clogged off-ramp yields zero flux through the node. As a remedy, non-FIFO conditions have been proposed. However, as we demonstrate here, those lead to spurious re-routing of vehicles. A new coupling model, FIFO with queue (FIFOQ), is presented which preserves the desirable properties of non-FIFO models while not leading to any spurious re-routing.
Sourdough Project
Estimating the readiness time of sourdough through mathematical modeling of Yeast Fermentation
This problem was presented to us by our industry partners at the Amber Grain Bakery in New Jersey. The aim of this project was to mathematically model the evolution of the volume of sourdough as a function various factors such as ambient temperature and initial ingredient ratios.
Through the course of our work, we investigate the problem experimentally by growing sourdough culture using varied initial ratios at varied ambient temperatures. We then fit the data we gather to a mathematical model which tracks the amount of yeast produced over time. Additionally, we study the microbes present in a sample of culture under a microscope using imaging software. Based on our experimental observations as well as the results of our model, we conclude that the ambient temperature, rather than the initial ratio of flour to water to starter used, is the key factor affecting the time to readiness, contrary to initial expectations.
We designed the sourdough sleeping room, shown in the picture, by hacking a wine cooler and controlling it with an high precision temperature sensor and a micro-controller. The microcontroller regularly reported the temperature to a channel on thingspeak.com website.