I often tell beginners in optimization modeling that before starting to code, they should get a piece of paper and write down the mathematical model. There are several reasons for this:

I am a full-time consultant and provide services related to the design, implementation and deployment of mathematical programming, optimization and data-science applications. I also teach courses and workshops. Usually I cannot blog about projects I am doing, but there are many technical notes I'd like to share. Not in the least so I have an easy way to search and find them again myself. You can reach me at erwin@amsterdamoptimization.com.

## Monday, March 29, 2021

## Sunday, March 28, 2021

### Parallel machine scheduling I, two formulations

## Tuesday, March 23, 2021

### SOS1 sets: when to use them

Short answer: almost never.

Beginners in optimization are always very excited when they read about SOS sets in the documentation. This looks like a very efficient tool to use for constructs like pick (at most) 1 out of \(n\) (SOS1) or for interpolation (SOS2). However, experienced modelers use SOS sets very sparingly. Why? Well, solvers like binary variables much better than SOS sets. Binary variables yield great bounding and cuts (there has been enormous progress in this area), while SOS constructs are really just about branching.

## Wednesday, March 17, 2021

### MST + few Steiner points: convex quadratic model

In [1], I discussed a model for the **Euclidean Streiner Tree problem**. A non-convex integer programming model from the literature was reformulated into a MISOCP (not a version of a Japanese dish, but a **Mixed-Integer Second-Order Cone Program**). Together with a symmetry-breaking constraint and some high-performance solvers, this can lead to being able to solve larger models.

One of the disadvantages of the model in [1] is that it only works with the full number of Steiner points \(n-2\) where \(n\) is the number of given (original) points. Here I want to discuss how we can use Minimum Spanning Tree (MST) models [2], as a building block for a model where we can add just a few Steiner points. One reason this is interesting: the first few Steiner points have the most impact on the objective.

## Tuesday, March 16, 2021

### Excel Never Dies

In a post by (famous economist) Paul Krugman:

I’m sometimes embarrassed at how much I use Excel. But it turns out to be a work of genius.

The online article he refers to is:

Packy McCormick, Ben Rollert,

Excel Never Dies, https://www.notboring.co/p/excel-never-dies

It is a nice read.

In my work, I see Excel intensively used by (almost) all clients I work with or talk to. One sometimes wonders: what would happen if Excel would just suddenly stop working everywhere?

## Monday, March 15, 2021

### Euclidean Steiner tree problems as MISOCP

In [1] I looked at MIP models for the Minimum Spanning Tree problem. A related, but much more difficult problem is the **Euclidean Steiner Tree Problem**. Here we are allowed to add points to make the tree shorter. Here are two obvious examples [2]:

## Friday, March 12, 2021

## Monday, March 8, 2021

### Minimum Spanning Trees in Math Programming Models

Algorithms for the Minimum Spanning Tree (MST) problem are readily available. However, sometimes we want to solve this problem inside a Mathematical Programming model. Usually, this is for two reasons:

- We have some side constraints
- Or as part of a larger model

**Data**

---- 298 SETcitiesManchester, N.H. , Montpelier, Vt. , Detroit, Mich. , Cleveland, Ohio , Charleston, W.Va. Louisville, Ky. , Indianapolis, Ind. , Chicago, Ill. , Milwaukee, Wis. , Minneapolis, Minn. Pierre, S.D. , Bismarck, N.D. , Helena, Mont. , Seattle, Wash. , Portland, Ore. Boise, Idaho , Salt Lake City, Utah, Carson City, Nevada , Los Angeles, Calif. , Phoenix, Ariz. Santa Fe, N.M. , Denver, Colo. , Cheyenne, Wyo. , Omaha, Neb. , Des Moines, Iowa Kansas City, Mo. , Topeka, Kans. , Oklahoma City, Okla., Dallas, Tex. , Little Rock, Ark. Memphis, Tenn. , Jackson, Miss. , New Orleans, La. , Birmingham, Ala. , Atlanta, Ga. Jacksonville, Fla. , Columbia, S.C. , Raleigh, N.C. , Richmond, Va. , Washington, D.C. Boston, Mass. , Portland, Me.

**dantzig42**from TSPLIB [8].

## Monday, March 1, 2021

### A difficult multi-line regression data set

In [1], I discussed some models for a small 2 line regression problem. Here I want to dive into a more challenging problem.