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.