gdx2sqlserver: more optimizations

The bulk import facility of SQL Server allows both ascii (text) files or binary files. The documentation states this can make some differences in performance. To test this I added a binary flag (-b) to the gdx2sqlserver tool so it can create a temporary file in native binary format.

To measure the difference we first execute the following GAMS model:

set i /i1*i100/; alias(i,j,k); parameter a(i,j,k); a(i,j,k) = uniform(0,100); execute_unload "test",a; execute "gdx2sqlserver -i test.gdx -S .\SQL1 -db tmp -s tmp -v";

I.e. create a three dimensional parameter a with 100 x 100 x 100 = 1 million entries. The values are random. Then export this as gdx file test.gdx and finally import the gdx file into SQL Server using default settings (except for a verbose –v flag). We see:

a (1000000 records)    select object_id('[tmp].[a]','U')    drop table [tmp].[a]    create table [tmp].[a]([i] varchar(4),[j] varchar(4),[k] varchar(4),[value] double precision)    temp file: [C:\Users\Erwin\AppData\Local\Temp\tmp2B08.tmp]    writing C:\Users\Erwin\AppData\Local\Temp\tmp2B08.tmp    bulk insert [tmp].[a] from 'C:\Users\Erwin\AppData\Local\Temp\tmp2B08.tmp'    rows affected: 1000000    commit    time: 16.0 seconds    deleting [C:\Users\Erwin\AppData\Local\Temp\tmp2B08.tmp]

This was using a text file (actually a tab delimited file). Next we do the same thing but add the –b flag. The result is:

a (1000000 records)    select object_id('[tmp].[a]','U')    drop table [tmp].[a]    create table [tmp].[a]([i] varchar(4),[j] varchar(4),[k] varchar(4),[value] double precision)    temp file: [C:\Users\Erwin\AppData\Local\Temp\tmp9F9.tmp]    writing C:\Users\Erwin\AppData\Local\Temp\tmp9F9.tmp    bulk insert [tmp].[a] from 'C:\Users\Erwin\AppData\Local\Temp\tmp9F9.tmp' with (datafiletype='native')    rows affected: 1000000    commit    time: 10.0 seconds    deleting [C:\Users\Erwin\AppData\Local\Temp\tmp9F9.tmp]

The difference in performance is much more pronounced than I expected. A second advantage is that the floating point numbers are not suffering from round-off during the conversion from and to ascii.

A number of optimizations has enabled to move data quickly from a GAMS GDX file into SQL server and each optimization gave us some extra performance. Here is a short review of things I tried, with timings on transferring the same large parameter ‘a’, so the numbers are comparable:

1. Multiple inserts. Done reasonably smart: no auto-commit after each insert, and a prepared statement to reduce some overhead: 258.3 seconds.
2. Bulk insert with ascii file: 17.8 seconds.
3. Improved buffering when writing ascii file: 16.0 seconds.
4. Bulk insert with buffered binary file: 10.0 seconds.

Large tab delimited files and buffer size

A piece of software reads a GAMS GDX file and produces a tab delimited text file to be used for bulk import into a database. This is written in Delphi (Pascal) and the default text buffer size is a skimpy 128 bytes. That means many Windows API calls for my data set. It is better to use a larger buffer size, but I expect the effect of making the buffer larger will taper off very quickly. Indeed, I did a small, quick test:

We measure here the time of the loop:

for i := 1 to n do begin
   read_record_from_gdx_file;
   write_record_to_text_file;
end;

Indeed moving from the default of 128 bytes to a 1k buffer gives us most of the performance boost, while moving further to 2k or 4k helps just a tiny bit. After that there is no further effect.

Markal and VB6

Yesterday I saw some demonstrations of different versions of the Markal energy model (and its successor Times). These systems use GAMS as modeling tool and heavily depend on Excel and VBA for data entry and MS Access for storage. More interestingly, both front-ends I saw (Answer and Veda) are still VB6 based applications. The last version of Visual Basic 6 is from 1998, almost 20 years ago! (With an MSDN subscription you can still download Visual Basic 6.0 Enterprise). Obviously these applications are not on the cutting edge of technology. But this is not really the point I want to make. What is really noteworthy is the longevity this specialized optimization application shows. This is essentially a 30 year old model that still has much relevancy today.

Browser-based Pivot Tables

