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. Nach den Präsentationen und einer Evaluation des Kurses erhalten die Teilnehmer ihre Zertifikate. Den erfolgreichen Abschluss der Projekte feiern wir am Abend mit einem Konferenz-Dinner.
SCoNDO 9 in 2018
Datum und Ort
SCoNDO 9 findet am Samstag, den 7. Juli von 8:30 bis 18:15 Uhr im Hörsaal 2 (Raum BC2 0.01.17) in Garching, Parkring 35-39, statt. Das Konferenz-Dinner beginnt um 18:30 Uhr in der Quantum Lounge im selben Gebäude.
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 Sessions||8:30 - 12:30|
|Afternoon Sessions||13:30 - 16:40|
|Evaluation & Zertifikate||17:00 - 18:15|
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.
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 michael.ritter (at) tum.de. Natürlich laden wir Sie auch dezu ein, an unserem Konferenz-Dinner teilzunehmen - wir arrangieren bis zur Mittagspause eine Pizza-Bestellung. Sollten Sie erst später dazu kommen, informieren Sie uns bitte, wenn Sie etwas bestellen möchten.