[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Help-glpk] Pointing to an inner points to start the simplex

From: Andrew Makhorin
Subject: Re: [Help-glpk] Pointing to an inner points to start the simplex
Date: Thu, 26 Apr 2007 03:57:14 +0400

> I have a problem, where I know the exact coordinates of a good but not
> optimal inner point. I want to use this good inner points in my 
> calculations, everything is done via APIs.
> Is it a good idea to save all columns bounds, fix the columns, start
> the simplex. After that I would like to recover the bounds and start
> the simplex again. Via this the optimum should be reached faster. Or
> should it be attacked in a different way?

An interior point, even if it is feasible, is useless for the simplex
method, because to start the search it needs a basic solution, i.e. it
needs to know which variables are basic and which ones are non-basic.
Geometrically this means that the simplex method can start only from a
vertex of the polyhedron, not from an arbitrary point.

On the other hand, if you can determine which constraints or bounds
are active in the initial interior point, you can make corresponding
rows and columns non-basic, providing the simplex method with a good
initial basis. The problem is that the number of basic variables has
to be the same as the number of rows, so sometimes it is difficult to
determine a complete set of basic variables.

Or do you mean something else?

reply via email to

[Prev in Thread] Current Thread [Next in Thread]