exists and forall operators

[Raid Alsoghayer]

Hello to you all

Can anybody help, please?

I am a student and I use the CPLEX 11.2 student edition for AMPL on Windows. I tried to use the operator exists, or forall, in a model. When I run the solve command AMPL stop working and Microsoft error report revealed with the usual information.

 

ampl.exe has encountered a problem and needs to close.  We are sorry for the inconvenience.

 

Is this a limitation of the student edition or my model is wrong? What I am trying to do is simple. Assign a task to one CPU from a list of CPUs. I want the task to be assigned to only one CPU, otherwise no solution exists, so I write the following condition:

 

subject to Time :exists {i in cpu} (ft[i]-st[i]) * speed[i] = p[index];

were ft := finishing time (var)

         st := starting time (var)

         speed := CPU speed (param)

         p := task processing time (param)

 

If I change exists to sum the model work fine. But when p is big more than one CPU from the list are used because of sum.

 

Regards,

Raid

 

 

[Paul]

The exists and forall operators are really intended to work with
parameters, not variables. They may work with variables after the
model is solved (and the variables have been assigned values) -- I've
never tried it, so I'm not positive -- but they are not suitable for
constraining variables.

If you want to require that expression(i) = constant for at least one
i in some set I, where expression(i) is an expression involving
variables as well as parameters, then you need to use the following
general approach:

