I see. Thank you!

... even though it allows for more fine-grained control and a deeper understanding of MIP aspects, rather than relying on a black-box solver where many things may happen under the hood? This seems to be a trend noticed among students in e.g. previous MIP workshops.

This is great. Thanks for putting this together, Thiago!

If I may ask, is there a particular reason for using a (interface to a) commercial solver rather than an academic or open-source one, such as SCIP? I’m generally curious why it seems to be less commonly used, at least in US institutions ...

And a personal thanks to @thserra.bsky.social for his advice and for inspiring me (and hopefully others) to do this and contribute to the community😄

A special issue of the INFORMS Journal on Optimization is soon open for submissions.

The talk wraps up with future directions, including a Branch-and-Price implementation to handle integrality, and the potential of combining Simplicial and Dantzig-Wolfe decompositions. Lucas also briefly mentions leveraging quantum optimization for tackling QUBO pricing subproblems.

Lucas also draws nice connections to graph theory, where these structural links help identify when and how a problem can be broken down effectively.

Finally, Lucas hints at the promise of block decompositions when the problem allows it. Numerical evidence suggests that when the model breaks into a handful of blocks (typically less than five), block-wise decomposition strategies can be effective.

A key takeaway is that injecting quadratic constraints in the pricing leads to better dual bounds but a harder pricing subproblem (as is the case for general DW in MIP).

The focus then shifts to non-convex binary quadratic problems, with reformulations that blend Dantzig-Wolfe decomposition with convex quadratic reformulations.

Lucas begins with a simplicial decomposition framework inspired by Carathéodory’s theorem, one that doesn’t rely on duality. Several strategies are proposed for handling the master, taking ideas from the Frank-Wolfe method and enhanced with cutting and sifting techniques for the pricing step.

The talk concludes with a discussion on refining the bounds and exploring related problems.

The proofs/extensions to higher dimensions use clever arguments involving tiling and pigeonhole principles.