When do two intervals overlap?

For a scheduling tool I encountered the following problem. For a set of intervals generate a list of a pairs that overlap. For those pairs (A,B) I can generate a constraint (Note: we are smart and do not generate both x_A+x_B≤1 and x_B+x_A≤1) The test if two intervals A=[a₁,a₂], B=[b₁,b₂] overlap is:

or

depending on borderline cases (the last version is called the “strict” version in the following). Here is the demonstration:

Note that if the intervals are determined endogenously in the model, we often write “no-overlap” constraints for two intervals A=[a₁,a₂], B=[b₁,b₂] as:

I.e. B starts after A ends or A starts after B ends. Indeed, we can see that

which derives our second “strict” form of the overlap conditions.

Coin CBC command line

For a small project I was trying out the binary distribution of COIN-OR’s CBC. The good news, it can solve the problem quickly (provided I allow a  reasonable gap). I encountered a few issues:

1. The Windows executables are not built with parallel threading support.
2. The CSV writer is too simplistic. Names (with commas in them) are not properly quoted.

Threads option ignored

C:\projects\test>cbc model1a.lp ratio 0.05 threads 8 solve printing csv solution model1a.csv Welcome to the CBC MILP Solver Version: 2.8.8 Build Date: Dec 23 2013 Revision Number: 1998 command line - cbc model1a.lp ratio 0.05 threads 8 solve printing csv solution model1a.csv (default strategy 1) ratioGap was changed from 0 to 0.05 No match for threads - ? for list of commands No match for 8 - ? for list of commands Continuous objective value is 57.0769 - 0.02 seconds Cgl0002I 30 variables fixed Cgl0003I 0 fixed, 0 tightened bounds, 527 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 475 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 429 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 291 strengthened rows, 0 substitutions Cgl0003I 0 fixed, 0 tightened bounds, 69 strengthened rows, 0 substitutions Cgl0004I processed model has 743 rows, 499 columns (346 integer) and 2429 elements Cbc0038I Pass   1: suminf.    0.00000 (0) obj. 12146 iterations 431 Cbc0038I Solution found of 12146 Cbc0038I Before mini branch and bound, 316 integers at bound fixed and 140 continuous Cbc0038I Full problem 743 rows 499 columns, reduced to 247 rows 145 columns Cbc0038I Mini branch and bound improved solution from 12146 to 166 (0.50 seconds) 0  Obj 166 Dual inf 0.22137435 (11) End of values pass after 26 iterations 26  Obj 166 Dual inf 549.2981 (110) Perturbing problem by 0.001 % of 0.92934395 - largest nonzero change 1.9181672e-005 (% 0.0011298852) - largest zero chan ge 1.9246056e-005 120  Obj 166 Optimal - objective value 166 Cbc0038I Round again with cutoff of 164.5 Cbc0038I Pass   2: suminf.    7.33333 (22) obj. 164.5 iterations 163 Cbc0038I Pass   3: suminf.    6.22857 (20) obj. 164.5 iterations 71 Cbc0038I Pass   4: suminf.    5.33336 (18) obj. 164.5 iterations 34 Cbc0038I Pass   5: suminf.    4.10000 (14) obj. 164.5 iterations 28 Cbc0038I Pass   6: suminf.    0.00750 (3) obj. 164.5 iterations 166 Cbc0038I Solution found of 162 Cbc0038I Before mini branch and bound, 311 integers at bound fixed and 141 continuous Cbc0038I Full problem 743 rows 499 columns, reduced to 296 rows 158 columns Cbc0038I Mini branch and bound did not improve solution (0.74 seconds) Cbc0038I Round again with cutoff of 159.8 Cbc0038I Pass   7: suminf.    8.02667 (26) obj. 159.8 iterations 29 Cbc0038I Pass   8: suminf.    7.10546 (36) obj. 159.8 iterations 122 Cbc0038I Pass   9: suminf.    7.12365 (46) obj. 159.8 iterations 40 Cbc0038I Pass  10: suminf.   18.70686 (90) obj. 159.8 iterations 281 Cbc0038I Pass  11: suminf.    9.66191 (71) obj. 159.8 iterations 220 Cbc0038I Pass  12: suminf.    9.07849 (73) obj. 159.8 iterations 59 Cbc0038I Pass  13: suminf.    9.67900 (63) obj. 159.8 iterations 157 Cbc0038I Pass  14: suminf.    8.05376 (64) obj. 159.8 iterations 92 Cbc0038I Pass  15: suminf.    9.90251 (61) obj. 159.8 iterations 100 Cbc0038I Pass  16: suminf.    8.87667 (61) obj. 159.8 iterations 59 Cbc0038I Pass  17: suminf.   11.47273 (46) obj. 159.8 iterations 120 Cbc0038I Pass  18: suminf.   10.18668 (44) obj. 159.8 iterations 33 Cbc0038I Pass  19: suminf.    7.58501 (60) obj. 159.8 iterations 60 Cbc0038I Pass  20: suminf.    6.99899 (78) obj. 159.8 iterations 36 Cbc0038I Pass  21: suminf.    7.66668 (32) obj. 159.8 iterations 128 Cbc0038I Pass  22: suminf.    7.13455 (64) obj. 159.8 iterations 106 Cbc0038I Pass  23: suminf.    7.20358 (59) obj. 159.8 iterations 80 Cbc0038I Pass  24: suminf.    7.13455 (64) obj. 159.8 iterations 67 Cbc0038I Pass  25: suminf.    8.20892 (48) obj. 159.8 iterations 257 Cbc0038I Pass  26: suminf.    7.32000 (30) obj. 159.8 iterations 124 Cbc0038I Pass  27: suminf.    9.03479 (27) obj. 159.8 iterations 92 Cbc0038I Pass  28: suminf.    7.34334 (33) obj. 159.8 iterations 59 Cbc0038I Pass  29: suminf.    7.32000 (30) obj. 159.8 iterations 53 Cbc0038I Pass  30: suminf.    7.32000 (30) obj. 159.8 iterations 31 Cbc0038I Pass  31: suminf.   16.85062 (65) obj. 159.8 iterations 288 Cbc0038I Pass  32: suminf.    5.71250 (21) obj. 159.8 iterations 277 Cbc0038I Pass  33: suminf.    5.00000 (15) obj. 159.8 iterations 69 Cbc0038I Pass  34: suminf.    5.00000 (15) obj. 159.8 iterations 72 Cbc0038I Pass  35: suminf.    5.00000 (15) obj. 159.8 iterations 136 Cbc0038I Pass  36: suminf.    9.86669 (43) obj. 159.8 iterations 256 Cbc0038I No solution found this major pass Cbc0038I Before mini branch and bound, 178 integers at bound fixed and 89 continuous Cbc0038I Full problem 743 rows 499 columns, reduced to 542 rows 307 columns - 15 fixed gives 331, 197 - ok now Cbc0038I Full problem 743 rows 499 columns, reduced to 328 rows 197 columns Cbc0038I Mini branch and bound did not improve solution (1.22 seconds) Cbc0038I After 1.23 seconds - Feasibility pump exiting with objective of 162 - took 0.92 seconds Cbc0012I Integer solution of 162 found by feasibility pump after 0 iterations and 0 nodes (1.24 seconds) Cbc0038I Full problem 743 rows 499 columns, reduced to 317 rows 154 columns Cbc0038I Full problem 743 rows 499 columns, reduced to 0 rows 0 columns Cbc0031I 19 added rows had average density of 171.78947 Cbc0013I At root node, 19 cuts changed objective from 151 to 154.55353 in 100 passes Cbc0014I Cut generator 0 (Probing) - 207 row cuts average 2.5 elements, 7 column cuts (7 active)  in 0.203 seconds - new frequency is 1 Cbc0014I Cut generator 1 (Gomory) - 1562 row cuts average 349.6 elements, 0 column cuts (0 active)  in 0.842 seconds - n ew frequency is 1 Cbc0014I Cut generator 2 (Knapsack) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.094 seconds - new frequency is -100 Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 0.037 seconds - new fr equency is -100 Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 0 row cuts average 0.0 elements, 0 column cuts (0 active)  in 1.313 s econds - new frequency is -100 Cbc0014I Cut generator 6 (TwoMirCuts) - 191 row cuts average 191.0 elements, 0 column cuts (0 active)  in 0.253 seconds - new frequency is 1 Cbc0011I Exiting as integer gap of 7.4464682 less than 1e-010 or 5% Cbc0001I Search completed - best objective 162, took 17263 iterations and 0 nodes (6.98 seconds) Cbc0035I Maximum depth 0, 42 variables fixed on reduced cost Cuts at root node changed objective from 151 to 154.554 Probing was tried 100 times and created 214 cuts of which 0 were active after adding rounds of cuts (0.203 seconds) Gomory was tried 100 times and created 1562 cuts of which 0 were active after adding rounds of cuts (0.842 seconds) Knapsack was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.094 seconds) Clique was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.037 seconds) MixedIntegerRounding2 was tried 100 times and created 0 cuts of which 0 were active after adding rounds of cuts (1.313 s econds) FlowCover was tried 1 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.000 seconds) TwoMirCuts was tried 100 times and created 191 cuts of which 0 were active after adding rounds of cuts (0.253 seconds) Result - Optimal solution found (within gap tolerance) Objective value:                162.00000000 Lower bound:                    154.554 Gap:                            0.05 Enumerated nodes:               0 Total iterations:               17263 Time (CPU seconds):             7.05 Time (Wallclock seconds):       7.05 Option for printingOptions changed from normal to csv Total time (CPU seconds):       7.08   (Wallclock seconds):       7.08 C:\projects\test>

