Monday, May 16, 2022

Ranking using numpy.argsort

I needed to find a ranking of a large data set. Using Python, it makes sense to look at the numpy library for this. 

Numpy has the function argsort, which returns index positions [1]. One would think these are exactly the ranks we are after. Unfortunately, this is not the case.

>>> import numpy as np
>>> a = [3.0, 1.0, 5.0, 2.0]
>>> indx = np.argsort(a)
>>> indx
array([1, 3, 0, 2], dtype=int64)

I would expect:
     indx = [2, 0, 3, 1]

Actually, the reported indices are for a reversed mapping: from the (unknown) sorted vector to the original unsorted vector.

On the left is what I was after, and on the right is what argsort returns.

It is not very difficult to get the inverse mapping. Here are a few ways to do this:
  1. Using loops. Use the simple fact that for an index \(p\) and its inverse mapping \(p'\), we have: \[p_i=j \iff p'_j=i\]
    >>> rank = np.empty_like(indx)
    >>> for i,j in enumerate(indx):
    ...     rank[j]=i
    >>> rank
    array([2, 0, 3, 1], dtype=int64)
    Looping is in general quite slow in Python. So we may want to look into some alternatives.
  2. Fancy indexing[2]. Here we use the array indx to permute the values [0,1,2,3].
    >>> rank = np.empty_like(indx)
    >>> rank[indx] = np.arange(len(indx))
    >>> rank
    array([2, 0, 3, 1], dtype=int64)
  3. Applying argsort twice[2]. This is a bit of a surprise, but it does exactly what we want.
    >>> rank=np.argsort(indx)
    >>> rank
    array([2, 0, 3, 1], dtype=int64)
    This one is the most intriguing of course: argsort(argsort(a)) gives the ranking.

An alternative is to use scipy.stats.rankdata. The above ranking can be replicated with:

>>> import scipy.stats as stats
>>> rank = stats.rankdata(a,method='ordinal')-1
>>> rank
array([2, 0, 3, 1], dtype=int64)


Wednesday, May 4, 2022

Evil Sudoku

On[1] there is now an "evil" difficulty level. I found these very difficult to solve by hand (I usually give up).


Of course, a good MIP presolver/preprocessor devours these in no time. It should solve models like this in less than 0.1 seconds using zero Simplex iterations and zero B&B nodes.

Version identifier: | 2021-04-07 | 3a818710c
CPXPARAM_Advance                                 0
CPXPARAM_Threads                                 1
CPXPARAM_MIP_Display                             4
CPXPARAM_MIP_Pool_Capacity                       0
CPXPARAM_MIP_Tolerances_AbsMIPGap                0
Generic callback                                 0x50
Tried aggregator 2 times.
MIP Presolve eliminated 168 rows and 580 columns.
Aggregator did 28 substitutions.
Reduced MIP has 128 rows, 122 columns, and 501 nonzeros.
Reduced MIP has 122 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.06 sec. (0.93 ticks)
Found incumbent of value 0.000000 after 0.06 sec. (1.66 ticks)

Root node processing (before b&c):
  Real time             =    0.06 sec. (1.67 ticks)
Sequential b&c:
  Real time             =    0.00 sec. (0.00 ticks)
Total (root+branch&cut) =    0.06 sec. (1.67 ticks)

--- MIP status (101): integer optimal solution.
--- Cplex Time: 0.06sec (det. 1.67 ticks)

Proven optimal solution
MIP Solution:            0.000000    (0 iterations, 0 nodes)
Final Solve:             0.000000    (0 iterations)

Best possible:           0.000000
Absolute gap:            0.000000
Relative gap:            0.000000

CBC is a bit terser (not always the case):

COIN-OR CBC      38.2.1 96226ea8 Feb 19, 2022          WEI x86 64bit/MS Window

COIN-OR Branch and Cut (CBC Library 2.10)
written by J. Forrest

Calling CBC main solution routine...
No integer variables - nothing to do

Solved to optimality (within gap tolerances optca and optcr).
MIP solution:    0.000000e+00   (0 nodes, 0.019 seconds)

Best possible:   0.000000e+00
Absolute gap:    0.000000e+00   (absolute tolerance optca: 0)
Relative gap:    0.000000e+00   (relative tolerance optcr: 0.0001)



