[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
> 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