Mixed-Integer Linear Programming
Coordination: Prof. Dr. Jörg Rambau
Contact: Prof. Dr. Jörg Rambau
Represented in MODUS since 2009/01
Members with experience in this area:
- Prof. Dr. Jörg Rambau
The method "Mixed-Integer Linear Programming":
WHAT IS THIS?
Mixed-Integer Linear Programming (MILP) denotes optimization problems with continuous and integer variables, influencing a linear objective function and restricted by linear constraints.
WHAT IS IT GOOD FOR?
MILP is the right model, when decisions to be optimized refer to indivisible entities and all quantitative relations can be expressed by linear equations and linear inequalities. For example, the navigation in a street network has to decide whether to turn right or to turn left – it is not possible that half a car goes to either side. The total travel time is the sum of all travel times between crossings. A famous example for the power of MILP are proven optimal solutions to very large instances of the Traveling Salesman Problem (TSP). In a TSP, a shortest closed tour visiting a given set of cities has to be planned. Trying out all possibilities for a 100-cities-TSP would mean to enumerate far more solutions than there are atoms in the universe. In contrast to this naive approach, MILP methods could solve TSPs with 25000 cities to proven optimality! The speciality of MILP compared to heuristic methods is the ability to generate not only better solutions but also so-called dual bounds during the solution process. Dual bounds provide a cost value that cannot be improved by any feasible solution. The solution process can be stopped as soon as one has found a solution whose optimality gap, i.e., the distance to the optimal value, is satisfactory.
WHERE HAVE WE APPLIED IT?
The members of MODUS have applied this method for the following challenges:
- Optimal dspatching of ADAC service vehicles
- Optimal dispatching of pallet elevators in factories
- Optimal distribution of apparel among branches assorted by sizes
- Optimal inventory management in multi-echelon warehouse networks
- Optimal sequencing for the welding of islands in generative production
- Optimal consolidation of full-truckload deliveries for logistic networks