Appendix: GAMS model


Evil Sudoku from



'all areas (rows,columns,squares)' /r1*r9,c1*c9,s1*s9/
'rows' /r1*r9/
'columns' /c1*c9/
'squares' /s1*s9/
'areas with unique values a=area name, (i,j) are the cells'
'values' /1*9/;

* populate u(a,i,j)
u(i,i,j) =
u(j,i,j) =
ord(s)=3*ceil(ord(i)/3)+ceil(ord(j)/3)-3) = yes;
display u;

* given values
table v0(i,j)
c1 c2 c3 c4 c5 c6 c7 c8 c9
r1                 9     5
r2  7                    1
r3        8  2        7     9
r4  6              4  9     8
r5     4     1
r6                          5
r7        2     3
r8  8              1  6     4
r9                       7

* MIP model
binary variable x(i,j,k);
x.fx(i,j,k)$(v0(i,j)=k.val) = 1;
variable z 'dummy objective';

'one value per cell'

dummy.. z =e= 0;
sum(u(a,i,j), x(i,j,k)) =e= 1;
sum(k, x(i,j,k)) =e= 1;

model sudoku /all/;

* solve
solve sudoku minimizing z using mip;

* display solution
parameter v(i,j) 'solution';
v(i,j) =
sum(k, k.val*x.l(i,j,k));
option v:0;
display v;

Most models have separate constraints for rows, columns, and squares. In this formulation, I generalize this to "areas". The multidimensional set \(u(a,i,j)\) contains for each area \(a\) the corresponding cells \((i,j)\).  You can display this set to view it. Once we have this set \(u\) properly populated, the uniqueness constraints become exceedingly simple. The idea is that constraints are more difficult to debug than sets/parameters. So I am inclined to spend more effort in creating somewhat complex sets, expecting some pay-off in constraints becoming so simple that few things can go wrong.

u(a,i,j) for different values of a

As usual, we have \[\color{darkred}x_{i,j,k} = \begin{cases} 1 &  \text{if cell $(i,j)$ has value $k$} \\ 0 & \text{otherwise}\end{cases}\] To recover the Sudoku solution, we form \[ \color{darkblue}v_{i,j} = \sum_k \color{darkblue}k\cdot \color{darkred}x^*_{i,j,k}\] 

The final solution is:

----     73 PARAMETER v  solution

            c1          c2          c3          c4          c5          c6          c7          c8          c9

r1           3           2           4           7           1           9           8           5           6
r2           7           5           9           8           6           3           4           1           2
r3           1           6           8           2           4           5           7           3           9
r4           6           7           1           3           5           4           9           2           8
r5           9           4           5           1           8           2           3           6           7
r6           2           8           3           9           7           6           1           4           5
r7           4           9           2           6           3           7           5           8           1
r8           8           3           7           5           2           1           6           9           4
r9           5           1           6           4           9           8           2           7           3

Sunday, May 1, 2022

Getting rid of non-linearities

In [1], an attempt was made to implement the following non-linear constraint: \[\frac{\displaystyle\sum_t \max\left\{\sum_i CF_{i,t}\cdot q_i -L_t, 0 \right\}}{\displaystyle\sum_t L_t} \le 0.015 \] Obviously code like:

