Re: [Help-glpk] [Fwd: Help demand]

[Jeffrey Kantor]

Hi Alexandre,

The model appended below captures the logic of your problem.  This is a direct translation of your problem logic into MathProg using standard techniques (for example, see http://moya.bus.miami.edu/~tallys/docs/logical-expr.pdf or http://archive.ite.journal.informs.org/Vol3No3/ChlondToase/index.php).  This model assumes X, Z, W, and K are integer variables.

You can verify by cutting and pasting into http://www3.nd.edu/~jeff/mathprog/mathprog.html

Caveat emptor.

Jeff

var X, integer, >= 1, <= 60;

var Z, integer, >= 1, <= 60;

var W, integer, >= 1, <= 10;

var K, integer, >= 1, <= 10;

var y, binary;

param M := 100;

param eps := 0.01;

# A <=> (X>Z)

var A, binary;    

s.t. A1: X - Z >= eps - M*(1-A);

s.t. A2: X - Z <= M*A;

# B <=> (Z>X)

var B, binary; 

s.t. B1: Z - X >= eps - M*(1-B);

s.t. B2: Z - X <= M*B;

# C <=> (W>K)

var C, binary;  

s.t. C1: W - K >= eps - M*(1-C);

s.t. C2: W - K <= M*C;

# D <=> (K>W)

var D, binary;

s.t. D1: K - W >= eps - M*(1-D);

s.t. D2: K - W <= M*D;

# y => not(A) and not(B) and not(C) and (not(D))

s.t. a: A + y <= 1;

s.t. b: B + y <= 1;

s.t. c: C + y <= 1;

s.t. d: D + y <= 1;

# not(y) => A or B or C or D

s.t. e: A + B + C + D + y >= 1;

maximize obj: X + Z + W + K;

solve;

end;

On Mon, Feb 11, 2013 at 7:53 AM, Andrew Makhorin <address@hidden> wrote:

-------- Forwarded Message --------
From: Alexandre Saidi <address@hidden>
To: glpk <address@hidden>
Cc: Alexandre Saidi <address@hidden>, Andrew Makhorin
<address@hidden>
Subject: Help demand
Date: Mon, 11 Feb 2013 10:14:48 +0100

Dears,
I've been fighting some (few) quarters with the translation of the following constraint into GLPK.
If anybody can help with a working answer :

trying to translate efficiently the "element" CP constraint to GLPK, I've the following (simpler) constraints that i want to translate (but let's forget "element" for now) :

                (binary_y = 1) <=> (X = Z and W = K)            every thing is  variable.

X,Z are bounded (1..60), W,K are also bounded (1..10, they are vector indices)

That's, if I ever have binary_y = 1, I want to put 2 pairs of variables equal. 'and' is a logical connector and '<=>' stands for 'equivalent' (double 'implies').
In fact, I'm working with a problem with 20000 variables and many many constraints. So the 'performance' is a critical issue.

I know that the 'element' constraint has been studied but those general solutions did not work (efficiently) for me.
A translation by the BigM method is welcome (apart from all cons of that method).

regards

Alex


 -------------------------------
Alexandre Saidi
Maitre de Conférences
Ecole Centrale de Lyon-Dép. MI
LIRIS-CNRS UMR 5205
Tél : 0472186530, Fax : 0472186443










_______________________________________________
Help-glpk mailing list
address@hidden
https://lists.gnu.org/mailman/listinfo/help-glpk