Adding a new constraint at runtime

[Giotto]

Hi all,
I'm trying to implement a dynamic simplex in ampl using cplex as
solver. The goal is to add constraints as soon as I discover that they
are needed.
Substantially I'm going to execute a loop where I solve the problem
through a "solve" command and then I run another script (through a
"commands" command) that recognize if there is a violated constraint
that should be added. After this I've to insert this new constraint
and then execute a new iteration of the main loop. When the script
recognize that there is no new constraint to add, the loop finishes
and I display the solution.
I've defined a parameter called "constraints" that indicates the
number of actual constraints (starting from 0), and the constraint set
in this way:

param constraints;
param Constraints {1..constraints, 1..NUM_EDGES};
[...]
subject to ConstraintSet {i in 1..constraints}:
sum {j in 1..NUM_EDGES_NW} Constraints[i, j] * x[j] >= 1;

"Constraints" is a matrix where each row identifies a single
constraint. The script that adds the constraint does it in this way:

let constraints := constraints + 1;
for {k in 1..NUM_EDGES}
{
let Constraints[constraints, k] := 1 - min_cut[s, t, k];
}

The problem is that when I execute the second time the "solve" command
in order to solve the problem again with the new constraint added, I
discover that I've to add again the same constraint. In other words,
it seems that the new constraint is not considered by the solver,
because it's not possible that I have a solution that violates some of
the constraints.
How can I send the solver the new constraints? It would be an action
that I must execute every iteration of the loop.

Thank you in advance for your help

[sverkunoff]

Sounds like you are trying to change the model within the loop. One way to do it is to define the problem with all the constraints using 'subject to', then use 'drop' to turn off the ones you don't need, then use 'restore' to turn on the constraints as you go (for sintax/examples see p.214 of AMPL book)

Instead of having one problem and turning off/on the constraints, another way is to use 'problem' to define a series of named problems with different sets of constraints and then use 'solve' with the name of the problem that currently needs to be solved.

[Paul]

There's nothing structurally wrong with your approach (or at least as much as is shown in your post).  You defined Constraints as having second dimension 1..NUM_EDGES but summed over 1..NUM_EDGES_NW when defining constraints; I can't tell if that's deliberate or a typo.

You might try issuing the command 'expand ConstraintSet;' after the second solve, to see if (a) the second constraint is present and (b) it is what you expected.  If the second constraint is there but a duplicate of the first, then you have a bug elsewhere in your code.

/Paul

[Giotto]

On 19 Gen, 23:57, Paul <parubi...@gmail.com> wrote:
> There's nothing structurally wrong with your approach (or at least as much
> as is shown in your post).  You defined Constraints as having second
> dimension 1..NUM_EDGES but summed over 1..NUM_EDGES_NW when defining
> constraints; I can't tell if that's deliberate or a typo.

Sorry, it was a mistake, the 1..NUM_EDGES_NW should be 1..NUM_EDGES.

> You might try issuing the command 'expand ConstraintSet;' after the second
> solve, to see if (a) the second constraint is present and (b) it is what you
> expected.  If the second constraint is there but a duplicate of the first,
> then you have a bug elsewhere in your code.

I've tried to issue the 'expand' command and the constraints were all
there.
They were duplicated so I discovered a bug in my code and I solved it.
Now seem that it's working but I've another question. The problem that
I must
solve is defined as follows:

maximize TotalCapacity: sum {j in 1..NUM_EDGES} link_capacity[j] *
x[j];

subject to Budget:
sum {j in 1..NUM_EDGES} link_cost[j] * x[j] <= BUDGET;

subject to ConstraintSet {i in 1..constraints}:

sum {j in 1..NUM_EDGES} Constraints[i, j] * x[j] >= 1;

ConstraintSet is the set of constraints that I'm building at runtime.
I'm not sure about how to define x variables:

var x {i in 1..NUM_EDGES} >= 0, <= 1;
#var x {i in 1..NUM_EDGES} binary;

The set of constraints in ConstraintSet should assure me that if a
vector x
satisfies all constraints into this set, it must be an incidence
vector of
a covering graph of the original one (in other words the same graph
with a
subset of the edges such that the resulting graph is still connected).
Should I define x variables binary or continuous? I was thinking that
if a
vector x satisfies ConstraintSet then it must be an incidence vector
and so
it cannot hold fractional values, but it can only be a binary vector.
Unfortunately, declaring x continuous, cplex gives me a fractional
solution.
Is this due to the fact that ConstraintSet is built dinamically so
during the
execution it's not complete? So should I declare x as binary
variables?

Thanks again

[Paul]

On Thursday, January 20, 2011 9:25:09 AM UTC-5, Giotto wrote:

The problem that I must solve is defined as follows:

maximize TotalCapacity: sum {j in 1..NUM_EDGES} link_capacity[j] *
x[j];

subject to Budget:
sum {j in 1..NUM_EDGES} link_cost[j] * x[j] <= BUDGET;

subject to ConstraintSet {i in 1..constraints}:
sum {j in 1..NUM_EDGES} Constraints[i, j] * x[j] >= 1;

ConstraintSet is the set of constraints that I'm building at runtime.
I'm not sure about how to define x variables:

var x {i in 1..NUM_EDGES} >= 0, <= 1;
#var x {i in 1..NUM_EDGES} binary;

The set of constraints in ConstraintSet should assure me that if a vector x satisfies all constraints into this set, it must be an incidence
vector of a covering graph of the original one (in other words the same graph with a subset of the edges such that the resulting graph is still connected).
Should I define x variables binary or continuous?

Binary.

 

I was thinking that if a vector x satisfies ConstraintSet then it must be an incidence vector and so it cannot hold fractional values, but it can only be a binary vector. Unfortunately, declaring x continuous, cplex gives me a fractional solution.

This is what I would expect.
 

Is this due to the fact that ConstraintSet is built dinamically so during the execution it's not complete?

No, it's due to the nature of the formulation.  Without the constraints in ConstraintSet (and assuming you use continuous variables), you have a knapsack problem.  The solution will be to order the links in decreasing ratio of capacity to cost, set as many of them to 1 as you can (working first to last), and set the last one to whatever fraction consumes the final remnant of your budget.  The extra constraints in ConstraintSet may force you to turn on links not in the knapsack solution, but they won't prevent the solver from using a "fractional link" to polish off the budget.

So should I declare x as binary variables?

Yes, I don't see a way around that.

/Paul

[Giotto]

Thank you so much for the help.