cfm = quicksum( max(quicksum(cf[i][t] * q[i] - L[t] for i in range(I)), 0) for t in range(T) /  quicksum(L[t] for t in range(T)) <= 0.015

is really not what we want to see. It is best, not to directly start up your editor and write Python code like this. Rather, get a piece of paper, and focus on the math.

There are two non-linearities: a division and a \(\max()\) function. Note that I am not sure which symbols are variables or parameters.  I'll try to explain some possible cases below.


Exogenous divisions of the form \[\frac{\color{darkred}x}{\color{darkblue}a}\] where \(\color{darkblue}a\) is a constant, are not an issue. This is just really a linear coefficient \(1/\color{darkblue}a\). If you have \[\frac{\color{darkred}x}{\sum_i \color{darkblue}a_i}\] in the constraints, I would advice to calculate \[\color{darkblue}\alpha :=\sum_i \color{darkblue}a_i \] in advance, so we can simplify things to \[\frac{\color{darkred}x}{\color{darkblue}\alpha}\] It is a good habit to keep constraints as simple as possible, as they are more difficult to debug than parameter assignments.

If we have something like \[\frac{\color{darkred}x}{\color{darkred}y}\] (endogenous division) we need to be careful and worry about division by zero (or, more generally, that the expression can assume very large values if \(\color{darkred}y \approx 0\)). If \(\color{darkred}y\) is a positive variable, we can protect things a bit by using a lower bound, say \(\color{darkred}y\ge 0.0001\). This is difficult to do if \(\color{darkred}y\) is a free variable (we want a hole in the middle). If we have  \[\frac{\color{darkred}x}{\sum_i\color{darkred}y_i}\] it may be better to write this as: \[\begin{align}&\frac{\color{darkred}x}{\color{darkred}z}\\ & \color{darkred}z= \sum_i \color{darkred}y_i  \\ &\color{darkred}z\ge 0.0001  \end{align}\] at the expense of an extra variable and constraint. It has the additional advantage of making the model less non-linear (fewer non-linear variables, smaller non-linear part of the Jacobian). Note that we assumed here that \(\sum_i\color{darkred}y_i \ge 0\). If this expression can assume both negative and positive values, this will not not work.

If the division is not embedded in other non-linear expressions, we often can multiply things out. E.g. if we have the constraint:  \[\frac{\color{darkred}x}{\sum_i\color{darkred}y_i} \le 0.015\] then we can write: \[\color{darkred}x \le  0.015 \cdot \sum_i\color{darkred}y_i\] This is now linear. This is what can apply to our original constraint:\[\sum_t \max\left\{\sum_i CF_{i,t}\cdot q_i -L_t, 0 \right\} \le 0.015\cdot \sum_t L_t \]

Max function

We can feed \(\max\{\color{darkred}x,0\}\) to a general-purpose NLP solver. However, this is dangerous. Although this function is continuous, it is non-differentiable at \(\color{darkred}=0\).

In the special case \[\max\{\color{darkred}x,0\} \le \color{darkred}y\] we can write: \[\begin{align}  \color{darkred}x &\le \color{darkred}y \\ 0 & \le \color{darkred}y\end{align} \] If \(\color{darkred}y\) represents an expression, you may want to use an extra variable to prevent duplication.  

If we have \[\sum_i \max\{\color{darkred}x_i,0\} \le \color{darkred}y\] we can do: \[\begin{align} & \color{darkred}z_i \ge 0 \\ & \color{darkred}z_i \ge \color{darkred}x_i \\ &\sum_i \color{darkred}z_i \le \color{darkred}y \end{align}\] Note that the variables \(\color{darkred}z_i\) are a bit difficult to interpret. They can be larger than \(\max\{\color{darkred}x_i,0\}\) if the inequality is not tight. The reason I use \(\color{darkred}z_i \ge \max\{\color{darkred}x_i,0\}\) is that it is sufficient for our purpose and that \(\color{darkred}z_i = \max\{\color{darkred}x_i,0\}\) is just way more difficult to represent.

This is the reformulation we can apply to our original problem: \[\begin{align}&z_t \ge \sum_i CF_{i,t}\cdot q_i -L_t \\ & z_t \ge 0 \\ & \sum_t z_t \le 0.015\cdot \sum_t L_t  \end{align}\] This is now completely linear: we have removed the division and the \(\max(.,0)\) function.


Thursday, April 28, 2022

Inverting a large, dense matrix

In this post I show some experiences with inverting a large, dense matrix. The variability in performance was a bit surprising to me. 


I have available in a GAMS GDX file a large matrix \(A\). This is an input-output matrix. The goal is to find the so-called Leontief inverse \[(I-A)^{-1}\] and return this in a GAMS GDX for subsequent use [1]. It is well-known that instead of calculating the inverse it is better to form an LU factorization of \(I-A\) and then use that for different rhs vectors \(b\) (essentially a pair of easy triangular solves). [2] However, economists are very much used to having access to an explicit inverse.

A GAMS representation of the problem can look like:

'regions' /r1*r2/
'products' /p1*p3/

rp(r,p) =

table A(r,p,r,p)

r1.p1  r1.p2  r1.p3  r2.p1  r2.p2  r2.p3
r1.p1    0.8    0.1
r1.p2    0.1    0.8    0.1
r1.p3           0.1    0.8    0.1
r2.p1                  0.1    0.8    0.1
r2.p2                                0.8    0.2
r2.p3                  0.1    0.1    0.1    0.7


'Identity matrix'
I(rp,rp) = 1;
IA(rp,rp2) = I(rp,rp2) - A(rp,rp2);
option I:1:2:2,IA:1:2:2;
display I,IA;

* inverse in GAMS

'inv(I-A) calculated by a CNS model'

equation LinEq(r,p,r,p)   'IA*invIA=I';

sum(rp3, IA(rp,rp3)*invIA(rp3,rp2)) =e= I(rp,rp2);

model Linear /linEq/;
solve linear using cns;

option invIA:3:2:2;
display invIA.l;

* accuracy check.
* same test as in tool
scalar err 'max error in | (I-A)*inv(I-A) - I |';
err =
smax((rp,rp2),abs(sum(rp3, IA(rp,rp3)*invIA.l(rp3,rp2)) - I(rp,rp2)));
display err;

The problem at hand has a 4-dimensional matrix \(A\) (with both regions and sectors as rows and columns). Of course, the real problem is very large. Because of this, a pure GAMS model is not really feasible. In our real data set we have 306 regions and 63 sectors, which gives us a \(19,278 \times 19,278\) matrix. The above model would have a variable and a constraint for each element in this matrix. We would face a model with 371 million variables and constraints. Below, we try to calculate the inverse using a standalone C++ program that reads a GDX file with the \(A\) matrix (and underlying sets for regions and sectors) and writes a new GDX file with the Leontief inverse. 

Attempt 1: Microsoft Visual C++ with the Eigen library.

Here I use the Micosoft Visual C++ compiler, with the Eigen [3] library. Eigen is a C++ template library. It is very easy to use (it is a header only library). And it provides some interesting features:
  • It contains quite a few linear algebra algorithms, including LU factorization, solving, and inverting matrices.
  • It allows to write easy-to-read matrix expressions. E.g. to check if things are ok, I added a simple-minded accuracy check: \[\max | (I-A)^{-1} \cdot (I-A) - I | \]  should be small. Here \(|.|\) indicates elementwise absolute values. This can be written as:
       double maxvalue = (INV * IA - MatrixXd::Identity(matrixSize, matrixSize)).array().abs().maxCoeff();
  • Support for parallel computing using OpenMP [4]. MSVC++ also supports this.

The results are:

  • By default OMP (and Eigen) uses 16 threads. This machine has 8 cores and 16 hardware threads.
  • Reading the input GDX file is quite fast: 1.3 seconds. (Note: this is read in "raw" mode for performance reasons). There is also some hashing going on.
  • The nonzero count of \(I-A\) is 4.9 million. The inverse will be dense, so \(19278^2=372\) million elements. We use here dense storage schemes and dense algorithms.
  • Instead of calling inverse(), I split the calculation explicitly into two parts: LU decomposition and solve. The time to perform the LU factorization looks reasonable to me, but the solve time is rather large. 
  • We can write the GDX file a bit faster by using compression. The writing time goes down from 29.4 to 14.8 seconds.

Why is the solve so slow? The following pictures may show the reason:

CPU usage during LU decomposition

CPU usage during solve

Basically, during the solve phase, we only keep about 2 cores at work. I would expect that multiple rhs vectors (and a lot of them!) would give more opportunity for parallelization. I have seen remarks that this operation is memory bound, so adding more threads does not really help.

Attempt 2: Intel/Clang with the MKL library.

Here I changed my toolset to Intel's Clang compiler icx, and its optimized MKL library. The Clang compiler is part of the LLVM project, and is known for excellent code generation. The MKL library is a highly optimized and tuned version of the well-known LAPACK and BLAS libraries. It is possible to use MKL as a back-end for Eigen, but here I just coded against MKL directly (I just have one LU decomposition, an invert, and a matrix-multiplication in the check). So how does this look like?

CPU Usage during solve

This looks much better. 

  • MKL only uses 8 threads by default: the number of physical cores.
  • Both the LU decomposition, but especially the solve part is much faster.
  • Here we used compression when writing the GDX file.
  • I used Row Major Order memory layout (i.e. C style row-wise storage).
  • MKL is a bit more low-level. Basically, we use BLAS[6] and LAPACK[7].


Intel/Clang/MKL can be much faster than MSVC/Eigen on some linear algebra operations. The total time to invert this matrix went from > 1000 seconds to  < 100 seconds:

Inverting a 19278x19278 matrix
LibraryLU factorizationSolve
MSVC++/Eigen49 seconds1047 seconds
Intel/Clang/MKL24 seconds68 seconds



Saturday, April 16, 2022

Expanding Visual Studio in the Task Manager


This is scary. Note that is in an idle state (nothing compiling, running, or debugging at the moment). Soon we all need 128 GB of RAM.

Thursday, April 14, 2022

GAMS: Undocumented PUT formats

The GAMS documentation mentions (standard notation) and (scientific notation) for formatting numeric items using the PUT statement. There are however a few more. Here we print values using different formats:
         1.20     1.20E+00 1.2000000000          1.2
         1.23     1.23E+00 1.2345000000       1.2345
 123450000.00     1.23E+08 123450000.00    123450000
         0.00     1.20E-07 0.0000001200       1.2E-7
         0.00     1.23E-07 0.0000001235    1.2345E-7

It looks like formats 3 and 4 are inspired by SAS PUT formats f12.10 and best12.10.


  1. Dictionary of formats,

Appendix: GAMS code

'values'   /i1*i5/
'formats'  /''*''/

parameter p(i) 'test values' /
i1  1.2
i2  1.2345
i3  1.2345e8
i4  1.2e-7
i5  1.2345e-7

* write all values in all formats

file f /put.txt/;
* right align text
f.lj = 1;
put f;
* write headers
put /;
* write values
put ' ':0;
put p(i);
put /;

Sunday, April 10, 2022

Rewriting old GAMS code

It is always a good idea to revisit existing GAMS code and see if we can improve it. Here is an example of an actual model.

The problem is that we want to set up a mapping set between two sets based on the first two characters. If they are the same, the pair should be added to the mapping. The old code looked like:

'regions' /
AP   'Appalachia'
CB   'Corn Belt'
LA   'Lake States'
'subregions' /
'mapping regions<->subregions'

* old code:
LOOP(R,  value('1',R) = 100*ord(,1) + ord(,2); );
LOOP(S,  value('2',S) = 100*ord(,1) + ord(,2); );
'1',R) = value('2',S)) = YES;

