Wednesday, February 27, 2013

Repeating messages

Solvers sometimes spit out messages that are basically similar. Here is an example of a list of a few million messages (literally!):

MOSEK Warning 53     : A numerically large upper bound value 2.3e+009 is specified for variable 'alloc(12463682,barl_h)' (2).
MOSEK reports warning number 53: A numerically large upper bound value 2.3e+009 is specified for variable 'alloc(12463682,barl_h)' (2).
MOSEK Warning 53     : A numerically large upper bound value 2.2e+009 is specified for variable 'alloc(12463684,barl_h)' (20).
MOSEK reports warning number 53: A numerically large upper bound value 2.2e+009 is specified for variable 'alloc(12463684,barl_h)' (20).
MOSEK Warning 53     : A numerically large upper bound value 2.0e+009 is specified for variable 'alloc(12473679,barl_h)' (38).
MOSEK reports warning number 53: A numerically large upper bound value 2.0e+009 is specified for variable 'alloc(12473679,barl_h)' (38).
MOSEK Warning 53     : A numerically large upper bound value 2.3e+009 is specified for variable 'alloc(12473683,barl_h)' (56).
MOSEK reports warning number 53: A numerically large upper bound value 2.3e+009 is specified for variable 'alloc(12473683,barl_h)' (56).
MOSEK Warning 53     : A numerically large upper bound value 3.6e+009 is specified for variable 'alloc(12473684,barl_h)' (74).
MOSEK reports warning number 53: A numerically large upper bound value 3.6e+009 is specified for variable 'alloc(12473684,barl_h)' (74).
MOSEK Warning 53     : A numerically large upper bound value 4.2e+009 is specified for variable 'alloc(12473685,barl_h)' (92).
MOSEK reports warning number 53: A numerically large upper bound value 4.2e+009 is specified for variable 'alloc(12473685,barl_h)' (92).
MOSEK Warning 53     : A numerically large upper bound value 1.4e+009 is specified for variable 'alloc(12483674,barl_h)' (110).
MOSEK reports warning number 53: A numerically large upper bound value 1.4e+009 is specified for variable 'alloc(12483674,barl_h)' (110).
MOSEK Warning 53     : A numerically large upper bound value 2.4e+009 is specified for variable 'alloc(12483683,barl_h)' (128).
. . . .

In general the n-th message has very little additional value if n is  large. A better approach is to stop issuing those similar messages after say n=10 and then just report an aggregate e.g. how many times this situation happened.

The next example is almost what I would like to see in this respect. Missing is the total number domain errors when loading this symbol.

   1  set i /j1*j1000/;
   2  alias (i,j);
   3  parameter a(i,j);
GDXIN   C:\projects\tmp\ide\x.gdx
--- LOAD  a = 3:a
**** Domain errors for symbol a
**** Only the first 10 errors are shown
     i1.i1
     i1.i2
     i1.i3
     i1.i4
     i1.i5
     i1.i6
     i1.i7
     i1.i8
     i1.i9
     i1.i10
   5  $loaddc a
****          $649
**** 649  Domain violation when loading from GDX file

Sunday, February 24, 2013

SOS2 in GAMS

https://groups.google.com/d/topic/gurobi/YZGRWaA-oQE/discussion:

image

No, sorry, this is not at all the case. In the link http://yetanothermathprogrammingconsultant.blogspot.com/2009/06/gams-piecewise-linear-functions-with.html it is indeed mentioned this is really needed to interpret the sos2 sets correctly:

“Here we need to keep c last in variable lambda. This makes sure we have i × t sets with c members.”

I.e.

  • SOS2 variables x(i) : a single set with i members (actually card(i) members but I drop the card for convenience)
  • SOS2 variables x(i,j) : i sets with j members
  • SOS2 variables x(i,j,k) : i x j sets with k members

It has nothing to do with reordering of indices to achieve better performance (I don’t think the blog post even implies this).

Of course for more information see the GAMS manual.

Saturday, February 23, 2013

SQL and NULL

Yesterday this came up again: a client was using a query with something like:

SELECT xxx FROM yyy WHERE zzz=NULL

This does not work as expected. This query will always return zero rows. The correct way is:

SELECT xxx FROM yyy WHERE zzz IS NULL

Similarly “WHERE zzz<>NULL” should be written as “WHERE zzz IS NOT NULL.” This mistake happens very often; there must be a lot of queries being used that are just wrong and giving wrong results as a consequence of this SQL quirk. This is of course a language issue: the expression looks harmless and does not give an error message.  

Notes:

  • In Access there is also an alternative: use the function isnull()
  • In SQL Server there is an option ANSI_NULLS that can be set to off to allow comparisons against NULL. This feature will be removed from a future version of SQL Server (http://msdn.microsoft.com/en-us/library/ms188048.aspx).

Friday, February 22, 2013

Meta-Heuristics or Math Programming

The problem of scheduling maintenance of generators is a well-studied problem. In particular a specific data sets has been used a lot:

 

all use the same problem. They all use some form of meta-heuristics. However this problem is also easily solved by mathematical programming. The following reformulations have helped:

  • Look at the data: the 12 month schedule can be split into two 6-month schedules. Solves 2 smaller problems is in general faster than solving one big one.
  • Use a linearization technique. Although the original problem can be formulated as a MIQP, it turns out that some MIP formulations are still faster and more reliable (e.g. Cplex has serious problems with the MIQP models). See: http://yetanothermathprogrammingconsultant.blogspot.com/2012/11/smoothing.html.

Some advantages of using math programming approaches are:

  • May be able to prove global optimality
  • May give bounds to assess quality of a solution when terminated before proving optimality
  • Modeling vs programming may (or may not) lead to more maintainable systems (easier to adapt to new circumstances, especially when using a modeling language).

Monday, February 18, 2013

big-M

In http://bob4er.blogspot.com/2013/02/the-big-m.html a big-M constraint (my favorite subject!) is formed like:

xij ≤ [1.1 min (ai, bj)] zij

I don’t really understand the reason for the fudge factor 1.1. I would write this as:

image

Here M(i,j) is an implied upper bound on x(i,j). The feasibility tolerances already add a “fudge factor”, and I can not see why I should add another one.

In some cases big-M’s need to be much smaller than this post suggests. In http://yetanothermathprogrammingconsultant.blogspot.com/2009/03/yet-another-big-m-problem-dont-blame.html we see M=1e5 is not good enough, and reducing M to 1e4 helped solve Cplex the problem correctly.

option optcr?

In the following paper an MIQP formulation is proposed for an optimal dispatch problem for power generators where some of the generators have certain output levels that are not allowed. Often we see minimum and maximum output levels, but here we have some regions inside the range [minimum_output,maximum_output] where we don’t want to be. Of course using a MIP formulation we can formulate OR constraints to model this.

image

As the fuel usage is a quadratic function of output, we end up with a MIQP model.

image

The examples are small and solve easily with Cplex or Gurobi. For the largest example with 40 generators however we get a better solution than reported:

image

May be they solved without option optcr=0…. I would love to pocket the difference.

See also: http://yetanothermathprogrammingconsultant.blogspot.com/2012/12/option-optcr.html

PS. To check a given solution, do something like:

image

That will (almost) make sure the model is formulated correctly.

Sunday, February 17, 2013

GAMS Plotting Marginals

The GAMS/IDE has an issue plotting marginals. When we select the marginals of an equation, and try to plot these, we actually get the levels:

imageimage

The workaround is to create an extra parameter and assign to it these marginals:

image

Plotting this parameter is of course no problem.

Friday, February 15, 2013

Constraint Programming and Music

Not completely sure what this is about:

Monday, February 11, 2013

Errmsg

After installing GAMS one of the first things to do is to change one of its more obscure options:

image

Without this you get the convenient default where error messages are not shown where the errors are. Like in:

3570     export.up(g,ce)    = explimit(g,ce) ;
****                $171                $171
3571     itr.fx(z1,g)=0; itw.fx(z1)  =0;

The actual error messages are found near the bottom of the listing file. With ERRMSG=1 we get a more reasonable behavior:

3570     export.up(g,ce)    = explimit(g,ce) ;
****                $171                $171
**** 171  Domain violation for set
3571     itr.fx(z1,g)=0; itw.fx(z1)  =0;