There are some interesting ways to present a pivot table in a browser. Some of the Javascript based tools can actually work with very large data sets:

Here we have a data set with 1.2 million records, and it is actually quite workable using the JavaScript code from here. In this example we used the heatmap to show production of green coffee and we see immediately Brazil is the largest producer. This tool is a useful alternative for the GAMS/IDE GDX viewer which has a very fast pivot table facility but is somewhat barebones, and for Excels pivot table which is highly configurable but needs external data for large data sets (and needs Excel to be installed).

The data for the above table was exported from a GAMS data set, and included in the HTML page as a JSON-type data set. The advantage of a browser based solution is that you can disseminate results easily over the Web and users do not have to install any software.

ODHeuristics

From: VUGApril2​016PDF.zip:

Some results are shown on some big, nasty problems:

The people behind this effort are Alkis Vazacopoulos and Robert Ashford. They know what they are talking about as they were behind the Xpress MP solver (now FICO Xpress). Interestingly they are now using Cplex as MIP engine.

GAMS Google Group out of commission

The GAMS google group “gamsworld” is no longer functioning:

From what I understand this problem seems more complicated to fix than one would expect.

Cplex and counting solutions

When running MIP models I basically stare somewhat obsessively at the log. Hence I noticed:

71    73        0.0423   292       18.1387        0.0000    87092  100.00%      72    74        0.2139   380       18.1387        0.0000    90725  100.00% Elapsed time = 688.25 sec. (76733.97 ticks, tree = 0.01 MB, solutions = 2)      81    83        0.0980   354       18.1387        0.0000    98918  100.00% *    87+   87                           17.7364        0.0000           100.00% Found incumbent of value 17.736352 after 688.25 sec. (76733.97 ticks)      94    96        0.1251   291       17.7364        0.0000   106148  100.00%      98   100        0.0899   325       17.7364        0.0000   111398  100.00%      99   101        0.0648   296       17.7364        0.0000   111683  100.00%     103   105        0.1777   286       17.7364        0.0000   113016  100.00%     104   106        0.1122   367       17.7364        0.0000   116380  100.00%     111   113        0.0000   130       17.7364        0.0000   122226  100.00%     113   115        0.1117   296       17.7364        0.0000   123107  100.00%     114   116        0.0491   229       17.7364        0.0000   123240  100.00%     115   117        0.0961   371       17.7364        0.0000   125152  100.00% Elapsed time = 688.27 sec. (79705.40 ticks, tree = 0.01 MB, solutions = 2)     116   118        0.0049   284       17.7364        0.0000   125684  100.00%                                                  ZeroHalf: 73                      117   119        0.0196   352       17.7364        0.0000   127374  100.00%     118   120        0.0000   113       17.7364        0.0000   127401  100.00%     119   121        0.0921   383       17.7364        0.0000   130049  100.00%     120   122        0.0029   297       17.7364        0.0000   130295  100.00%     121   123        0.0564   400       17.7364        0.0000   134590  100.00%     122   124        0.0029   276       17.7364        0.0000   134734  100.00%     123   125        0.0210   391       17.7364        0.0000   142995  100.00%     124   126        0.0319   323       17.7364        0.0000   144228  100.00%     125   127        0.0196   334       17.7364        0.0000   144391  100.00% Elapsed time = 866.91 sec. (91170.15 ticks, tree = 0.01 MB, solutions = 3)     130   132        0.0114   442       17.7364        0.0000   154043  100.00%     131   133        0.0480   292       17.7364        0.0000   155292  100.00%     137   139        0.0539   137       17.7364        0.0000   160339  100.00%

First I thought, wow, Cplex needs a lot of time to do a single addition: the third solution only is noticed many nodes and many seconds later. But then look at the timings marked in orange. There is actually very little time between logs lines where the solution is found and where the number of solutions is reported. (This was a run with multiple threads, no doubt that played a role).

Sequencing of jobs

Suppose we need to sequence \(n\) jobs where each job has a cost \(a_i\). In addition there is a changeover cost \(c_{i,j}\) when job \(i\) immediately precedes job \(j\) (see this post). 

First observe that the cost \(\sum_i a_i\) form just a constant (we need to execute each job exactly once), so we can leave them out of the model.

For some the remaining problem may look like a TSP (Traveling Salesman Problem), except we don’t need to return to the city where we started from. We can also look at it differently.

