# Coordinating Variable Signs

Someone asked me today (or yesterday, depending on whose time zone you go by) how to force a group of variables in an optimization model to take the same sign (all nonpositive or all nonnegative). Assuming that all the variables are bounded, you just need one new binary variable and a few constraints. Assume that …

More

# Minimizing a Median

$$\def\xorder#1{x_{\left(#1\right)}} \def\xset{\mathbb{X}} \def\xvec{\mathbf{x}}$$A somewhat odd (to me) question was asked on a forum recently. Assume that you have continuous variables $$x_{1},\dots,x_{N}$$ that are subject to some constraints. For simplicity, I’ll just write $$\xvec=(x_{1},\dots,x_{N})\in\xset$$. I’m going to assume that $$\xset$$ is compact, and so in particular the $$x_{i}$$ are bounded. The questioner wanted to …

More

# Rolling Horizons

I keep seeing questions posted by people looking for help as they struggle to optimize linear programs (or, worse, integer linear programs) with tens of millions of variables. In my conscious mind, I know that commercial optimizers such as CPLEX allow models that large (at least if you have enough memory) and can often solve …

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

# 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

# Better Estimate, Worse Result

I thought I might use a few graphs to help explain an answer I posted on Quora recently. First, I’ll repeat the question here: In parametric optimization with unknown parameters, does a better estimator of the parameter always lead to better solutions to the actual problem? Here we’re trying to minimize f(x,θ) with respect to …

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

# Using CLP with Java

The COIN-OR project provides a home to a number of open source software projects useful in operations research, primarily optimization programs and libraries. Possibly the most “senior” of these projects is CLP, a single-threaded linear program solver. Quoting the project description: CLP is a high quality open-source LP solver. Its main strengths are its Dual …

More

# Matching Ordering Is Not Always Easy

In some circumstances, you might want to build an optimization model containing two sets of variables, say and , and constrain them so that the sort order of each matches. That condition is easily expressed in logical terms: if and only if for all pairs with . Translating that into a mathematical programming model that …

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

# The Geometry of a Linear Program

I frequently see questions on forums, in blog comments, or in my in-box that suggest the person asking the question is either unfamiliar with the geometry of a linear program, unsure of the significance of it, or just not connecting their question to the geometry. This post is just the starting point for addressing some …

More

# Turning Bounds into Constraints in CPLEX

I had to delve into the CPLEX documentation today, and found something I had not seen before. As part of a (Java) program I’m writing, I need to use the conflict refiner to track down which upper and lower bounds on variables take a role in making a linear program infeasible. Of course, I could change the …

More