Tuesday, April 26, 2011

Performance of Python based modeling

The performance of real-world, large-scale models can be relatively low with Python approaches. I suspect this is because this is essentially a “scalar” based approach behind a high-level syntax: each individual constraint and variable leads to objects being created.

From: https://software.sandia.gov/trac/coopr/raw-attachment/wiki/Pyomo/pyomo-jnl.pdf :

  • up to 62 times slower (32 times when garbage collection is disabled) than AMPL on a large, dense p-median problem
  • 6 times slower than GAMS on a complex production/ transportation model

 

pyomo

I don’t think this performance hit is mainly a result of Python vs. C/C++, but rather a result of the abstraction level of the modeling framework. It would need to be lifted to blocks of variables, equations and parameters instead of individual variables and equations. I suspect that a “proper” implementation of such a modeling framework (which is more complex than what is done here) would be able to achieve AMPL- and GAMS-like performance

Monday, April 18, 2011

Large transportation problem

I was rerunning a large instance of a test problem with GAMS/MOSEK. As it is a network problem (a transportation model in fact; it models how to assign people to jobs after a reorganization), it makes sense to try a few different algorithms.

Statistics (incl obj) Rows 4,601
  Columns 4,800,001
  NZ 13,020,000
Timings (sec) GAMS generation 40
  MOSEK default (interior point) 105
  MOSEK primal simplex 57
  MOSEK network 49

This is with default GAMS-solver communication (i.e. files). With DLL usage (no files) the times for GAMS and MOSEK are slightly larger (I don’t know why this is the case: in-core data structures should in general – well actually always – be faster than disk files; I suspect there is something wrong with the new “load library” link).

Update: a little more investigation shows that GAMS still writes a very large socalled dictionary file even if we use solvelink = 5 (load library). The fastest way seems to drop m.solvelink=5 (still don’t understand why that option is not faster) but to include m.dictfile=0. This yields: GAMS generation time: 31 seconds, MOSEK network code: 44 seconds. I.e. GAMS still generates this large network model a little bit quicker than the fastest network solver I have access to can solve it.

Live databases

Recently I was helping out with some AMPL modeling effort. The client used the ODBC table facilities of AMPL to read data directly from an SQL server database. Although this sounds very efficient and sexy, in many cases it may be better to not to get the data directly from a live database. The main issue is that runs may not be reproducible (the database content may change). Also it is difficult to share by email or ftp a corporate database. Instead I often suggest to make a snapshot in a format that is somewhat more convenient to share. In this case we used Access as a staging database. This will allow us to easily save instances and get these into the hands of external consultants. Actually I am thinking if it would be worthwhile to invest a little bit of time to generate AMPL data files (text). This will lead to smaller files, and AMPL can read those files very fast. Especially when the model is under active development this scheme is very convenient.

For another client I used a similar approach with GAMS. The client generated one big XML file from SQL Server, and we imported this to Access where we added some extra data checks and data preparation steps. The next step was to convert this to a GDX file which can be imported efficiently into GAMS. In this case we moved some of the data preparation into Access while this could have been done also in GAMS. The main reason is that there are developers available (both externally and in-house) with good knowledge of Access but without knowledge and experience in GAMS. Available skill sets can be a determining factor in deciding what to do where in the whole chain.

Thursday, April 14, 2011

Modeling vs writing code

Recently I delivered a prototype model that implements some supply chain functionality and will be integrated into an  Enterprise Resource Planning (ERP) system. The model was implemented in Microsoft Solver Foundation. I often find expressing optimization models in code somewhat cumbersome and less productive than using a more compact modeling language. So I chose to use the same approach as shown here: http://yetanothermathprogrammingconsultant.blogspot.com/2009/05/ms-oml-model-using-c-and-data-from.html. I.e. embed the model in a C# but still use the modeling language (in this case OML). Of course the model itself (about 50 lines) is much “smaller” than all the code needed to prepare the data and getting the data in and out (even though the .NET DataTables have nice functionality to process data – even without using LINQ).

Large MIP

I am working on this very large MIP model:

MODEL STATISTICS

BLOCKS OF EQUATIONS          13     SINGLE EQUATIONS      172,124
BLOCKS OF VARIABLES          11     SINGLE VARIABLES      162,496
NON ZERO ELEMENTS       887,642     DISCRETE VARIABLES    157,506

I did not expect to get much performance out of this, but amazingly Gurobi solves this thing to a very small gap in a few hundred seconds on my laptop.

The model is still in development and not all conditions are yet properly formulated. I am almost sure we will get into trouble later on, but for now being able to solve these models in one shot is great.

At least we have exercised a fairly large part of the application: retrieving the data from the data base and we also checked plugging in an existing user-provided solution. That means we have stressed and verified a significant portion of the whole system.

Thursday, April 7, 2011

Persistency

Especially with scheduling models, solutions tend to differ widely from one run to the next. Often this is the case without a significant impact on the objective. See also: http://yetanothermathprogrammingconsultant.blogspot.com/2009/11/persistency-in-math-programming-models.html.

Currently I am involved in developing a MIP based scheduling tool for TV advertisements. It is interesting to see that the original home-brew scheduling software (I am supposed to “beat” this existing system) actually has facilities to achieve persistency (without using this term).  The conclusion is: this is a problem real users observe and we better make sure this is also handled by our implementation.