Students' Conference on Nonlinear and Discrete Optimization
SCoNDO, die Konferenz für Nichtlineare und Diskrete Optimierung, findet einmal im Jahr - meist im Juli - an der TUM statt. Die Konferenz bietet den Teilnehmern unserer Kurse Fallstudien Diskrete / Nichtlineare Optimierung die Chance, ihre Projekte und Ergebnisse einem breiteren Publikum zu präsentieren. Zusätzlich zu den 25-minütigen Präsentationen jedes Teams können sie die spezifischen Herausforderungen, die mathematische Theorie und die praktischen Ergebnisse in kurzen Frage-und-Antwort-Runden sowie während der Kaffee- und Mittagspausen diskutieren.
Jeder, der sich für mathematische Optimierung und ihre Anwendungen in realen Projekten interessiert, laden wir herzlich ein, die Vorträge anzuhören und sich mit den Teams zu unterhalten.
SCoNDO 10 in 2019
Datum und Ort
Da die Parkmöglichkeiten in der Umgebung eingeschränkt sind, nutzen Sie bitte möglichst die öffentlichen Verkehrsmittel. Der Tagungsort ist von der U-Bahnstation Garching-Hochbrück (U6) in 5 Minuten zu Fuß erreichbar.
|Morning Session 1||09:00 - 11:10|
|Coffee break||11:10 - 11:40|
|Morning Session 2||11:40 - 13:00|
|Lunch break||13:00 - 14:00|
|Afternoon Session||14:00 - 16:10|
09:00 – Welcome
9:10 – Topology Optimization - Light & Stable
In the field of Topology Optimization, the optimization variable is the distribution of material in a given domain of available free space. Our project partner BMW wants to find the optimal design of a mounting connecting engine and body of a car. The goal of our project was to find a combination of model and efficient solver where constraints on the deformation could be applied in a meaningful way. Objective functions describe the volume or deformability. In each case, suitable constraints are considered. The corresponding deformation field is computed by discretizing the linear elasticity equation with bilinear Finite Elements. The density distribution is discretized by elementwise constants. The different approaches were compared on a simplified 2D geometry.
9:50 – Portfolio Optimization using Conditional Value-at-Risk
In asset management, different financial instruments are combined into a portfolio to reduce the risk of a failed investment. There are different measures to quantify risk in such a portfolio which can be minimized to find the safest investment strategy. We investigate the Conditional Value-at-Risk measure and compare different methods to minimize it in terms of solution quality, runtime and robustness.
10:30 – Time-optimal Nonlinear Model Predictive Control of Autonomous Vehicles
In the hot topic of autonomous driving, motion planning plays an important role. We tackled this task using an optimal control strategy called Model Predictive Control (MPC), in order to have an autonomous vehicle clear a race track autonomously while adapting to possible disturbances. To this end, one has to solve several subproblems such as track generation, choosing a suitable vehicle model and incorporating both into the optimal control problems. Another crucial issue is the notion of time-optimality, that has to be defined. Since the car has to be controlled in real time, the ultimate goal is to find a good trade-off between computation time and accuracy.
11:40 – Constrained Global Optimization of Power Trains
We aim to find a global minimum of a non-convex, non-smooth objective function on a linearly bounded feasible set. It models the fuel consumption of a car with given speed and torque. The variable corresponds to the way of shifting gears. Since, due to the non-smoothness no gradient based method can be applied, we implemented several heuristic approaches to obtain a global solution. Namely, Particle Swarm Method (PSO), Genetic Algorithm (GA) and the Covariance Matrix Adaption Evolution Strategy (CMAES). To include the constraints we tested several (non-differentiable) penalty functions. All methods were implemented and tested in Python and it became clear that the latter one (CMAES) produced the best results and was able to find the feasible set effectively. CMAES also converges faster compared to the PSO and Genetic.
12:20 – Optimal Camera Placement in a Warehouse
Autonomous guided vehicles (AGVs) gain more popularity in the field of logistics. To use such AGVs in a warehouse, the floor needs to be fully covered by cameras for guidance and supervision. Our goal was to find an optimal camera placement to have the minimum number of cameras to cover the whole floor of the warehouse. This problem can be modeled as a Set Cover Problem with varying constraints. Since this problem is
NP-hard, we tried to find a good approximation of the solution. For this, we considered different versions of greedy-type algorithms. Additionally, we compare the results of our algorithm to the optimal solution of the corresponding integer linear program. This allows us to determine how good
our approximate solution is.
14:00 – Photovoltaic Power Plant Optimization
The layout of photovoltaic (PV) power plants which contribute significantly to green energy has to be customized with respect to the area where it should be built. The goal of our project was to develop a tool which determines the optimal layout of a PV powerplant with only the coordinates of the area and the resulting topological information as an input. A suitable simplification is to maximize the number of PV tables fitting in the given area and minimize the length of cables connecting the tables and inverters. For the first subproblem we developed a discretization. For the second one we adjusted Lloyds k-mean algorithm such that all the electro-physical constraints are satisfied. Within the resulting clusters the cabling is represented by a minimum spanning tree.
14:40 – Distributing School Meals
We live in a century where still every ninth person suffers from malnutrition. The School Meals Programme by the World Food Programme (WFP) aims to cut down this number by delivering nutrient rich meals to the schools of students in need. To achieve that, the WFP builds kitchens from where they use vehicles to distribute the meals efficiently to schools nearby. The main part of our task is to develop a suitable model to decide where to place these kitchens and which vehicles are needed to deliver all meals in time. When we plan the distribution network, complexity is greatly increased by taking constraints such as freshness of food into account. A combinatorial optimization problem is formed when representing the network with a complete graph. We find good solutions to our model by covering the resulting graph with suitable tours of food delivering vehicles. In order to visualize the outcome of our well-working approach we created an user-friendly interface.
15:20 – Just-In-Time Delivery in Car Production
Our project is realized in cooperation with AUDI and is about planning efficient transportation routes for their car production. In the automotive production nowadays car parts exist in many different variations. Considering that each variant of a part is stored in a container, it is obvious that this leads to a storage problem at the production line. Therefore trains driven by workers pick up the needed car parts from a storage area and bring them to their target location at the production line. Furthermore, the trains only have a certain time span to fulfill these tasks. Our task was to minimize the amount of workers while still being able to deliver every part "just-in-time" and to allocate the workload equally. Our solution approach is made out of different steps and optimization problems. The main part of our talk will be covered by the presentation of the solution procedure, in which we want to explain the general functionality of our algorithm.
16:00 – Closing
Wir freuen uns, wenn Sie die SCoNDO besuchen, sich die Vorträge anhören und sich mit den Studierenden über ihre Projekte austauschen. Bitte melden Sie sich vorab an, wenn Sie teilnehmen möchten, damit wir Sie mit ausreichend Kaffee, Keksen und Obst versorgen können. Senden Sie dazu einfach eine E-Mail an pfefferer (at) ma.tum.de.
SCoNDO 9 in 2018
08:30 – Welcome
8:40 – Class Scheduling for a special education school
Team Class Scheduling
The software market for scheduling programs for schools already is wide. However, most of this software is designed for high or middle schools. As a special education school, SFZ and their students have more restricted needs for their schedule and therefore a regular software is not applicable anymore.
The goal of this project was to transform the scheduling process from a three-week paperwork with a magnetic board to a fully automized, fast optimization that still reflects all the needs of the school.
The job is now taken over by a mathematical model together with Mosel Xpress, which contains all constraints given by the school. This does not only allow to do the job much faster, but on top optimizes according to priorities. Data pre- and postprocessing makes sure the tool is easy handable and the result format is ready to use right away.
9:20 – Robust graph-based optimization in Localization and Mapping
Team Localization and Mapping
One task in Computer Vision is to map the surrounding environment and localize yourself, which is called Simultaneous Localization and Mapping (SLAM). During long trajectories drift can occur, because of accumulating small errors. Detecting previous location, which is called Loop Closures, allows to minimize the accumulated drift.
This problem can be modeled as a graph optimization. Since current algorithms are not performing well in case of outliers, our aim is to model a robust optimization scheme. Thus, we used the robust algorithm Iteratively Reweighted Least Squares and incorporated adaptive weighting of constraints in the graph. We used the C++ framework g2o for optimizing graph-based nonlinear error functions.
10:30 – Order Batching
Team Order Batching
In a warehouse orders are commissioned by workers. We want to minimize the total path length that is walked by all the workers during one day. Because the path length has a major effect on the commissioning cost, it is reasonable to decrease this objective. To manage the commissioning process one has to come up with combinations of orders that can be collected in a single tour. Then one can tell the workers what orders to pick up and how to walk the warehouse in each tour. The sum over the lengths of all these tours is our objective. As we are aiming for an optimal solution we approach this challenge using an Integer Linear Program. This ILP entails a Knapsack and a Traveling Salesman subproblem.
11:10 – Motion Interpolation and Sensor Fusion
Team Motion Interpolation
Fields such as computer vision and robotics are interested in tracking 3D objects and understanding their position and orientation (6d pose). There are a variety of systems for measuring 6d poses, such as OTS (optical tracking system) or IMUs (inertial measurement units). We combine sensor data from an IMU and OTS to calculate rotation and translation and use non-linear optimization to improve established spline interpolation techniques, to find a smooth and accurate pose trajectory that describes the underlying motion. Interpolations are calculated using unit quaternions, which are analogous but provide several advantages over more common methods of calculating rotation in SO3
11:50 – Optimizing Charter Bus Routes
Team Bus Charter
As Flixbus is continuously expanding, its routes become more and more complex. This complexity is a huge challenge for the company but also provides lots of possibilities for optimization.
In our project, we have been working together with Flixbus Charter, a service which rents out whole busses to various groups of customers, for example for school or business trips. Flixbus itself doesn’t own the busses but works as a facilitator between bus companies and customers. Our task was to develop an algorithm that combines various customer requests to trips so that the costs for Flixbus are minimized. This was very challenging due to constraints like driving regulations or bus capacities. Nevertheless, we found a model that promises savings of more than 8%.
13:30 – Coating Printed Circuit Boards
Team Coating Printed Circuit Boards
Printed Circuit Boards (PCB) are sensitive and thus need to be protected from harmful environmental inﬂuences like dust, moisture and extreme temperature. Therefore, they are coated with a protective material, dispensed onto the PCB using a nozzle held by a robotic arm. This nozzle can only spray stripes with a width of 5 mm or 10 mm.
The area of a PCB is split into areas that must be coated (coating areas), must not be coated (non-coating areas) and area we are free to (or not to) coat. The goal of our project is to design and implement an algorithm that instructs the robot on how to perform.
In order to tackle our problem, we subdivide it into a covering and roundtour subproblem. Covering consists of two steps. In a pre-processing step, each coating area is modiﬁed to satisfy nice geometric properties. Using heuristics, we divide these areas into rectangles and further into stripes.
The combinatorial structure of the covering is captured in a graph where vertices correspond to stripes and edges to transition between or within stripes. Edge-weights are assigned using A* search on an auxiliary graph considering constraints for movement of the nozzle. Finally, on this graph a roundtour is found solving instances of a problem that is strongly related to the travelling salesman problem. Altogether a coating procedure is deﬁned minimizing time and material waste.
14:10 – Modelling and implementing a mixed-integer problem for portfolio optimization
Team Portfolio Optimization
Minimizing the risk of a portfolio is often done by investing in many different asset classes to benefit from diversification. This approach has the disadvantage of high managements costs.
Therefore, we investigated the effect of different constraints on the optimal asset allocation. Our focus was on setting upper bounds for the number of asset classes to invest in, and on using minimal values for the wealth allocation used on these assets.
As all these constraints are of integer value, a mixed-integer optimization problem occurs. In our presentation, we discuss the mathematical formulation of this mixed-integer optimization problem and its implementation in a commercial software with focus on initialisation methods to optimize the run time.
15:20 – Motion planning in robotics - Real-time calculation of a movement
Team Motion Planning in Robotics
The transition from a manual to a digitized production (Industry 4.0) requires the use of robots that have to react quickly to changing conditions. In order to respond to these predictable and unpredictable changes, the robot must be provided with a certain degree of flexibility. To ensure this, it is no longer sufficient to just calculate the movement of a robot arm. A recalculation also has to be done in real-time and therefore as fast as possible to prevent a collision.
To achieve this kind of movement we have performed several numerical approximations to calculate the motion and to implement a fast solving algorithm. Moreover, we have extended the model by applying various approaches for further accelerating the recalculation in order to assure that the trajectory can be found in real-time.
16:00 – Automation of cargo trains scheduling
Team Cargo Trains
Due to a high request of railway companies to the DB network, it is essential to automatically generate a timetable. Our goal is it to maximize the amount of cargo trains routed through the network while passenger trains have already been fixed. To do so, certain constrains like waiting time, blockings of signals and safety distance need to be followed. To approach this problem, a systemized network with nodes and edges has been created. We focused on two nodes and the road in between, which is divided in many segments. As a basis for our different approaches, we pre-processed our data by calculating feasible starting intervals for each segment. First, we used a greedy Algorithm to schedule cargo trains with the same velocity. This follows the extension to different cargo train types with different velocities. To finalize our case study, we give an outlook about how to handle crossings of two roads with a flow model.