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.


Mastering the principles of hybridization and decomposition methods in order to solve difficult problems of large size.


Engineers, economists, scientists and developers interested in modeling decision problems and implementing optimization algorithms.


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.


• 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.


Practical information

Training Duration
2 days

Entire Catalog
Available on this link

Artelys is a training institution, registered under n°11754066975.


Are you interested in this training ? Register now !



© ARTELYS • All rights reserved • Legal mentions

Pin It on Pinterest

Share This