(l,S) separation algorithm - valid inequalities

[Vasile Axel]

Dear All,

I'm struggling with the implementation of the (l,S) separation algorithm:

I wrote the following code:

set G;

set S{K};

option relax_integrality 1;

solve;

for{k in 1..g}

{

for{f in 1..n}

{

let S[k] := {};

for{t in 1..f}

{

if (Q[k,t] > dendp[k,t,f]*x[k,t]) then

{

let S[k] := S[k] union {t};

if sum{v in S[k]} Q[k,v] > (sum{v in S[k]} dendp[k,v,f]*x[k,v] + E[k,f]) then

{

let G := G union {(k,f,S[k])};

}

}

}

}

}

s.t. Inequalities{(k,f,S[k]) in G}: sum{t in S[k]} Q[k,t] <= sum{t in S[k]} dendp[k,t,f]*x[k,t] + E[k,f];

And I receive the following error message:

syntax error

context:  let G := G union  >>> {(k,f,S[ <<< k])};

I assume this error occurs because AMPL cannot deal with sets within sets?!

Does anyone has an idea how to execute the separation algorithm?

I want to implement only the valid inequalities within my model and this requires that I have to delete the inactive ones beforehand.

BR, Vasile

[AMPL Google Group]

Using the terminology of the mathematical statement of Algorithm 1, it appears to me that:

• There should be a set S for each combination of i and ell.
• The if statement at the end should be outside of the "for t = 1 . . ." loop.
• Each violated inequality is defined by an (i,ell) pair and the associated set S[i,ell].
• To keep a set of all violated inequalities, you only need to collect a set of (i,ell) pairs.

Definitely AMPL will not let you define a triple -- like "(k,f,S[k])" -- that consists of two numbers and a set. But I think you just need to save the two numbers, since you have a unique S-set corresponding to them.

It seems to me that you would have an easier time writing the separation algorithm in AMPL if you could use the same notation as in the mathematical statement, at least when you are starting out.

--
Robert Fourer
am...@googlegroups.com

{#HS:1435687651-101554#}

[Vasile Axel]

 Dear Mr Fourer,

Thank you for replying to my questions. I considered all of your recommendations from above and implemented the following code:

set G default {(1,1)}; #here I struggled to define a two-dimensional, you may give your advice on how to correct this?

let G := G diff {(1,1)};

set ell := 1..n;

set S{K,ell};

option relax_integrality 1;

solve;

for{k in K}

{

for{f in ell}

{

let S[k,f] := {};

for{t in 1..f}

{

if (Q[k,t] > dendp[k,t,f]*x[k,t]) then

{

let S[k,f] := S[k,f] union {t};

}

}

if (sum{v in S[k,f]} Q[k,v] > (sum{v in S[k,f]} dendp[k,v,f]*x[k,v] + E[k,f])) then

{

#let G := G union {S[k,f]}; #I tried both variants, just for reference; and I included the if-loop into the for-loop from above --> same result

let G := G union {(k,f)};

}

}

}

s.t. Inequalities{(k,f) in G}: sum{v in S[k,f]} Q[k,v] <= (sum{v in S[k,f]} dendp[k,v,f]*x[k,v] + E[k,f]);

After the execution of this code, I get the following error messages:

CPLEX 12.9.0.0: optimal solution; objective 2120.59987

151 dual simplex iterations (44 in phase I)

presolve, variable E[5,1]:

impossible deduced bounds: lower = 0, upper = -10

presolve, variable E[2,1]:

impossible deduced bounds: lower = 0, upper = -10

....... (and some more from this sort)

As you can see, I have the problem that doesn't know how to implement ONLY restrictions that meet the if-condition from above. (--> "Add the violated (l,S) inequality")

The algorithm from the paper which I'm trying to implement defines the inequalities as follows:

You may have another hint for me on how to add only the valid inequalities?

Thank you very much.

BR, Vasile

[AMPL Google Group]

I do not see any obvious problems with the logic of your loop or with your constraint "Inequalities {(k,f) in G}". The error that you're getting is that, after you add those inequalities, the problem has no feasible solution. To determine the cause, you could start by looking at the output of the AMPL command "expand Inequalities;" which shows exactly the constraints that were added; you can compare this to the constraints that you expected to generate.

Minor notes: To say that G is an empty two-dimensional sets (a set of pairs), you can write "set G dimen 2 default { };". . . . Your code treats all of the S[k,f] as one-dimensional sets, since you write "set S{K,ell};" and later you have "let S[k,f] := S[k,f] union {t};". Thus you cannot write "let G := G union {S[k,f]};" since it is taking the union of a two-dimensional set with a one-dimensional set. However, "let G := G union {(k,f)};" is a valid statement, and it appears to give what you want.

--
Robert Fourer
am...@googlegroups.com

{#HS:1435687651-101554#}

On Thu, Feb 25, 2021 at 10:39 PM UTC, AMPL Google Group <am...@googlegroups.com> wrote:

Using the terminology of the mathematical statement of Algorithm 1, it appears to me that:

• There should be a set S for each combination of i and ell.
• The if statement at the end should be outside of the "for t = 1 . . ." loop.
• Each violated inequality is defined by an (i,ell) pair and the associated set S[i,ell].
• To keep a set of all violated inequalities, you only need to collect a set of (i,ell) pairs.

Definitely AMPL will not let you define a triple -- like "(k,f,S[k])" -- that consists of two numbers and a set. But I think you just need to save the two numbers, since you have a unique S-set corresponding to them.

It seems to me that you would have an easier time writing the separation algorithm in AMPL if you could use the same notation as in the mathematical statement, at least when you are starting out.

--
Robert Fourer
am...@googlegroups.com