filmov
tv
Michele Conforti: Scanning integer points with lex-cuts: A finite cutting plane algorithm...
Показать описание
Full Title: Michele Conforti: Scanning integer points with lex-cuts: A finite cutting plane algorithm for nonlinear programming over compact sets
The lecture was held within the framework of the follow-up workshop to the Hausdorff Trimester Program: Combinatorial Optimization.
Abstract:
We consider the integer points in a box B, ordered by a lexicographic rule. To each integer point x in B we associate a cutting plane (lex-cut) that eliminates the integer points in B that are lexicographically smaller than x and is satisfied by the others. The family of lex-cuts contains the Chvátal-Gomory cuts, but does not contain and is contained in the family of split cuts.We give finite cutting plane method based on lex-cuts to solve the integer program min{cx: x ∈ S ∩ Zn}, where S ⊂ Rn is a compact set and c ∈ Zn. We analyze the worst-case behavior of our algorithm and propose some variants.
Joint work with Marianna De Santis, Marco Di Summa and Francesco Rinaldi.
The lecture was held within the framework of the follow-up workshop to the Hausdorff Trimester Program: Combinatorial Optimization.
Abstract:
We consider the integer points in a box B, ordered by a lexicographic rule. To each integer point x in B we associate a cutting plane (lex-cut) that eliminates the integer points in B that are lexicographically smaller than x and is satisfied by the others. The family of lex-cuts contains the Chvátal-Gomory cuts, but does not contain and is contained in the family of split cuts.We give finite cutting plane method based on lex-cuts to solve the integer program min{cx: x ∈ S ∩ Zn}, where S ⊂ Rn is a compact set and c ∈ Zn. We analyze the worst-case behavior of our algorithm and propose some variants.
Joint work with Marianna De Santis, Marco Di Summa and Francesco Rinaldi.
0:27:03
1:04:04
0:58:07