Maximum number of points with minimum distance

In [1] the following problem is posted:

Consider \(N\) points and a minimum distance \(\mathit{\color{darkblue}{MinDist}}\). Pick as many points as possible from this collection, such that the distances between the selected points is at least \(\mathit{\color{darkblue}{MinDist}}\).

A small data set can look like:

----      9 PARAMETER p  coordinates of points

              x           y

i1       17.175      84.327
i2       55.038      30.114
i3       29.221      22.405
i4       34.983      85.627
i5        6.711      50.021
i6       99.812      57.873
i7       99.113      76.225
i8       13.069      63.972
i9       15.952      25.008
i10      66.893      43.536
i11      35.970      35.144
i12      13.149      15.010
i13      58.911      83.089
i14      23.082      66.573
i15      77.586      30.366
i16      11.049      50.238
i17      16.017      87.246
i18      26.511      28.581
i19      59.396      72.272
i20      62.825      46.380
i21      41.331      11.770
i22      31.421       4.655
i23      33.855      18.210
i24      64.573      56.075
i25      76.996      29.781
i26      66.111      75.582
i27      62.745      28.386
i28       8.642      10.251
i29      64.125      54.531
i30       3.152      79.236
i31       7.277      17.566
i32      52.563      75.021
i33      17.812       3.414
i34      58.513      62.123
i35      38.936      35.871
i36      24.303      24.642
i37      13.050      93.345
i38      37.994      78.340
i39      30.003      12.548
i40      74.887       6.923
i41      20.202       0.507
i42      26.961      49.985
i43      15.129      17.417
i44      33.064      31.691
i45      32.209      96.398
i46      99.360      36.990
i47      37.289      77.198
i48      39.668      91.310
i49      11.958      73.548
i50       5.542      57.630

Comparing matrix balancing objectives

The matrix balancing problem can be described as [1]: find a non-negative matrix \(\color{darkred}A_{i,j}\), that is as close as possible to \(\color{darkblue}A^0_{i,j}\), while observing given row and column totals and a given sparsity pattern. Or, mathematically,

Matrix Balancing Problem
\[\begin{align}\min_{\color{darkred}A}\>&{\bf{dist}}(\color{darkred}A,\color{darkblue}A^0)\\ & \sum_i \color{darkred}A_{i,j} = \color{darkblue}c_j && \forall j\\ & \sum_j \color{darkred}A_{i,j} = \color{darkblue}r_i && \forall i \\&\color{darkred}A_{i,j}=0 &&\forall i,j|\color{darkblue}A^0_{i,j}=0\\ &\color{darkred}A_{i,j}\ge 0 \end{align} \]

Networks not always need an extra source and sink node

Convert standard assignment problem to a network problem

A standard assignment problem formulated as an LP/MIP looks like:

 

Assignment problem
\[\begin{align}\min&\sum_{i,j} \color{darkblue}c_{i,j}\cdot\color{darkred}x_{i,j}\\ & \sum_j \color{darkred}x_{i,j}=1 && \forall i \\ & \sum_i \color{darkred}x_{i,j}=1 && \forall j \\ & \color{darkred}x_{i,j} \in \{0,1\} \end{align}\]

Cuckoo search is a bit cuckoo

Excuses for the lame title.

This could be the start of a very extended series of papers.

References

1. Christian L. Camacho-Villalón, Marco Dorigo, Thomas Stützle, An analysis of why cuckoo search does not bring any novel ideas to optimization, Computers & Operations Research, Volume 142, 2022, https://www.sciencedirect.com/science/article/pii/S0305054822000442.
2. Aranha, C., Camacho Villalón, C.L., Campelo, F. et al. Metaphor-based metaheuristics, a call for action: the elephant in the room. Swarm Intell 16, 1–6 (2022)

A strange series

In [1] a question is posed about a somewhat strange series. Let \(i \in \{ 0,\dots,n\}\). Then we require:

• \(\color{darkred}x_i \in \{0,1,2,\dots\}\),
• \(\color{darkred}x_i\) is equal to the number of times the value \(i\) occurs in the series. In mathematical terms, one could say: \[\color{darkred}x_i = |\{j:\color{darkred}x_j=i\}|\] (here \(|S|\) is the cardinality of the set \(S\)).

An example for \(n=4\) is: 

index  0 1 2 3 4 

value  2 1 2 0 0

sum of K largest