display value;
display rs;


To verify this indeed generates the correct result for set rs, we look at the output:

----     27 PARAMETER value  

           AP          CB          LA     APN0501     APN0502     APN0504     CBL0704     CBM0404     LAM0404

1    6580.000    6766.000    7665.000
2                                        6580.000    6580.000    6580.000    6766.000    6766.000    7665.000

+     LAM0406

2    7665.000

----     28 SET rs  mapping regions<->subregions

       APN0501     APN0502     APN0504     CBL0704     CBM0404     LAM0404     LAM0406

AP         YES         YES         YES
CB                                             YES         YES
LA                                                                     YES         YES

The set rs is obviously correctly populated. The auxiliary parameter value contains the ASCII values: e.g. AP has value 6580 as the decimal ASCII codes for A and P are 65 and 80.

  • The function ord(string, pos) returns the ASCII value of the character at position pos of the string.
  • The suffix .TL is the text string of the set element (internally GAMS does not work with the strings but rather an integer id for each set element; here we make it explicit we want the string).
  • The loops are not really needed. We could have used:
    value('1',R) = 100*ord(,1) + ord(,2);
    value('2',S) = 100*ord(,1) + ord(,2);
  • The mapping set is a very powerful concept in GAMS. It is somewhat like a dict in Python, except it is not one way. It can map from r to s but also from s to r.

