Re: [Help-glpk] help to formulate problem in terms of LP

[glpk xypron]

Hello Dima,

the red area exist for:

xamin < xbmin
or
xamax > xbmax
or
yamin < ybmin
or
yamax < ybmax

This cannot be described in an LP, but in a MILP:

binaries xb1, xb2, yb1, yb2;
constant M sufficiently high;
(xbmin - xamin) - M * xa1 <= 0;
(xamax - xbmax) - M * xb1 <= 0;
(ybmin - yamin) - M * ya1 <= 0;
(yamax - ybmax) - M * yb1 <= 0;
(xbmin - xamin) + M * (1-xa1) >= 0;
(xamax - xbmax) + M * (1-xb1) >= 0;
(ybmin - yamin) + M * (1-ya1) >= 0;
(yamax - ybmax) + M * (1-yb1) >= 0;

An area of a outside of b exist if sum(xb1, xb2, yb1, yb2) > 0

Best regards
Xypron
-------- Original-Nachricht --------
> Datum: Sat, 19 Apr 2008 17:30:05 +0400
> Von: Dima Ry <address@hidden>
> An: address@hidden
> Betreff: [Help-glpk] help to formulate problem in terms of LP

> 
> I currently deal with parallelepipeds. The task is to know is one
> parallelepiped itersects other one. The geometry shown at picture :
> http://www.nabble.com/file/p16782979/lp_question.gif 
> 
> I need to know is the red area of parallelepiped "a" exists or not. The
> red
> area can be found as intersection of "a" internal area and "b" external
> area. If intersection exists then "a" intersects "b"
> 
> If where a way to solve this task using LP?
> 
> 
> There is  no problem to express internal area in terms of LP. But i wonder
> if external area of "b" can be expressed?
> 
> I tried following :
> for "a" following constraints :
> x >= 1
> x <= 3
> y >= 2
> y <= 3
> 
> for "b" 
> x <= 2
> x >= 4
> y <= 1
> y >= 4
> 
> Since all equation are connected with "and" operator thus "x <= 2 and x >=
> 4" will issue "no solution"
> 
> Thanks in advance for any ideas.
> -- 
> View this message in context:
> http://www.nabble.com/help-to-formulate-problem-in-terms-of-LP-tp16782979p16782979.html
> Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.
> 
> 
> 
> 
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/help-glpk

-- 
Psst! Geheimtipp: Online Games kostenlos spielen bei den GMX Free Games! 
http://games.entertainment.gmx.net/de/entertainment/games/free