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

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

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