This book [1] on DEA models has an accompanying website with all the GAMS models [2].

Of course, I'll be doing some nitpicking on the GAMS code.

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.

This book [1] on DEA models has an accompanying website with all the GAMS models [2].

Of course, I'll be doing some nitpicking on the GAMS code.

When I deal with regional codes such as FIPS[1] and HUC[2], CSV file readers often mutilate my regions. Here is an example in **R**:

Data Envelopment Analysis (DEA) models are somewhat special. They typically consist of small LPs, of which a whole bunch have to be solved. The CCR formulation (after [1]), for the \(i\)-th DMU (Decision Making Unit), can be stated as [2]:

CCR LP Model |
---|

\[\begin{align} \max \>& \color{darkred}{\mathit{efficiency}}_i=\sum_{\mathit{outp}} \color{darkred}u_{{\mathit{outp}}} \cdot \color{darkblue}y_{i,{\mathit{outp}}} \\ & \sum_{\mathit{inp}} \color{darkred}v_{{\mathit{inp}}} \cdot \color{darkblue}x_{i,{\mathit{inp}}} = 1 \\ & \sum_{\mathit{outp}} \color{darkred}u_{{\mathit{outp}}} \cdot \color{darkblue}y_{j,{\mathit{outp}}} \le \color{darkred}v_{{\mathit{inp}}} \cdot \color{darkblue}x_{j,{\mathit{inp}}} && \forall j \\ & \color{darkred}u_{{\mathit{outp}}} \ge 0, \color{darkred}v_{{\mathit{inp}}} \ge 0 \end{align}\] |

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

Labels:
GAMS,
Minimum Spanning Tree,
Multiple Solution,
Visualization

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}\]

Labels:
cplex,
HTML,
Mixed-Integer Programming,
Solution Pool,
SVG

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}\] |

Labels:
GAMS,
HTML,
non-convex optimization,
Packing,
parallel jobs,
SVG,
Visualization

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.

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]:

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:

Subscribe to:
Posts (Atom)