Consider a vector of variables \(\color{darkred}x_i\). We want to impose the constraint: \[\text{sum of $K$ largest $\color{darkred}x_i$}  \le 0.5\sum_i \color{darkred}x_i\] I.e. the sum of the largest \(K\) values are less than half of the total. Sometimes this is expressed mathematically as \[\sum_{i=1}^K \color{darkred}x_{[i]} \le 0.5\sum_i \color{darkred}x_i\] where \(\color{darkred}x_{[i]}\) is an ordered version of \(\color{darkred}x_i\) with \(\color{darkred}x_{[1]}\ge\color{darkred}x_{[2]} \ge \color{darkred}x_{[3]} \dots \). There are several formulations for this constraint, all of them interesting, I think.

Brian Kernighan talks about modeling languages

 

Nov 17, 2015 Professor Brian Kernighan presents on 'How to succeed in language design without really trying.' Brian Kernighan is Professor of Computer Science at Princeton University and Honorary Professor in the School of Computer Science at The University of Nottingham.

Basically, Kernighan says:

• GAMS is terrible (somewhat of a side note). This makes some sense: that opinion was probably the reason to develop AMPL in the first place (if he thought GAMS was terrific, why develop AMPL).
• Original declarative AMPL i.e. the part he worked on: good.
• Later procedural facilities in AMPL (he was not involved in that): bad. (IMHO practical modeling often needs some procedural support; this is one of the reasons why modeling tools embedded in Python are popular).

Micro-econometrics: discrete choice models

In this post, I want to discuss some statistical models from [1]. I'll implement these models in GAMS. First of all to emphasize these are all (nonlinear) optimization problems. Instead of using canned routines using a statistical package, this can help to get a better understanding of what is really going on. At least for me, not using a black-box routine, forces me to understand the underlying optimization models. Another application can be to have this part of a larger GAMS model. Some mathematical programming models just need some estimation code before the real model can be attacked. If the rest of the model is in GAMS, it may be a little bit easier to also use GAMS in the estimation tasks, instead of using a statistical package. This actually happens quite a lot. Finally, it may be easier to add constraints using a GAMS formulation compared to a canned routine in a statistical package.

In this case, the first argument was the reason for using GAMS. Reproducing results is for me a good tool to help me understand a dense text.  

Select points

In [1], the following problem is posted:

I have multiple sets of data points. For example, set 1 contains 5 data points, set 2 contains 1 data point, set 3 contains 10, etc. I need to select one data point from each set so that distances between these selected points is minimal. Any Python based functions to be used will be very helpful

This can be stated as an optimization problem. Writing down the model is a useful exercise, not only to solve it and get solutions but also to define the problem a bit more precisely than a typical "word problem". 

A super simple non-convex MIQP model is:

Non-convex MIQP Model
\[\begin{align}\min&\sum_{i,j|\color{darkblue}{\mathit{ok}}_{i,j}} \color{darkblue}{\mathit{dist}}_{i,j}\cdot\color{darkred}x_i \cdot\color{darkred}x_j \\ & \sum_{i|\color{darkblue}{\mathit{group}}_{i,g}} \color{darkred}x_i = 1 && \forall g\\ & \color{darkred}x_i \in \{0,1\} \end{align}\]

Some Matrix Balancing Experiments

This is about the matrix balancing problem.

We have three sets of data:

• A matrix with with entries \(\color{darkblue}A^0_{i,j}\ge 0\). 
• Row- and column-totals \(\color{darkblue}r_i\) and  \(\color{darkblue}c_j\).

The \(\color{darkblue}A^0\) matrix is collected from different sources than the row- and column-totals. So the matrix elements don't sum up to our totals. The problem is finding a nearby matrix \(\color{darkred}A\), so the row and column totals are obeyed. In addition, we want to preserve the sparsity pattern of  \(\color{darkblue}A^0\): zeros should stay zero. And also: we don't want to introduce negative numbers (preserve the signs). More formally:

Matrix Balancing Problem
\[\begin{align}\min\>&{\bf{dist}}(\color{darkred}A,\color{darkblue}A^0)\\ & \sum_i \color{darkred}A_{i,j} = \color{darkblue}c_j && \forall j\\ & \sum_j \color{darkred}A_{i,j} = \color{darkblue}r_i && \forall i \\&\color{darkred}A_{i,j}=0 &&\forall i,j|\color{darkblue}A^0_{i,j}=0\\ &\color{darkred}A_{i,j}\ge 0 \end{align} \]

Approximate the matrix subject to row- and column-sum constraints