[Coin-lpsolver] Some problems about LP solver

[Matthew Saltzman]

On Wed, 17 Sep 2003, Lei Chen wrote:

> Hi,
>     I am currently using CLP as a part of my research project. I have a
>     collection of LP problems and try to solve them as fast as possible.
>     So I try to exploite the relations among LPs tasks to speed up the
>     performance. Now I have the following question:
>
>     1. If there are two LP tasks, The second only has one more row
>     constraint than the first one, how can I speed up the second LP
>     after the first one is done?
>             This question has already been answered by John (Thanks!).
>             We can simply add one more row and use dual algorithm. Then
>             the second LP will be a lot faster.
>
>     2. If I have a collection of LP, all of them shares the same matrix
>     A, the column lower bound, and column higher bound. The only
>     difference are the row lower bound and higher bound. How can I take
>     advantage of this fact to minimize the total cost of all these LP
>     tasks.

See question 1.  Once you have an optimal solution to the first problem,
changeing the RHS can only affect feasibility of the optimal basis.  So
the optimal basis is good to start the dual simplex.  This is not a
guarantee of a quick solution to the next problem, but it is likely to be
better than starting from scratch, particularly if the bounds don't change
"much".

>
>     3. Since the solution space of a LP is convex. Is there any fast way
>     to find all the extreme points of the convex solution space?

There are codes to do this, none in the current COIN-OR repository.  See
the LP FAQ
(http://www-unix.mcs.anl.gov/otc/Guide/faq/linear-programming-faq.html).
In general, this can't be done fast, as the number of vertices can grow as
fast as \choose{n}{m}.

>
>     I know that some of the question might seen to be amateurish. My
>     research major is in Database rather than Optimization. But I really
>     appreciate if some one can give me any clue about the above
>     question. Thanks in advance.
>
> Lei Chen
>
>

-- 
		Matthew Saltzman

Clemson University Math Sciences
mjs AT clemson DOT edu
http://www.math.clemson.edu/~mjs