Artelys - Training for Combinatorial Optimization III: Relaxation & Hybridization
Aside from the attributes, it is possible to get around a problem by using its structure. In such a case, rather than solving a large size problem subject to combinatorial explosion, it is possible to solve several small problems in a coordinated way: this is the principle of decomposition. In some cases, it may even be advantageous to combine Combinatorial Optimization techniques (IP, CP, local search) to overcome a problem particularly difficult to solve. This is the principle of hybridization.
COURSE OBJECTIVES
Mastering the principles of hybridization and decomposition methods in order to solve difficult problems of large size.
TARGET AUDIENCE
Engineers, economists, scientists and developers interested in modeling decision problems and implementing optimization algorithms.
INSTRUCTORS
Artelys consultants specialized in modeling and solving large size optimization models applied to the domains of energy, transport and logistics.
Hybridization techniques
- Linear programming / Constraint programming hybridization. Mixed modeling, common search trees, dialogue among branching schemes. Using reduced cost.
- Constraint programming / Local search hybridization. Description of neighborhoods as constrained neighborhoods. Under constraints’ neighborhood exploration.
Decomposition techniques
- Principles of Price Decomposition and Resource Decomposition. Types of information exchanges. Elementary examples.
- Lagrangian. Duality. Definition and economic interpretation of the dual function. Duality gap. Convex and Non-Convex cases.
- Price Decomposition: coordination algorithms and Non-differentiable Optimization.
- Benders decomposition: principles and implementation.
Applications
- Joint gas and electricity assets optimization: introduction, Benders and price decomposition.
- Example of constraint programming and local search hybridization: timetables scheduling, frequency assignment.
- Decomposition and hybridization for maintenance scheduling.
Next session
November 2023
Special session available
(minimum of 4 participants, on-site or online)
Training Duration
2 days
Training cost
Inter-company: €1,800 excluding taxes per person
In-house: €9,000 excluding taxes per session
This includes the materials, meals, coffee and handouts. Computers are provided.
Artelys is a training institution, registered under n°11754066975.