# 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

# Benders Decomposition with Generic Callbacks

Brace yourself. This post is a bit long-winded (and arguably geekier than usual, which is saying something). Also, it involves CPLEX 12.8, which will not ship until some time next month. I have an updated version of an old example, solving a fixed charge transportation problem using Benders decomposition. The example (using Java, naturally) is …

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

# Support for Benders Decomposition in CPLEX

As of version 12.7, CPLEX now has built-in support for Benders decomposition. For details on that (and other changes to CPLEX), I suggest you look at this post on J-F Puget’s blog and Xavier Nodet’s related slide show. [Update 12/7/16: There is additional information about the Benders support in a presentation by IBM’s Andrea Tramontani …

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