We can simplify the code to just:

* new code:
* compare first two characters in r and s
rs(r,s) =
ord(,1)=ord(,1) and ord(,2)=ord(,2);
display rs;

This gives the same result:

----     22 SET rs  mapping regions<->subregions

       APN0501     APN0502     APN0504     CBL0704     CBM0404     LAM0404     LAM0406

AP         YES         YES         YES
CB                                             YES         YES
LA                                                                     YES         YES

  • No need for the auxiliary parameter value.
  • No loops.
  • We could add a check that we have no unmapped subregions. E.g. by:
    abort$(card(rs)<>card(s)) "There are unmapped subregions";
  • This will also catch cases where the casing does not match.
  • Critical note: GAMS has very poor support for strings. This should have been rectified a long time ago. There is no excuse for this deficiency. 


It is always worthwhile to revisit existing models and clean them up. During development, especially when under time pressure, we often are happy once our code works. As the lifetime of models can be surprisingly long, and thus new generations of users and modelers start working with old models, it is a good idea to do a cleanup round to make the code as readable as possible.  

Saturday, March 5, 2022

Bostock's command-line cartography tutorial under Windows

In [1], an excellent tutorial is presented about the process of making maps. It is a little bit dated, so here I develop some Windows-based scripts that make it possible to follow these tutorials. The goal is two-fold:

  1. Make things work for Windows. I am comfortable with the Unix command line, but, by far, most of my colleagues are not. To allow for easier sharing, I used Windows CMD.
  2. Update the commands so they all function again. Some URLs have changed a little bit, and we need to use a specific version of d3. If you want to use the original Unix commands, and you encounter some issues, you may want to check how I repaired them. 