1. introduce binary variables (I'll call them z) indexed by i over
some set I;
2. add constraints the -L*(1-z[i]) <= expression(i) - constant <= M(1-
z[i]) where L and M are sufficiently large positive constants (could
be the same but do not have to be); and
3. add the constraint sum{i in I} z[i] >= 1.

The constraints in (2) enforce (z[i] == 1) => (expression(i) =
constant). You need to choose L and M sufficiently large that
expression(i) will never be less than constant - L nor greater than
constant + M. Picking excessively large values will work but will
slow down the solver, so you want to shoot for big enough but not too
big, which is context-specific.

/Paul

On Jul 12, 2:29 pm, Raid Alsoghayer <rai...@gmail.com> wrote:
> Hello to you all
>
> Can anybody help, please?
>
> I am a student and I use the CPLEX 11.2 student edition for AMPL on Windows.

> I tried to use the operator *exists, or forall,* in a model. When I run the
> *solve* command AMPL stop working and Microsoft error report revealed with
> the usual information.
>
> *ampl.exe has encountered a problem and needs to close.  We are sorry for
> the inconvenience.*

>
> Is this a limitation of the student edition or my model is wrong? What I am
> trying to do is simple. Assign a task to one CPU from a list of CPUs. I want
> the task to be assigned to only one CPU, otherwise no solution exists, so I
> write the following condition:
>
> subject to Time :exists {i in cpu} (ft[i]-st[i]) * speed[i] = p[index];
>
> were ft := finishing time (var)
>
>          st := starting time (var)
>
>          speed := CPU speed (param)
>
>          p := task processing time (param)
>

> If I change *exists* to *sum* the model work fine. But when p is big more

[Raid20]

Dear Paul

Thank you for your reply, yet I didn’t get it right. When I add the
constraint:

subject to Time {i in cpu}: -L *(1-z[i]) <= ((ft[i]-st[i]) * speed[i])
- p[index] <= M*(1-z[i]);

I resive the following error:

nonconstant left-most expression in double inequality constraint
context: subject to Time {i in cpu}: -L *(1-z[i]) <= ((ft[i]-st[i]) *
speed[i]) - p[index] <= >>> M*(1-z[i]); <<<

nonconstant right-most expression in double inequality constraint
context: subject to Time {i in cpu}: -L *(1-z[i]) <= ((ft[i]-st[i]) *
speed[i]) - p[index] <= >>> M*(1-z[i]); <<<

I would be thankful if you could help me with this.

Regards,
Raid

> > Raid- Hide quoted text -
>
> - Show quoted text -

[Paul]

On Jul 13, 9:21 am, Raid20 <rai...@gmail.com> wrote:
>
> subject to Time {i in cpu}: -L *(1-z[i]) <= ((ft[i]-st[i]) * speed[i])
> - p[index] <= M*(1-z[i]);
>
> I resive the following error:
>
> nonconstant left-most expression in double inequality constraint

Split it into two separate sets of constraints. I believe that the
combined form a <= ... <= b only works if a and b are constant
expressions (hence the error message).

/Paul

[Raid20]

Dear Paul

Thank you for prompt reply. It seems what I am trying to do is wrong
since your suggestion solves the error but if I try to solve using
CPLEX I receive the error:

QP Hessian is not positive semi-definite

When I used MINOS I get a wrong solution. I limit my code to the
following:

set cpu;
set job;

param cost {cpu} > 0;
param speed {cpu} > 0;
param risk {cpu} > 0;
param A {cpu} >= 0;

param p {job} > 0; # the reqiuered time for the job
param T > 0; # the time limite
param R > 0; # the Risk limite
param V >=0; #the job arrival time

param index; # the index of the jobs
param y; # the index of the CPUs


var st {j in cpu} >= 0, <= T; # starting time
var ft {j in cpu} >= 0, <= T; # finishing time

param v {i in cpu} =
if V >= A[i] then V else A[i];#the starting time is set to largest
time when
# the CPU or the job is available

minimize Total_cost: sum {j in cpu} cost [j] * (ft[j]-st[j]);


subject to Time1 :sum {i in cpu} (ft[i]-st[i]) * speed[i] = p[index];
subject to Risk {i in cpu}: (ft[i]-st[i]) * risk[i] <= (ft[i]-st[i])
* R;
subject to test1 {i in cpu}: st[i] = v[i];

When I run this code I get the correct answer. What I am trying to do
is schedule a job with a given requirement (Processing time, Deadline,
Risk and Arrival time) on some CPUs with (Speed, cost, Risk and
Available time). My objective is to minimize the cost of scheduling on
the CPUs while insuring the job requirements are guaranteed. The above
code dose the job, but if the CPU available time is not enough to
complete the processing the Job is divided into two, or more, CPUs.
This is because of the use of sum.

I need to change this code so only one CPU is used and if no CPU
existed with enough available time then no solution is available. I
tried your method yet I think I get it wrong. The code I used is:

set cpu;
set job;

param cost {cpu} > 0;
param speed {cpu} > 0;
param risk {cpu} > 0;
param A {cpu} >= 0;

param p {job} > 0; # the reqiuered time for the job
param T > 0; # the time limite
param R > 0; # the Risk limite
param V >=0; #the job arrival time

param index; # the index of the jobs
param y;
var L :=10000;
var M := 10000;

var st {j in cpu} >= 0, <= T;
var ft {j in cpu} >= 0, <= T;
var z { i in cpu} binary;

param v {i in cpu} =
if V >= A[i] then V else A[i];

minimize Total_cost: sum {j in cpu} cost [j] * (ft[j]-st[j]);


subject to Time1 {i in cpu}: -L *(1-z[i]) <= ((ft[i]-st[i]) *
speed[i]) - p[index];
subject to Time2 {i in cpu}: ((ft[i]-st[i]) * speed[i]) - p[index] <=
M*(1-z[i]);

subject to Time3: sum{i in cpu} z[i] >= 1;

subject to Risk {i in cpu}: (ft[i]-st[i]) * risk[i] <= (ft[i]-st[i])
* R;
subject to test1 {i in cpu}: st[i] = v[i];

I know I am asking a great deal, thank you very much for your effort.
I hope you could help me to correct this problem

Regards,
Raid

[Robert Fourer]

It appears you should be defining L and M as param components rather than
var components. When they are defined as vars then the problem becomes
nonconvex quadratic, hence the error message from CPLEX.

Bob Fourer
4...@ampl.com

> --
> You received this message because you are subscribed to the Google
> Groups "AMPL Modeling Language" group.
> To post to this group, send email to am...@googlegroups.com.
> To unsubscribe from this group, send email to
> ampl+uns...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/ampl?hl=en.

[Raid20]

Hi
The model is working :) and I would like to thank you all for your
help. I couldn’t find an answer without your help. Thank you again and
best of luck…..

Regards,
Raid

> >http://groups.google.com/group/ampl?hl=en.- Hide quoted text -