## Thursday, April 29, 2021

### What is this BRATIO option in GAMS?

This is a note about BRATIO, a very exotic GAMS option related to providing an advanced basis to a Simplex-based LP (or NLP) solver.

## Tuesday, April 20, 2021

### Inverting a matrix by LP

The questions for this post are:

• Can we model the inversion of a matrix as an LP problem? (A: yes)
• Should we do that? (A: no)
• If we insist, can we make it a bit quicker (A: yes)

## Monday, April 19, 2021

### Parallel machine scheduling II, three more formulations

In [1] two formulations were discussed for a scheduling problem with multiple machines. Here we add a few more. Some of them are a bit strange. None of them really works better than the ones in [1].

So this is a collection of formulations that may sound reasonable at first, but are really not suited for this problem. If you want to read about good models, skip this post.

## Monday, April 5, 2021

### This is really a modeling issue

In [1], the following scenario is described:

1. A MIP model is solved, delivering a feasible solution.
2. All integer variables are fixed to their levels.
3. The resulting LP model is solved in order to produce duals. This model turns out to be infeasible.

## Monday, March 29, 2021

### Mathematical Notation

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:

## Sunday, March 28, 2021

### Parallel machine scheduling I, two formulations

Scheduling problems with multiple machines are not that easy for MIP solvers. However, modern solvers are capable to solve reasonably sized problems to optimality quite efficiently. Here are some notes.

## Tuesday, March 23, 2021

### SOS1 sets: when to use them

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 Dieshttps://www.notboring.co/p/excel-never-dies