90C11 Mixed integer programming
How to avoid collisions in scheduling industrial robots?
- In modern production facilities industrial robots play an important role. When two ore more of them are moving in the same area, care must be taken to avoid collisions between them. Due to expensive equipment costs our approach to handle this is very conservative: Each critical area is modeled as a shared resource where only one robot is allowed to use it at a time. We studied collision avoidance in the context of arc welding robots in car manufacture industry. Here another shared resource comes into place. When using laser welding technology every robot needs to be connected to a laser source supplying it with the necessary energy. Each laser source can be connected to up to six robots but serve only one at a time. An instance of the problem consists of a set of robots, a set of welding task, a number of laser sources, a distance table, collision information and a production cycle time. The goal is to design robot tours covering all task and schedule them resource conflict free such that the makespan does not exceed the cycle time. We propose a general model for integrated routing and scheduling including collision avoidance as well as a branch-and-bound algorithm for it. Computational results on data generated with the robot simulation software KuKa Sim Pro are also provided showing that our algorithm outperforms standard mixed-integer models for our application.
On Efficient Solution Methods for Mixed-Integer Nonlinear and Mixed-Integer Quadratic Optimization Problems
- In this thesis we focus on solution methods for convex mixed-integer nonlinear
optimization problems (MINLP). As one main result, we propose a new algorithm
guaranteeing global optimality for convex MINLPs under standard
assumptions. The new algorithm called MIQP-supported outer approximation
(MIQPSOA) incorporates the successive solution of convex mixed-integer
quadratic programs (MIQP) in a linear outer approximation framework. An extensive
numerical competitive study based on several different MINLP solvers shows,
that a first implementation of the new method performs well in terms of both
the reliability and the efficiency. Since the new method is designed to solve simulation-based optimization problems arising in practical engineering applications, the main performance criterion is the number of function evaluations required to solve a problem.
Furthermore, the test results indicate, that the integration of mixed-integer search steps, resulting from the solution of convex MIQPs, significantly improves the reliability and the efficiency compared to well-known linear outer approximation methods.
After reviewing available solution techniques for convex MINLP problems, we present the algorithmic set-up as well as the convergence proof of MIQPSOA. As pointed out in this dissertation, MIQPSOA is a first step towards a convergent MINLP solution method, that solely relies on the successive solution of convex MIQPs as proposed by Exler and Schittkowski. Finally, we present an extensive numerical test case study considering different solution methods for convex MINLPs.
The second part of this thesis deals with efficient solution techniques for
convex mixed-integer quadratic programs, that arise as subproblems during the
solution of MINLPs by MIQP-based algorithms, such as MIQPSOA. First, we
briefly review latest developments in state-of-the-art mixed-integer linear
(MILP) solvers, since we want to develop a MIQP solver that incorporates the most successful components of MILP solvers. As we focus on branch-and-bound methods, one main component is an efficient and robust sub-solver for continuous quadratic programs, which is able to perform warmstarts. On the other hand, cutting planes have led to a tremendous speed-up of mixed-integer linear solvers during the last 20 years. As a consequence, we extend an efficient construction method for disjunctive cutting planes, such that it can be applied for MIQPs.
Extensive numerical tests show, that the performance of a branch-and-bound solver can be significantly increased by exploiting warmstarts. Furthermore, it turns out, that in a majority of the test cases, where disjunctive cutting planes exist, the calculation times are reduced up to a factor of more than 5. Nevertheless there are also instances, where the presents of disjunctive cutting planes significantly slows down the performance. Due to the efficient cut generation method developed within this thesis, the generation of cutting planes has almost no influence on the calculation time, if no disjunctive cuts exist, which is the case in about 45 \% of all test instances. As a consequence, the application of cutting planes for MIQPs needs further attention and especially a dynamic cut management might be very profitable. Finally, we compare the performance of our branch-and-cut solver MIQL with the solver SCIP, which is one of the state-of-the-art MILP solvers, that can also solve MIQPs. These tests indicate, that MIQL outperforms SCIP on hard MIQP instances, while SCIP is faster for simpler test cases.