Students' Conference on Nonlinear and Discrete Optimization
SCoNDO, short for Students' Conference on Nonlinear and Discrete Optimization, takes place at TUM once a year, usually in July. The conference offers the participants of our courses Case Studies Discrete / Nonlinear Optimization a chance to present their projects and results to a wider audience. In addition to a 25 minute presentation from each team, there is also the opportunity to discuss the specific challenges, mathematical theory and practical results in a brief questions-and-answers round, as well as during the coffee and lunch breaks.
Anyone interested in mathematical optimization and its applications in real-world projects is welcome to attend, listen to the talks and engage in conversation with the participants. After the presentations and an evaluation of the course, the participants receive their certificates. To celebrate the successful completion of the projects, a conference dinner is held.
SCoNDO 9 in 2018
Date and Location
SCoNDO 9 will take place on Saturday, 7 July 2018 from 8:30 to 18:15. The conference will be held in lecture hall 2 (room 200.01.17) at Garching, Parkring 35-39. The conference dinner will be held in the evening at 18:30, served in the quantum lounge in the same building.
As parking is somewhat restricted in the area, please use public transport if possible. The conference venue is easily accessible via a 5 minute walk from the U-Bahn station Garching-Hochbrück (U6).
|Morning Sessions||8:30 - 12:30|
|Afternoon Sessions||13:30 - 16:40|
|Evaluation & Certificates||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.
You are welcome to attend the conference, listen to the talks and discuss the projects with our students. If you want to participate, we would appreciate prior registration by email to michael.ritter (at) tum.de, so we can be sure to have ample supplies of coffee, cookies and fruit. Of course, you are also welcome to join us for our conference dinner - an order of pizza will be arranged before the lunch break, so if you can only join later, please let us know if you want to order something.