help-glpk
[Top][All Lists]

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

 From: glpk xypron Subject: Re: [Help-glpk] help to formulate problem in terms of LP Date: Sat, 19 Apr 2008 21:16:21 +0200

```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
> 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