## Wednesday, September 4, 2024

### Multiple Solutions in Minimum Spanning Tree example

In [1], I discussed some LP and MIP formulations for the Minimum Spanning Tree (MST) problem.

 Minimum Spanning Tree visualized through Google Maps

Here, I focus on two formulations: a multicommodity network approach (this can be solved as a large LP) and a MIP formulation based on techniques we know from the Traveling Salesman Problem (TSP). The main issue I want to discuss is the presence of multiple optimal solutions.

## Sunday, September 1, 2024

### N-queens and solution pool

In [1], I described some chess-related problems. Here, I want to reproduce the $$n$$-queens problem. The single solution problem, placing as many queens on the chess board as possible so they don't attack each other, is pretty standard. I want to focus on the more complex question: How many different ways can we place those queens? In other words: what are all the optimal solutions? We can do this by adding a no-good constraint that forbids the previously found solution. However, as this problem has more than a handful of different solutions, I want to use the Cplex solution pool.

### Single Solution Model

We define the decision variables as: $\color{darkred}x_{i,j} = \begin{cases} 1 & \text{if we place a queen on the square (i,j)} \\ 0 & \text{otherwise}\end{cases}$

 Chess Board

## Wednesday, August 28, 2024

### Circle Packing and HTML reporting

Little example. Here, we try to pack $$n$$ circles with a given radius $$r_i$$ into a larger disc with an unknown radius $$R$$. The goal is to minimize $$R$$. The underlying model is simple:

Packing of Circles
\begin{align} \min\> & \color{darkred}R \\ & \sum_c \left(\color{darkred}p_{i,c}-\color{darkred}p_{j,c}\right)^2 \ge \left(\color{darkblue}r_i+\color{darkblue}r_j\right)^2 & \forall i\lt j \\ & \sum_c \color{darkred}p_{i,c}^2 \le \left(\color{darkred}R-\color{darkblue}r_i\right)^2 & \forall i \\ & \color{darkred}R \ge 0\\ & c \in \{x,y\} \\ \end{align}

## Monday, August 12, 2024

### Revised Simplex LP Solver written in GAMS

I am teaching some GAMS classes, and a question arose: "How does the Simplex method work?" It's not easy to answer in a few sentences, but I want to touch upon the concept of a basis anyway. Once you have a good intuition of what a basis is, a simple Simplex method is not so far-fetched. I find the tableau presentation somewhat confusing and far removed from what actual Simplex solvers do. I strongly prefer the Revised Simplex Method in matrix notation.

Minor rant: I just don't understand the appeal of the tableau method. It looks to me like an invention for torturing undergrad students. Most of all, it is not very structure-revealing; it does not help you understand the underlying concepts. But about 100% of the LP textbooks insist we should learn that first.

As a gimmick, I implemented a simplified version in the GAMS language. This reminds me that someone spent the effort writing a Basic interpreter in TeX [1]. This is probably just as useful.

## Monday, July 15, 2024

### Practical Large-Scale Modeling: Sparsity

Presentation at USDA-ERS Model Summit 2024.

## Sunday, June 30, 2024

### Inflation is a difficult concept for many

Last friday, 6/28, new PCE (Personal Consumption Expenditures Price Index) data were released. The year-on-year inflation numbers decreased from 2.7% last month to 2.6% [1]:

Let's see how the popular press reports this [2]:

## Wednesday, May 15, 2024

### Another very small but very difficult global NLP model

The goal of this exercise is to fill a square area $$[0,250]\times[0,100]$$ with 25 circles. The model can choose the $$x$$ and $$y$$ coordinates of the center of each circle and the radius. So we have as variables $$\color{darkred}x_i$$, $$\color{darkred}y_i$$, and $$\color{darkred}r_i$$. The circles placed inside the area should not overlap. The objective is to maximize the total area covered.

A solution is:

## Thursday, May 9, 2024

### Modeling surprises

Here is an example where the PuLP modeling tool goes berserk.

In standard linear programming, only $$\ge$$, $$=$$ and $$\le$$ constraints are supported. Some tools also allow $$\ne$$, which for MIP models needs to be reformulated into a disjunctive constraint. Here is an attempt to do this in PuLP [1]. PuLP does not support this relational operator in its constraints, so we would expect a meaningful error message.

## Monday, May 6, 2024

### Rounding inside an optimization model

In [1], the question was asked: how can I round to two decimal places inside an optimization model? I.e., $\color{darkred}y_{i,j} = \mathbf{round}(\color{darkred}x_{i,j},2)$ To get this off my chest first: I have never encountered a situation like this. Rounding to two decimal places is more for reporting than something we want inside model equations. Given that, let me look into this modeling problem a bit more as an exercise.

## Monday, April 15, 2024

### LP in statistics: The Dantzig Selector

Lots of statistical procedures are based on an underlying optimization problem. Least squares regression and maximum likelihood estimation are two obvious examples. In a few cases, linear programming is used. Some examples are:

• Least absolute deviation (LAD) regression [1]
• Chebyshev regression [2]
• Quantile regression [3]
Here is another regression example that uses linear programming.

We want to estimate a sparse vector $$\color{darkred}\beta$$ from the linear model $\color{darblue}y=\color{darkblue}X\color{darkred}\beta+\color{darkred}e$ where the number of observations $$n$$ (rows in $$\color{darkblue}X$$) is (much) smaller than the number of coefficients $$p$$ to estimate (columns in $$\color{darkblue}X$$) [4]: $$p \gg n$$. This is an alternative to the well-known Lasso method [5].