A better error message could indicate this executable was not compiled with parallel threading support.
I think parallel CBC does not work very well on Windows. I have tried also a GAMS version of the model using GAMS/CBC with threads=8. This leads to a crash:



Looks like this is just not working very well. May be it is good threads are disabled in the Windows executable from the binary dsitribution.

Incorrect CSV output

The column name has some embedded commas, so the name should be quoted by the CSV writer. Here is a fragment of the output.

Assign(Student1,MON,m3),0 Assign(Student1,SCH,m1),1 Assign(Student1,MON,m4),0 Assign(Student1,MON,m7),0 Assign(Student1,MON,m8),0 Assign(Student1,GES,m11),0 Assign(Student1,GES,m12),0 Assign(Student1,GES,m13),0

Update: running on Mac (GAMS/CBC)

This also looks very scary (memory overruns?):

Maximum depth 0, 6 variables fixed on reduced cost 7 added rows had average density of 51.857143 At root node, 17 cuts changed objective from 158.29268 to 161.10418 in 8 passes Cut generator 0 (Gomory) - 37 row cuts average 58.3 elements, 0 column cuts (12 active) CutS egaerncehr actoomrp l0e t(eGdo m-o rbye)s t-  o3b7j ercotwi vceu t1se +a5v0e,r atgoeo k5 82.039  eilteemreanttiso,n s0  acnodl u0m nn ocduetss  ((1182. 5a5c tsievceo nds) Maximum depth 0, 6 variables fixed on reduced cost

The CBC log is pretty dense and messy (matter of taste of course), so not always easy to see strange messages, but this gibberish is of course a sign of a problem.

Update2: Mac again

After recompiling from sources I could run the problem with multiple threads (when reading from MPS files). May be a build problem in the GAMS version of CBC. But now I see my LP files are no longer accepted:

Coin3007W ### CoinLpIO::is_invalid_name(): Name is empty Coin3007W ### CoinLpIO::are_invalid_names(): Invalid name: vnames[1396]: (null) Coin3007W ### CoinLpIO::setLpDataRowAndColNames(): Invalid row names

Not a very clear message. I would like to see what I should do to fix my file. The solution is bogus so the lp file is read in incorrectly. (To be complete: this was tar file version 2.8.12).  I am not a happy camper…

Excel Solver Error Message

Error messages really need to be formulated with care. I am already confused my code does not work and I would like to see a message that clearly states what is wrong and what I should do to remedy the situation.

A counter example is here:

Two Excel Solver bugs in two lines!! More info on the first one: http://yetanothermathprogrammingconsultant.blogspot.com/2014/04/how-do-they-make-bug-like-this.html.

Just want to make a few quick plots:

Update: fixed by coding the number as a string in the variant. An alternative fix is shown here. Both are not obvious (to me).

Old Fashioned SQL scripts

The tools gdx2sqlserver has an option to generate SQL scripts to populate a SQL Server database from GAMS data. (It has many other ETL facilities including bulk operations for high performance). Sometimes old fashioned SQL scripts are useful: we can zip and email such a file and a database person can look at it and design SQL code for further processing.

Ouch

From: http://wwww.gams.com/mccarl/newsletter/news35.pdf

PDF if the probability of a point is needed

 

Update: this is now fixed.

A little bit extra fine tuning

Sometimes it helps to revisit old code and see if we can do better:

--- Job compare.gms Start 07/01/14 23:12:51 24.2.2 r44857 WEX-WEI x86_64/MS Windows
GAMS 24.2.2   Copyright (C) 1987-2014 GAMS Development. All rights reserved
Licensee: Erwin Kalvelagen                               G130719/0001CV-GEN
          Amsterdam Optimization Modeling Group                     DC10455
--- Starting compilation
--- compare.gms(1) 2 Mb
--- call gdx2sqlite -i test4_2.gdx -o tmp1.db
GDX2SQLITE v 0.4
GDX Library      24.2.2 r44857 Released Mar  4, 2014 VS8 x86/MS Windows      
Current directory:C:\Projects\impact3\OutputFiles\PivotTables

   InputFile:test4_2.gdx
   OutputFile:tmp1.db
   Symbols:1
   Uels:339
   Loading Uels
   Processing Symbols
     results(4094828 records)
   Elapsed:23.71 seconds
   Done

--- compare.gms(2) 2 Mb
--- call gdx2sqlite -i test4_2.gdx -o tmp2.db -fast -small
GDX2SQLITE v 0.4
GDX Library      24.2.2 r44857 Released Mar  4, 2014 VS8 x86/MS Windows      
Current directory:C:\Projects\impact3\OutputFiles\PivotTables

   InputFile:test4_2.gdx
   OutputFile:tmp2.db
   Symbols:1
   Uels:339
   Loading Uels
   Processing Symbols
     results(4094828 records)
   Elapsed:10.84 seconds
   Done

--- Starting execution - empty program
*** Status: Normal completion
--- Job compare.gms Stop 07/01/14 23:13:25 elapsed 0:00:34.574

Big data cubes

When exporting some large solution sets from GAMS I was wondering about the size improvements we can get by storing strings in a pool.

The output data is organized in a very large “cube”, i.e. a single large parameter (in GAMS language) or table (when looked at from an RDBMS). In the GAMS GDX viewer the parameter results(impactparameter, scenario, commodity, region, productiontype, year) looks like:

Note that some of the strings are fairly large (the first index), while most are coded efficiently (e.g. three letter country codes). When we export this to a csv file or a database typically we export this as a single large table:

If we look at the table below we are a little bit surprised about the file sizes:

 

This is a small test case: we can expect larger file sizes in practice (more scenarios, more impact parameters, more production technologies). The SQLite databases were exported with GDX2SQLITE. The compressed GDX files were generated with the environment variable GdxCompress turned on (see http://yetanothermathprogrammingconsultant.blogspot.com/2010/04/gamsgdx-compression.html).

One reason why GAMS GDX files may be more efficient is that strings (corresponding to set elements in GAMS) are stored in a separate data structure. This pool stores only Unique ELements (or UELs). Of course we can also export the data in this form:

1. Export the UELs into a separate table (called UELS$).
2. Export the parameters with integers in the index positions (these numbers correspond to the UEL$ table). For the example above we store this in a table results$.
3. To make it easy for the user we create an SQL VIEW called results that performs the joins to get the string data. You still can do select * from results and get the same results. This database schema is actually significantly more efficient w.r.t. space. The real data is stored in the the uels$ and results$ table. The view does not store any data: the joins are performed when we do a select.

It is interesting to see how few UELs typical models have. This big parameter results has more than 4 million records but it has only 339 unique elements:

or differently derived:

I.e. the UELS$ table will be quite small. A really smart query optimizer may build a hash table out of this for quick lookup (I have seen SQL Server doing these kind of tricks).

The SQL VIEW itself – performing the joins – is somewhat ugly, but as it is automatically generated we don’t really care:

The user can just use results as it were a normal table and does not need to worry about what is happening underneath. 

This organization is a little bit like the star schema used in data warehousing and OLAP. It is a bit special as for each dimension we use the same dimension table. If we have explicit sets for each dimension we really could implement a star schema. Again with a proper SQL VIEW we can hide the ugly details from the user.

Of course the GDX files themselves are even more compact (by a large margin!). I am pushing for an ODBC driver for GDX files: that would give us direct access to GDX files as if they were SQL tables. This is both useful for end-users with tools that can use ODBC data sources (e.g. Excel, Tableau, SQL Server, Access) and for programmers who are more familiar with relational data compared to using the GDX API directly (you really need to know GAMS before you can use the GDX API).

Analytics for journalists

In http://thenextweb.com/apple/2014/06/02/apple-announces-swift-new-programming-language-ios/:

The company says that Swift apps are significantly faster than Objective-C apps, outperforming them by over 93x.

Wow. That is some programming language...

Generating Larger Pivot tables in Excel from GAMS

I was working on generating some very large pivot tables to view model results. Some issues came up. Users tend to use things differently than expected: they may download and install 64 bit versions of Excel and they may run with different language settings (decimal point vs. decimal comma). And they may generate huge output: data tables with more than a million rows can not be stored inside Excel, so we need to store these outside (external data source). The reason for the large data is that we have a multi dimensional structure: results(impactparameter,scenario,commodity,region,productiontype,year). Indeed looking at the CSV file I see for a result set with just two scenarios:

or for the Windows aficionados:

i.e. 4 million records.

Here are some notes.

Management GUI in Excel

Generated Excel worksheet

Reporting infeasible LP solutions in GAMS

When debugging models, one strategy that can be very helpful: fix a number of variables to a known (feasible) solution, solve, and inspect the reported infeasibilities. The known solution can be complete or can be a partial solution (i.e. only a fraction of the variables is fixed). In GAMS this can be done with statements like:

   x.fx(i,j) = solutionx(i,j);
   solve m using lp minimizing z;

The infeasibilities are reported in the solution report in the listing file.
Unfortunately not all solvers support this. Here is a small sample:

• MINOS: ok
• BDMLP: ok
• Cplex: ok
• Gurobi: no solution reported so nothing to look at
• Mosek: not a normal solution reported 
• Lindo: no solution reported
• Xpress: no solution reported
• CBC: no solution reported

This is not a pretty list. All older GAMS solvers do a good job and provide the wanted information without a problem, but the newer solvers and links do a rather poor job on helping me out.