The task of assigning jobs to periods is just like an assignment problem:

\[\boxed{\begin{align}  &x_{i,t} \in \{0,1\} \\                           &\sum_t x_{i,t} = 1 \>\>\forall i\\                           &\sum_i x_{i,t} = 1 \>\>\forall t \end{align}}\]

This was the easy part. To see if a job \(j\) immediately follows a job \(i\), we can do something like:

\[\boxed{\begin{align}  &y_{i,j} \in \{0,1\} \\                           &y_{i,j} = \sum_{t} x_{i,t} x_{j,t+1} \end{align}}\]

The sum gives us either 0 or 1 for feasible integer solutions. A slightly different formulation turns out to be easier to handle:

\[\boxed{\begin{align}  &y_{i,j} \in \{0,1\} \\                           &y_{i,j} \ge x_{i,t} x_{j,t+1}\>\> \forall t \end{align}}\]

We let \(y_{i,j}\) float unrestricted if \(j\) is never a successor to \(i\). In that case, we leave it to the objective to choose \(y_{i,j}=0\) when needed.

We can linearize the last inequality by \(y_{i,j} \ge x_{i,t} + x_{j,t+1} –1\). Once we have \(y_{i,j}\) the objective is obvious: minimize \(\sum_{i,j} c_{i,j}y_{i,j}\).

The complete model can look like:

In the model we paid some attention to excluding cases where \(i=j\). Note that with \(c_{i,i}=0\) we just could leave out this exclusion, but I always prefer to model these things a bit more precise. The results for random \(c_{i,j}\) are:

gdx2sqlserver: bulk inserts into SQL Server

In this post we describe how a bulk insert method can help get better performance when importing large data sets into an MySQL database. The same thing is true for SQL Server. In the tool gdx2sqlserver we dynamically switch to using bulk inserts when the number of records to insert is larger than a threshold. Using this we get good performance on GDX file with 100 element set and a 1 million element parameter:

set i /i1*i100/; alias(i,j,k); parameter a(i,j,k); a(i,j,k) = uniform(0,100); execute_unload "test",i,a; execute "gdx2sqlserver -i test.gdx -S .\SQL1 -db tmp -s tmp";

The default output is:

--- Job Untitled_1.gms Start 05/01/16 12:46:29 24.6.1 r55820 WEX-WEI x86 64bit/MS Windows GAMS 24.6.1   Copyright (C) 1987-2016 GAMS Development. All rights reserved Licensee: Erwin Kalvelagen                               G150803/0001CV-GEN           Amsterdam Optimization Modeling Group                     DC10455 --- Starting compilation --- Untitled_1.gms(6) 3 Mb --- Starting execution: elapsed 0:00:00.010 --- Untitled_1.gms(5) 36 Mb --- GDX File C:\Users\Erwin\Documents\Embarcadero\Studio\Projects\gdx2sqlserver\Win32\Debug\test.gdx --- Untitled_1.gms(6) 36 Mb GDX2SQLServer v 0.1 Copyright (c) 2015-2016 Amsterdam Optimization Modeling Group LLC    GDX Library      24.6.1 r55820 Released Jan 18, 2016 VS8 x86 32bit/MS Windows    GDX:Input file: test.gdx    GDX:Symbols: 2    GDX:Uels: 100    GDX:Loading Uels    SQL:Selected driver: ODBC Driver 11 for SQL Server    SQL:Connection string: Driver={ODBC Driver 11 for SQL Server};Server=.\SQL1;Trusted_Connection=Yes    SQL:RDBMS version: Microsoft SQL Server 2014 - 12.0.2269.0 (X64)    SQL:Database: tmp    SQL:Schema: tmp    -----------------------    i (100 records)    a (1000000 records)    Done (17.2 seconds) *** Status: Normal completion --- Job Untitled_1.gms Stop 05/01/16 12:46:47 elapsed 0:00:17.862

With the –v (verbose) flag we see that the second, larger symbol is using BULK INSERT:

