# Piecewise Linear Approximations in MIP Models

In the past, I’ve written about piecewise linear approximations of functions of a single variable. (There are too many posts to list here. Just type “piecewise linear” in the search box of my blog if you want to find them.) Handling piecewise linear approximations of multivariable functions is a bit more intimidating. I’ll illustrate one …

More

# 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

# CPLEX 12.8: Generic Callbacks

IBM is getting ready to release CPLEX 12.8, and I had the opportunity to attend a presentation about by Xavier Nodet at the 2017 INFORMS annual meeting. Here are links to two presentations by Xavier: CPLEX Optimization Studio 12.8 – What’s New and CPLEX 12.8 – the Generic Callback. As with any new release, there …

More

# Memory Minimization

As I grow older, I’m starting to forget things (such as all the math I ever learned) … but that’s not the reason for the title of this post. A somewhat interesting question popped up on Mathematics StackExchange. It combines a basic sequencing problem (ordering the processing of computational tasks) with a single resource constraint …

More

# If This and That Then Whatever

I was asked a question that reduced to the following: if $$x$$, $$y$$ and $$z$$ are all binary variables, how do we handle (in an integer programming model) the requirement “if $$x=1$$ and $$y=1$$ then $$z=1$$”? In the absence of any constraints on $$z$$ when the antecedent is not true, this is very easy: add …

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

# MIP Models in R with OMPR

A number of R libraries now exist for formulating and solving various types of mathematical programs in R (or formulating them in R and solving them with external solvers). For a comprehensive listing, see the Optimization and Mathematical Programming task view on CRAN. I decided to experiment with Dirk Schumacher’s OMPR package for R. OMPR …

More

# Enforcing Simultaneous Arrivals

I’m recapping here an answer to a modeling question that I just posted on a help forum. (Since it will now appear in two different places, let’s hope it’s correct!) The original poster (OP) was working on a routing model, in which vehicles (for which I will use and if needed as indices) are assigned …

More

# Selecting the Least Qualifying Index

Something along the following lines cropped up recently, regarding a discrete optimization model. Suppose that we have a collection of binary variables $x_i \in B, \, i \in 1,\dots,N$ in an optimization model, where $B=\{0, 1\}$. The values of the $x_i$ will of course be dictated by the combination of the constraints and objective function. …

More

# Feelings of Rejection

This is a quick (?) recap of an answer I posted on a support forum earlier today. I will couch it in terms somewhat specific to CPLEX, but with minor tweaks it should apply to other mixed-integer programming solvers as well. It is possible to “warm start” CPLEX (and, I’m pretty sure, at least some …

More

# Partitioning with Binary Variables

Armed with the contents of my last two posts (“The Geometry of a Linear Program“, “Branching Partitions the Feasible Region“), I think I’m ready to get to the question that motivated all this. Let me quickly enumerate a few key take-aways from those posts: The branch and bound method for solving an integer linear program …

More

# Branching Partitions the Feasible Region

Yesterday’s post got me started on the subject of the geometry of a linear program (LP). Today I want to review another well-known geometric aspect, this time of integer linear programs (ILPs) and mixed integer linear programs (MILPs), that perhaps slips some people’s minds when they are wrestling with their models. Most solvers use some …

More

# Flagging a Specific Variable Value

A recent question on a web forum, one I’ve seen asked elsewhere, was the following: in a mathematical programming model, how does one constrain a binary variable to take the value 1 if another variable takes a specific (predefined) value, and 0 otherwise? If the binary variable is , the other variable is , and …

More

# Linearize That!

For whatever reason, I’ve seen a bunch of questions posted on various fora boiling down to “How do I linearize <insert grossly nonlinear function>?” Whether by coincidence or due to some virtual viral epidemic, I’ve seen three or four in the past week that involved logarithms. So, without further ado, here is the quick solution: …

More

# Multiple Children – Again!

I thought I had exhausted this topic, but no such luck … As noted in a previous post (“When the OctoMom Solves MILPs“), CPLEX (and I believe most other integer programming solvers) are have a design limitation of at most two child nodes per parent node in the search tree. Personally, I don’t consider that limitation a …

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

# Modeling an On/Off Span

I may be ruining a perfectly good homework problem by posting this. :-) Occasionally someone needs to incorporate in an integer programming model the notion of something changing state for a predefined span of time. The typical characterization I’ve seen is as follows: we have a sequence of binary variables xi∈{0,1},i∈{1,…,N} that indicate the state …

More