The output format of these scripts is svg. SVG files are plain text, represent vectors (instead of bitmaps), and can be read directly by a standard web browser.


Part 1

The first thing to do is to install node.js if you don't have this available already. Using [2] this process is quite straightforward. Our first batch file will follow the steps in [1].

::   Mike Bostock
::   Command-Line Cartography, Part 1
::   A tour of d3-geo’s new command-line interface.
::   Needs node.js. Install from:
::   we translate UNIX command line to Windows CMD

:: download shape file from Census Bureau (region 06 = California)
:: curl '' -o
:: use https instead, curl is part of windows
curl -O 

:: unzip -o
:: use tar instead (part of windows)
tar -xf

:: install node.js package
:: and extract geojson
call npm install -g shapefile
call shp2json cb_2014_06_tract_500k.shp -o ca.json

:: perform projection 
call npm install -g d3-geo-projection
call geoproject "d3.geoConicEqualArea().parallels([34, 40.5]).rotate([120, 0]).fitSize([960, 960], d)" < ca.json > ca-albers.json

:: create svg
call geo2svg -w 960 -h 960 < ca-albers.json > ca-albers.svg

:: launch browser
start ca-albers.svg


  • The curl command is available on newer versions of Windows.
  • Windows does not have unzip, but it has tar which can unzip files.
  • Use https instead of HTTP.
  • The use of quotes is different under Windows compared to Unix. 

The result should be the following vector image displayed in your browser:

Friday, February 18, 2022

Wanted: better error messages

In [1] a user tries the following constraint:
mdl.addConstrs((t[i,k] * X[i,j,k] - te1[i] <= 5) >> (z1[i,k] == 1) for i,j,k in arcos if i != 0 and i != 23)
(t and X and variables). This is not accepted, and the following error message is issued:

AttributeError: 'gurobipy.QuadExpr' object has no attribute 'getVar'

This is a terrible error message. It does not describe the real, underlying problem, and it does not tell the user what to do next. Developers typically do not pay much attention to error messages. Often they seem more aimed to make life easy for the developer than providing assistance to an already confused user. In this case, I believe the modeling tool did not even issue an error message, but rather made assumptions without checking, and left it to the Python run-time system to complain. 

This constraint has two problems: 
  • Indicator constraints have a simple binary variable as condition, not a general (boolean) expression
  • Only linear constraints are supported in indicator constraints

Maybe a better message is:

Indicator constraints have the form:

        binary variable == 0 ==> linear constraint


        binary variable == 1 ==> linear constraint 

Your constraint does not have this form. You need to reformulate it to fit this format, or use a different (big-M) formulation.

Well-formed and meaningful error messages are very important. The user is already confused, otherwise (s)he would formulate a correct constraint. Adding confusing error messages to this confusion is not a good idea. A good error message could have prevented this post. We can think of error messages as the UI (User Interface) when it really matters: when the user needs help. Developers should pay much more attention to this.

A question for another day is of course: why are only linear constraints supported?


  1. AttributeError: 'gurobipy.QuadExpr' object has no attribute 'getVar',