More on “Core Points”

A few additions to yesterday’s post occurred to me belatedly. First, it may be a good idea to check whether your alleged core point \(y^0\) is actually in the relative interior of the integer hull \(\mathrm{conv}(Y)\). A sufficient condition is that, when you substitute \(y^0\) into the constraints, all inequality constraints including variable bounds have …

More

Finding a “Core Point”

In a famous (or at least relatively famous) paper [1], Magnanti and Wong suggest a method to accelerate the progress of Benders decomposition for certain mixed-integer programs by sharpening “optimality” cuts. Their approach requires the determination of what they call a core point. I’ll try to follow their notation as much as possible. Let \(Y\) …

More

Fischetti on Benders Decomposition

I just came across slides for a presentation that Matteo Fischetti (University of Padova) gave at the Lunteren Conference on the Mathematics of Operations Research a few days ago. Matteo is both expert at and dare I say an advocate of Benders decomposition. I use Benders decomposition (or variants of it) rather extensively in my …

More

Updated Benders Example

Two years ago, I posted an example of how to implement Benders decomposition in CPLEX using the Java API. At the time, I believe the current version of CPLEX was 12.4; as of this writing, it is 12.6.0.1. Around version 12.5, IBM refactored the Java API for CPLEX and, in the process, made one or …

More