Saturday, January 28, 2023

Tiny non-convex quadratic model brings solvers to their knees

Here is a very small geometric problem:

Given \(n\) points in 2d space, find the smallest triangle that contains all these points.


Find the smallest triangle containing all points.


This looks like a simple problem. Somewhat to my surprise, my attempt here does not bear that out.

Tuesday, January 24, 2023

Export GAMS GDX file to different Python formats (CSV,Feather,Pickle)

A GAMS GDX file is a binary file with a number of GAMS symbols with their data. When collaborating with colleagues that work with Python, it may be useful to convert a GAMS GDX with relevant data to data files that Python can consume. 

The idea is here that a GAMS user can run the GAMS script, without knowing Python or having Python installed. (GAMS comes with its own somewhat barebones Python, which is used inside the GAMS script). On the other hand, the Python user will not need to have GAMS installed to read the generated data files. This is opposed to Python packages and tools that can interact with GDX files directly. You can see a few in the PyPI directory [1]. Those will require both a GAMS system and a Python environment.

Wednesday, January 11, 2023

MIP Bounds

MIP (and related) solvers have a unique property: they provide a bound on the best possible integer solution at time \(t\). Together with the best-found integer solution so far, we have two bounds. Somewhere in between is the final optimal solution. The typical picture for these two bounds is as follows:

Typical shape


Monday, January 2, 2023

High Level MIP Modeling


Most LP/MIP modeling tools stay close to what is the underpinning of a Mixed-Integer Programming problem: a system of linear equations (equalities and inequalities) plus a linear objective. Examples are Pulp and GAMS. In Constraint Programming (CP), modeling tools need to provide access to higher-level global constraints. Without these global constraints (such as the famous all-different constraint), CP solvers would not perform very well. 

Tuesday, December 27, 2022

Not bad for a MIP...

Often I see people who have read or heard about NP-completeness dismissing a MIP formulation even before trying. This is certainly a misunderstanding of complexity theory. To be clear:

Complexity theory says (almost) nothing about how fast a particular MIP solver can solve your particular problem on your particular dataset.  

I think we can even drop the "almost." So, let's not fall into this trap, and just try things out!

In [1] a simple problem is stated:

Given \(n=40,000\) numbers, select a subset that sums up to 100,000 or as closely as possible.

A small MIP model can do the job:


MIP model
\[\begin{align}\min\>&\left|\mathit{\color{darkred}{Deviation}}\right| \\ & \sum_i \color{darkblue}v_i \cdot \color{darkred}x_i = \mathit{\color{darkblue}{Target}} + \mathit{\color{darkred}{Deviation}}\\ & \color{darkred}x_i \in \{0,1\}\end{align} \]

Monday, December 26, 2022

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


Saturday, December 17, 2022

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

Friday, December 2, 2022

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

Monday, November 28, 2022

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)

Tuesday, November 22, 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