Scheduling Team Meetings

This is a simple problem from [1]:

I'm rusty on constraint optimization and am looking for help in this particular

use case. There are individuals who are each member to several teams. This is a

fixed many-to-many relationship and is determined a-priori. There are 3 time

slots where the teams can be scheduled to conduct a business meeting, but if an

individual is a member of more than one team which are both meeting at a given

time slot, they'll only be able to attend one. The objective is to schedule the

teams into the time slots, minimizing the number of overlaps of individuals.

For beginners, it is often a good idea to split the task in two:

1. Formulate a mathematical model (on a piece of paper)
2. Implement the model in code

GAMS: SMAX and sparsity

This is a discussion about the SMAX function in GAMS and how it behaves for sparse data.

The data structure we were facing was something like:

set

i 'cases' /case1*case100000/

j 'attribute' /j1*j25/

k 'attribute' /k1*k25/

t 'type' /typ1*typ2/

;

parameter p(i,j,k,t) 'positive numbers';

* note: for each i we have only one (j,k)

Plotting NUTS-2 maps from GAMS

 NUTS-2 regions are statistical subnational regions (often provinces), mainly for the EU and UK [1]. 

NUTS hierarchy (from [1])

In [2] we can find mapping information in the form of Shapefiles[3] and related formats. I used the GeoJSON[4] format, and created a Python notebook script to extract a GAMS set from that file. The file is reproduced in the appendix below. The NUTS-2 codes form the set elements, and the name is stored as explanatory text. There is an option to generate Latin names instead of using the native alphabet. The Latin names are also inside the geojson file. E.g. we have: 

EL65  'Πελοπόννησος'

which is in the Greek alphabet. Using the Latin name, this would look like:

EL65  'Peloponnisos'

Linear Programming Nonsense?

1. Inventory balance constraints

I came accross this text [1]:

Inventory Balance Constraint

Math and ChatGPT

Performing symbolic math steps is often related to pattern recognition. In theory, ChatGPT could be doing a good job here. I wanted to find the inverse of \[f(x) = {\mathrm{sign}}(x) \log(1+|x|)\] This function is a form of a signed logarithmic scaling. So, let's see what ChatGPT is telling us:

Julia vs Python

I gave a talk to economists (i.e., not professional programmers) about a Julia project we were working on. Julia is famous for its speed. It uses LLVM [1] as back-end for its JIT (Just In Time) compilation. As seeing is believing, here is an example algorithm which is used to compare performance between different languages and tools. This example was chosen as it is small, easy to explain, and easy to program while still showing meaningful time differences.

We have a square \([-1,+1]\times[-1,+1]\) and an inscribing circle with radius \(1\). See the dynamic figure below. Their areas are \(4\) and \(\pi\) respectively. The idea is to draw \(n\) points \[\begin{align}& x_i \sim U(-1,+1) \\ & y_i \sim U(-1,+1)\end{align}\]Let \(m\) be the number of points inside the circle, i.e. with \[x_i^2+y_i^2\lt 1\] Obviously, from the ratio of the areas, we have \[\frac{m}{n} \approx \frac{\pi}{4}\] It follows that an estimate of \(\pi\) is \[\hat{\pi}=4\frac{m}{n}\]

Simulation with n=1000

Critiquing a GAMS Model

It is always interesting to read GAMS models written by someone else. There are probably three things one can observe:

• A nice formulation or concept that is useful to learn about.
• A bad implementation: something that really should not be done that way.
• A piece of code that is correct and defensible, but I would write it differently. This includes things like style, layout, formatting, etc.

My way of reading GAMS code is often to start editing and make it "my code". It is a bit slower process, but that comes with its advantages: better understanding of what is going on, and often cleaner code.

Here, I am looking at the model sambal.gms in the GAMS model library [1]. It is a very small model, but I have many thoughts about it. The complete model is reproduced in Appendix 1. Let's walk through it.

The matrix balancing problem is to find a nearby matrix such that row- and column sums are obeyed. A relative quadratic objective is used to minimize the sum of the squared deviations between the original data (the priors) and the final matrix. Zeros in the matrix need to be maintained: they can't become nonzero. This is sometimes called sparsity preservation. Often, sign-preservation is another condition. That is not part of this model. Note that, in this model, not only the matrix is updated but also the row and column totals. 

Three-level Matrix Balancing

Matrix balancing: introduction

Matrix Balancing Models are often used in economic modeling exercises: they create consistent data sets from data originating from different, conflicting data sources. A standard example is updating a matrix subject to given row and column sums. An example can look like:

Update orange cells subject to row/column sums

The empty cells are zero, and they should remain zero. In other words, we need to preserve sparsity. Often, we have non-negativity restrictions on the values. The mathematical model can look like this:

Some TSP MTZ experiments

In [1], a question was posed about a TSP model using the MTZ (Miller-Tucker-Zemlin) subtour elimination constraints. The results with Julia/glpk were disappointing. With \(n=58\) cities, things were taken so long that the solver seemed to hang. Here I want to see how a precise formulation with a good MIP solver can do better. As seeing is believing, let's do some experiments. 

The standard MTZ formulation[1] can be derived easily. We use the binary variables \[\color{darkred}x_{i,j}=\begin{cases}1 & \text{if city $j$ is visited directly after going to city $i$}\\ 0 & \text{otherwise}\end{cases}\]  

Coloring edges of a grid

This is a little coloring problem from [1]:

Given an m * n grid, each edge must be colored. However, there are 2 constraints:

1. Entire grid must use only 3 unique colors
2. Each square in the grid must be colored using exactly 2 colors (2 edges per color)

Let's try to build a GAMS model for this. The question itself is not so interesting, but the modeling for setting up these grids is.