[Coin-lpsolver] Querying the feasible bounds

[Matthew Saltzman]

On Sat, 5 Nov 2005, Spencer Fung wrote:

> Lou,
>
> The Arc consistency is only for finite domain problem, isn't it? Actually, I
> am also interested on the techniques for pre-solving a LP. Do you know any
> paper talk about that?

The classic for LP is

A.L. Brearly, G. Mitra and H.P. Williams, An analysis of mathematical 
programming problems prior to applying the simplex method, Math. 
Programming 8 (1975), 54-83.

>
> BTW, I still want to know the procedure in CLP for getting the bounds after
> pre-solve.
>
> Thanks.
>
> Spencer
>
> -----Original Message-----
> From: coin-lpsolver-bounces at list.coin-or.org
> [mailto:coin-lpsolver-bounces at list.coin-or.org] On Behalf Of Lou Hafer
> Sent: Saturday, November 05, 2005 2:47 AM
> To: coin-lpsolver at list.coin-or.org
> Subject: RE: [Coin-lpsolver] Querying the feasible bounds
>
> Spencer,
>
> 	To expand a bit on Matt's answer: Essentially, you're asking the
> solver
> to infer tighter bounds by looking at the interactions between your
> constraints.
> This is what a presolve does --- analyses the constraint system and modifies
> it (usually, simplifies it) so that the inferences are explicit in the
> system.
>
> 	Over in AI, various techniques that OR people apply in presolve are
> used
> (often with more persistence) in constraint propagation.  Arc consistency
> (generalised as k-consistency) is one such technique.
>
> 	You can think of cutting planes as inferring consequences of
> integrality.
>
> 	Bottom line, though, is that inference is not free.
>
> 							Lou
>
> _______________________________________________
> Coin-lpsolver mailing list
> Coin-lpsolver at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>
> _______________________________________________
> Coin-lpsolver mailing list
> Coin-lpsolver at list.coin-or.org
> http://list.coin-or.org/mailman/listinfo/coin-lpsolver
>

-- 
 		Matthew Saltzman

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