help-glpk
[Top][All Lists]

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

 From: Jeffrey Kantor Subject: Re: [Help-glpk] [Fwd: Help demand] Date: Mon, 11 Feb 2013 10:45:37 -0500

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 wrote:
-------- Forwarded Message --------
Cc: Alexandre Saidi <address@hidden>, Andrew Makhorin
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