GDX2SQLServer v 0.1 Copyright (c) 2015-2016 Amsterdam Optimization Modeling Group LLC    GDX Library      24.6.1 r55820 Released Jan 18, 2016 VS8 x86 32bit/MS Windows    GDX:Input file: test.gdx    GDX:Symbols: 2    GDX:Uels: 100    GDX:Loading Uels    SQL:Selected driver: ODBC Driver 11 for SQL Server    SQL:Connection string: Driver={ODBC Driver 11 for SQL Server};Server=.\SQL1;Trusted_Connection=Yes    SQLInfo:[Microsoft][ODBC Driver 11 for SQL Server][SQL Server]Changed database context to 'master'.    SQLInfo:[Microsoft][ODBC Driver 11 for SQL Server][SQL Server]Changed language setting to us_english.       select @@VERSION    SQL:RDBMS version: Microsoft SQL Server 2014 - 12.0.2269.0 (X64)         Jun 10 2015 03:35:45         Copyright (c) Microsoft Corporation         Developer Edition (64-bit) on Windows NT 6.3 <X64> (Build 10586: )       select db_id('tmp')       use [tmp]    SQLInfo:[Microsoft][ODBC Driver 11 for SQL Server][SQL Server]Changed database context to 'tmp'.    SQL:Database: tmp       select schema_id('tmp')    SQL:Schema: tmp    -----------------------    i (100 records)       select object_id('[tmp].[i]','U')       drop table [tmp].[i]       create table [tmp].[i]([i] varchar(4))       insert into [tmp].[i] values (?)       sqlexecute(100 times)       commit       Time: 0.1 seconds    a (1000000 records)       select object_id('[tmp].[a]','U')       drop table [tmp].[a]       create table [tmp].[a]([i] varchar(4),[j] varchar(4),[k] varchar(4),[value] double precision)       temp file: [C:\Users\Erwin\AppData\Local\Temp\tmp908A.tmp]       writing C:\Users\Erwin\AppData\Local\Temp\tmp908A.tmp       bulk insert [tmp].[a] from 'C:\Users\Erwin\AppData\Local\Temp\tmp908A.tmp'       rows affected: 1000000       commit       Time: 17.8 seconds       deleting [C:\Users\Erwin\AppData\Local\Temp\tmp908A.tmp]    Done (18.0 seconds)

Here we deem symbol ‘i’ to be small (100 records) and we use a prepared insert statement. Symbol ‘a’ is considered large and we use bulk insert method. Indeed when we would have used normal inserts for the large symbol ‘a', we would have seen:

a (1000000 records)    select object_id('[tmp].[a]','U')    drop table [tmp].[a]    create table [tmp].[a]([i] varchar(4),[j] varchar(4),[k] varchar(4),[value] double precision)    insert into [tmp].[a] values (?,?,?,?)    sqlexecute(1000000 times)    commit (100 times)    Time: 258.3 seconds

which is much slower.

There are still some improvements possible:

• Better buffering of the intermediate text files. This reduces the time from 17.8 to 16 seconds.
• Use a binary data file (maybe slightly faster, and maintains precision) This has now been implemented (see here), and reduced the time to move symbol ‘a’ into SQL Server to 10 seconds.
• Use bulk data API. This requires us to bypass ODBC and use some SQL Server Client DLL that may not be installed by the user.

LP solve problems with tiny model

From this post:

Model name:  'LPSolver' - run #1 Objective:   Maximize(R0) SUBMITTED Model size:        3 constraints,       4 variables,            6 non-zeros. Sets:                                   0 GUB,                  0 SOS. Using DUAL simplex for phase 1 and PRIMAL simplex for phase 2. The primal and dual simplex pricing strategy set to 'Devex'. Relaxed solution                   4 after          4 iter is B&B base. Feasible solution                  2 after          6 iter,         3 nodes (gap 40.0%) Optimal solution                   2 after          7 iter,         4 nodes (gap 40.0%). Excellent numeric accuracy ||*|| = 0 MEMO: lp_solve version 5.5.2.0 for 32 bit OS, with 64 bit REAL variables. In the total iteration count 7, 1 (14.3%) were bound flips. There were 2 refactorizations, 0 triggered by time and 0 by density. ... on average 3.0 major pivots per refactorization. The largest [LUSOL v2.2.1.0] fact(B) had 8 NZ entries, 1.0x largest basis. The maximum B&B level was 3, 0.8x MIP order, 3 at the optimal solution. The constraint matrix inf-norm is 3, with a dynamic range of 3. Time to load data was 0.001 seconds, presolve used 0.010 seconds, ... 0.020 seconds in simplex solver, in total 0.031 seconds.