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

[Dima Ry]

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 = not found yet     <= +inf                     (1; 0)
+     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
>> 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
> 
> 
> _______________________________________________
> Help-glpk mailing list
> address@hidden
> 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.