Yet Another Math Programming Consultant
I am a full-time consultant and provide services related to the design, implementation and deployment of mathematical programming, optimization and data-science applications. I also teach courses and workshops. Usually I cannot blog about projects I am doing, but there are many technical notes I'd like to share. Not in the least so I have an easy way to search and find them again myself. You can reach me at erwin@amsterdamoptimization.com.
Saturday, March 25, 2023
Simultaneous equation models and data errors
Thursday, March 16, 2023
Algorithm vs. model
From [1]:
We are given a plane defined by Ax+By+Cz-D = 0 where D is significantly larger than A,B,C and GCD(A,B,C) = 1. How would I find all points (x, y, z), where x,y,z are integers and >= 0, that lie on the plane in an efficient manner?
So the poster asks for an algorithm to find \(\color{darkred}x,\color{darkred}y,\color{darkred}z \in \{0,1,2,\dots\}\) such that \[\color{darkblue}A \cdot \color{darkred}x + \color{darkblue}B \cdot \color{darkred}y + \color{darkblue}C \cdot \color{darkred}z = \color{darkblue}D\] Besides the assumptions stated in the question, I'll further assume \(\color{darkblue}A,\color{darkblue}B,\color{darkblue}C,\color{darkblue}D\gt 0\).
Tuesday, March 14, 2023
Choosing between NLP solvers: interior point or active set.
One way to categorize (local) nonlinear programming (NLP) solvers is active set methods and interior point solvers. Some representative large-scale sparse solvers are:
- Active set: CONOPT, SNOPT. These are using SQP algorithms.
- Interior point: IPOPT, Knitro. Note: Knitro also contains an active set algorithm.
Monday, March 6, 2023
Some approaches for moving data between MS Access and GAMS
Moving data between different environments is always more difficult than we hope. Here I list some approaches and actually try them out on a small dataset. We hit some bugs along the way and also a few conceptual stumbling blocks (even for this stylized example). We had some issues with Access as well as GAMS Connect.
This question came up in an actual project. My idea was: "Let me show you how this can be done". I am afraid, I got carried away a bit. But it demonstrates that we should not underestimate these, at first sight, menial tasks. When the data set becomes larger, the problems compound. We can't eyeball the data, and statistically, it is more likely we encounter some problems.
Friday, February 24, 2023
Another fast MIP model: covering
In [1], the following problem is stated:
- There is a collection of \(n=1,000\) test questions.
- Each question covers a number of skills.
- Given is a requirement for a number of questions for each required skill (e.g., 4 questions about skill 1, 3 questions about skill 2, etc.).
- Create a test with the minimum number of questions that fulfills the requirements.
Thursday, February 16, 2023
Assigning jobs to machines without overlap
Here we consider the following problem from [1]:
- We have jobs with a given start time and completion time
- Jobs can be repeated on given days (e.g. job 1 needs to run on Monday, Wednesday, and Friday)
- We want to assign jobs to machines in such a way that there is no overlap
- The objective is to minimize the number of machines needed to execute all jobs
Wednesday, February 15, 2023
Supplier selection: an easy MIP
- We want to order items in different quantities from suppliers.
- Suppliers have an available inventory for these items. This can be zero.
- We can split the ordering over different suppliers.
- The cost structure is as follows:
- Shipping cost is a fixed cost per supplier.
- Item cost is a variable per-unit cost.
Monday, February 13, 2023
Populating SQLite databases
GAMS has three easy ways to populate a SQLite database:
- Using the tool gdx2sqlite. This tool populates a SQLite database with data from a GDX file. This means we first have to export GAMS data to a GDX file. As there is quite some file I/O going on here (writing GDX file, reading GDX file, writing database), I would expect this to be slower than the next method.
- The new GAMS-connect facility. This does not use intermediate files, and directly copies records from in-memory data. This should be the fastest.
- Old fashioned CSV files. We first export data as a GDX file, and then use gdxdump to convert the data to a CSV file. Then sqlite can import the CSV file, and populate the database. There is much file I/O here, so this should be slow.
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.