help-glpk
[Top][All Lists]

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

 From: Dima Ry Subject: Re: [Help-glpk] help to formulate problem in terms of LP Date: Tue, 22 Apr 2008 01:24:58 -0700 (PDT)

```I tried to simulate following scenario :
http://www.nabble.com/file/p16823521/mip_question.gif

(X<=1 or X>=4) and (X>=2 and X<=3)
(Y<=1 or Y>=4) and (Y>=2 and Y<=3)
(Z<=1 or Z>=4) and (Z>=2 and Z<=3)

expressed in terms of MIP

\* Problem: bubble *\

Maximize
obj: + X + Y + Z

Subject To
r_1: - 10000000000 b1 + 3 X <= 3
r_2: + 10000000000 b1 - 3 X <= 9999999988
r_3: - 10000000000 b2 + 3 Y <= 3
r_4: + 10000000000 b2 - 3 Y <= 9999999988
r_5: - 10000000000 b3 + 3 Z <= 3
r_6: + 10000000000 b3 - 3 Z <= 9999999988
r_7: + X >= 2
r_8: - X >= -3
r_9: + Y >= 2
r_10: - Y >= -3
r_11: + Z >= 2
r_12: - Z >= -3

Bounds
0 <= b1 <= 1
0 <= b2 <= 1
0 <= b3 <= 1

Generals
b1
b2
b3

End

There should NOT be a solution but solver finds optimal solution. And found
solution does not satisfy equations.

I use Delphi glpk port.

Log is following :

0:   objval =   0,00000000E+000   infeas =   1,00000000E+000 (0)
6:   objval =   6,00000000E+000   infeas =   0,00000000E+000 (0)
*     6:   objval =   6,00000000E+000   infeas =   0,00000000E+000 (0)
*     9:   objval =   9,00000000E+000   infeas =   0,00000000E+000 (0)
OPTIMAL SOLUTION FOUND
Integer optimization begins...
+     9: mip =   9,00000000E+000 <=   9,00000000E+000   0.0% (1; 0)
+     9: mip =   9,00000000E+000 <= tree is empty       0.0% (0; 1)
INTEGER OPTIMAL SOLUTION FOUND

If i use
lpx_integer()
X=3 Y=3 Z=3 b1=0 b2=0 b3=0

If i use
lpx_intopt()
X=3 Y=3 Z=3 b1=1 b2=1 b3=1

But both solutions don't fit equations.

Any ideas?

xypron wrote:
>
> 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
>> 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
>
>
> _______________________________________________
> Help-glpk mailing list
> http://lists.gnu.org/mailman/listinfo/help-glpk
>
>

--
View this message in context:
http://www.nabble.com/help-to-formulate-problem-in-terms-of-LP-tp16783186p16823521.html
Sent from the Gnu - GLPK - Help mailing list archive at Nabble.com.

```