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.

Of course, we see some remarks about NP-Hardness. Complexity theory is about bounds, about worst-case and asymptotic behavior. Even if we can't prove that a particular problem with a particular dataset given to a particular solver must be fast, it does not mean the opposite: that it must be slow. It is not at all unusual that we can solve things very quickly, even though the complexity bounds are terrible. Of course, this depends on the model, on the data set, and on the solver. Here, we see an open-source MIP solver can solve this particular problem in less than 0.01 seconds. Many well-educated people misunderstand complexity theory – to their detriment. They miss out on great ways to solve actual problems! Obviously, this is a problem with how complexity theory is taught. 

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

The planning horizon is a week, and the problems has 50 jobs.

Supplier selection: an easy MIP

This is a fairly standard supplier selection model. It was posted in [1]. It is interesting as it is a good fit for a MIP model: it is simple to model, it solves fast, and it is not obvious how to solve without an optimization model.

The problem is:

• 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. 

Populating SQLite databases

 GAMS has three easy ways to populate a SQLite database:

1. 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.
2. The new GAMS-connect facility. This does not use intermediate files, and directly copies records from in-memory data. This should be the fastest.
3. 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.