Decomposition methods for mixed-integer linear programming

Abstract: Many decision problems in industry and society, such as vehicle routing, scheduling and air traffic planning, can be modelled as mixed-integer linear programs (MILPs). No polynomial-time methods are known for these problems in general. Modern MILP solvers are remarkably capable, but large-scale applications often call for exploiting the problem structure even further. Decomposition methods do this by splitting a problem into parts that are coordinated through a feedback mechanism, while retaining optimality guarantees. I will present some fundamental concepts behind two decomposition approaches. The first is Dantzig-Wolfe decomposition, where a reformulation in a higher-dimensional space can give a much stronger model, which is solved by branch-price-and-cut. The second is logic-based Benders decomposition, which is well suited to “assign then schedule” problems. Since the seminar series has a broad applied mathematics audience, most of the talk will be introductory. For the optimisation experts, I will also briefly mention the directions of our ongoing research projects.

numerical analysisoptimization and control

Audience: researchers in the discipline

CAM seminar

Series comments: Online streaming via zoom on exceptional cases if requested. Please contact the organizers at the latest Monday 11:45.