Monday, December 28, 2009

A simple example demonstrating the effect scaling in optimization problems.

Now assume you have the constraints

                   x  <= 1000000
1000001<= x

in an optimization model. Clearly the problem is infeasible. Now assume you have the constraints

                  1.0e-6  x  <= 1 + epsilon
1000001<=            x

then they are still infeasible if epsilon=0.0. Note the second set of constraints is equivalent to first set of constraints except the first constraint has be scaled by a factor of 1.0e-6 (assuming epsilon=0.0).
However for epsilon of 1.0e-6 the constraints are FEASIBLE! The status of the problem has changed.

Most optimizatizers for LPs and nonlinear problems will declare the solution feasible it satisfies all the constraints within a small tolerance of say 1.0e-6. And hence they will report the second set of constraints as feasible even for epsilon=0.0. Whereas they will consider the first set of constraints infeasible.

The following can learned form this small example:
  • Scaling of constrains (and variables) has an effect.
  • The effect can be quite dramatic if the problem is near infeasible or is near feasible.
  • Different optimizers will scale differently and hence it is very likely they will reach different conclusions i.e. whether the problem is infeasible or not.
B.t.w. most users on optimization software will prefer the software say feasible. At least we less likely to get complaints given that outcome.

Tuesday, December 8, 2009

Controlling the glibc version

On Linux we would very much like to control which glibc version we link with. The reason we are ISV and would like to make sure that our libraries works on as many platforms as possible. And also to know on which platforms it does not work so we can tell customers.

After reading the excellent blog and doing a lot expirimentation with gcc we concluded that it is almost impossible to get gcc to pick up another glibc version that the one installed as the default on the system. Therefore, it is very important to control which system the released code is build on.

OpenMP blues.

My company MOSEK sell a software package which essential part is a dynamic link library (shared libray). In order to exploit multiple threads we use OpenMP which is fairly simple to use.

Our customers may link that library with their application programs/libraries. Hence, we have very little control over how customers employ our library. They may link it with arbitrary other libraries. For instance our program may be called
  • .NET
  • Java
or some other third party environment. It is there essential that the OpenMP support library works with almost about anything just as the pthread library does on UNIX. Unfortunately it does not. Based on our expirience with the OpenMP library supplied with the Intel C compiler we have seen:
  • Crashes on Linux when OpenMP is used from MATLAB.
  • Strange crashes when our library is loaded on run time. It seems some finalize code is executed a the proper time when the shared libraries are off loaded.
  • Link problems. When we link with version of the OpenMP support library and our customer link with another version that our customers thinks we are stupid.
In summary it basic underlying assumption of OpenMP seems to be that the users build and link the complete application involving OpenMP. So it is very suitable for "Hello world" type of programs. It is pain to use for a commercial vendor of dynamic/shared link libraries. We definitely need something better. Our ideal requirements are
  • that is 100% compatible with C (not C++),
  • is almost as easy to use as OpenMP,
  • makes it a lot easier to debug i.e. be open source and
  • give us much control over what is happening.

Systems for selling software?

My company sell software licenses. Unfortunately that that seems t be way harder than you should think. I think the reason is that there is physical good with a serial number. Moreover,
maintenance is frequently a part of license and it involves a time dimension.

Currently, we use an home gown system for software sales but would like to replace it with a new system that we do not have maintain ourselves. It turns out to be extremely difficult to find a system that is better than current system. I will now explain why.

Some facts are:
  • The customers cannot keep track of their licenses. It essential we do that.
  • A customer may have many departments/groups and sometimes it is important to keep track of which group owns which license.
  • The customers may use software resellers such as Insight ( i.e. they buy licenses and maintenance on behalf of the end customer. Those middlemen never track licenses and if you ask them about maintenance renewable they never answer back.
  • You have track payments so you can ask customers why they do not pay.
  • Computing VAT for software licenses is not so obvious.
  • Ideally you would like to work with multiple currencies.
  • Know what purchase order is.
  • [Generate custom reports about the sales.]
Moreover, we have started seeing our big customers employs systems such as Ariba to generate purchase orders. Therefore, it would nice to be able to integrate with such systems.

Usually we sell those licenses with maintenance if customer want free upgrades. It works like this. Let us assume the license cost P$ and the maintenance pct is 25%. That means if you buy a license the 1st of June with maintenance you have to pay

P + (0.25 *P)*180/365

Regarding maintenance then the software selling system should:
  • compute the maintenance fee automatically.
  • the maintenance period should be shown on invoice.
  • it should easy to relate the maintenance to the license.
  • the system should make very easy to renew maintenance. It does not have to be automatic. Semi automatic is enough.
There many systems that helps selling software for instance Salesforce but they are normally focused at the selling. They do not help much with the license tracking and the maintenance renewable which is the key items for us.

Some other vendors are:
but to the best of knowledge they either not interested in small vendors like us. Or they are bot very good at maintenance handling.

If you the reader knows a system that could then please inform me about it :-). Thanks in advance.

Friday, November 6, 2009

Windows 7 on IBM T61

I have justed switched to Windows 7 on my IBM T61 laptop instead of server 2008.

It has been an extremely pleasant exprience. It works out of the box and uses much less resouces than Vista.

Monday, September 7, 2009

Presolve and duplicate constraints

Long time ago my brother and I wrote a paper about presolve in linear programming. A subject that keeps on surprising me. Here is something to think about.

We defined two rows of A to be duplicate if they were identical up to a nonzero multiplier. Hence,

1e-06 x1 -1e-06 x2 >= 0
x1 - x2 <= 0

are duplicate. Normaly the presolve would merge two such constraints too

1e-06 x1 -1e-06 x2 = 0 (1)

x1 - x2 = 0 (2)

Oberseve that (x1,x2)=(0.1 , 0) is infeasible for the orginal system but feasible for (1) given a feasibility tolerence of 1.0e-7. Moreover, (x1,x2)=(0 , 0.1) is feasible for the orginal system but infeasible for (2).

Mathematically (1) and (2) are equivalent to the original system. However, in a finite presiscion and using feasibility tolerances they are very different.

The first lesson to be learned is that scaling matters. The second lesson is that we should be careful when we merge duplicate constraints. My preference would be to include the constraint (2) in the presolved problem.

Tuesday, April 21, 2009

Windows remote desktop and sticky keys

I am frquently doing Remote Desktop from a Windows computer to a Windows computer.

For obvious reasons then client keyboard is usually a Danish key board. Now if the client computer has both an Danish and an English keyboard installed then some keys appears as sticky and the AltGr sometimes works strangely.

It seems the problem is described at Hence,

Configure Windows to stop applying keyboard shortcuts to Terminal Services sessions. To do this, follow these steps:
  1. Click Start, click Run, type mstsc.exe, and then click OK.
  2. In the Remote Desktop Connection dialog box, click Options, and then click the Local resources tab.
  3. In the Apply Windows key combinations list, click On the local computer.
  4. On the General tab, click Save As, type a name in the File name box, and then click Save.
solves the problem.



This is my private blog where plan to write about my work related experiences. It could for instance be tips or tricks I have found and the like.

Also I am likely to say something about mathematical optimization which is big interest for me.

Btw I am currently a CEO for MOSEK ( so there is likely to be some comments advetising for MOSEK. Now you are warned.