Originally posted by: SystemAdmin

[shadi said:]

hi
im using the following code in order to save all my columns in the set of tuples

for (;;){
'
'
'
pairCst.add(size,cpModel.pay,bc,cpModel.drivingTime,cpModel.drivingDistance,cpModel.totalBreakTime,cpModel.totalBreakTime+cpModel.drivingTime);
'
'
}

in the end of my program this set will contains millions of tuples => huge memory consumption.

so i want to save all these tuples in a database, my question is:
how i can write a tuple from the .mod file and not from the .dat file??



Kshieboun Shadi
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[vblanchard said:]

Database instructions have to be in the .dat file. I am not sure I understand your question, why do you think that having DBUpdate (or DBExecute) calls in the .mod would save memory?
Can you detail what you're trying to achieve?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[shadi said:]

dear vblanchard,
im using the column generation method, in the slave model the sets become very big (millions of tuples)
so i reach very fast to the memory limitation.
i want to save these tuples on the disc or in the database (maybe then i can save a lot of memory).

i tried the first option, i saved the tuples on .dat file, it become very big (>1GB), BUT the problem now how can i use this file, in the master model, without loading it to the memory?????


Kshieboun Shadi.


#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[vblanchard said:]

My understanding is that if you need the tuples to solve your model, they have to be loaded in memory.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[jfk said:]

Ｈｅｌｌｏ　Ｓｈａｄｉ，
as far as I understood you have trouble because you generated all the columns at once and now the size of the master problem is too big.
have you thought of dynamically generating the columns? To outline the process:
1. initially generate enough columns so the (first) master problem has solution
2. then repeatedly generate new columns based on the reduced cost of the old ones. That is you put a constraint when you generate a new column ssaying that the reduced cost of the new one has to be better than the old ones. In this way you will generate better columns always
3. add the new column(s) to the master and solve it
4. goto no.2
5. in the meantime probably you should monitor the already generated columns and delete those which are never chosen (not chosen in the x last solving of the master or something like that)

this approach has 1 more benefit (beside dealing with the size-memory problem): you will get better performance. I can hear you saying that you have to solve repeatedly master problems meanwhile in your approach you have to solve just 1, though big master problem. well, in my experience the suggested approach has better performance. In fact CPLEX has the so called sifting algorithm for problems where the number of variables (columns) are significantly bigger than the number of constraints. The idea there as well is that they load columns which have better reduced cost value (the chance to improve the goal) and they report significant performance improvements. Besides if you can't load the master problem at all you may not have a choice.

I hope it helps

cheers
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[shadi said:]

Dear katai,
i think that you exactly understood my problem, yes i generated all the columns at once and the size of the master problem is too big.


i have some question related to the method that you just suggested:
1. how i can calculate the reduced cost of a new column?????
2. as far as I understood you i must solve the master each time I find a new column, right?
3. in the slave model (CP model) i have to add a new constraint (that use the reduced cost value of the column which trying to generate) but in the phase i still dont know this value (reduced cost), how i can do that???



I read the Crew Scheduling example which has the same form as our project, but unfortunately there is no implementation for the reduced cost criterium there, do you have an example or can you explain me more about this strategy?


thanks in advanced
Kshieboun Shadi

#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[jfk said:]

Hello Shadi,
A1. you don't compute reduced cost on a not existing (new) column. You post a constraint when you generate a new column that the reduced cost of this column should be negative (minimization).
A2. yes, with the correction that you may want to generate more than just 1 column before you solve the master.
A3. see A1 above + the reduced cost is basically used for a implex itself to choose which column (variable) should be in the basis (in a simplex you have all the columns so you can compute all of them and choose the biggest so the simplex can gain the biggest value improvement in the goal function, in your case you simply have to say that the new column's reduced cost has to improve the goal function, which means you require negativity). You know how to compute a reduced cost of a column (cNew - sum(dualvectorI*aINew) : cNew is the coefficient in the goal function for the new column, aINew is a coefficient for the ith constraint for the new column, and dualvector is the dual vector of the actual solution). aINew and cNew are in the slave model and are variables, meanwhile the dual vector is computed from your master prb. In a regular column generation problem this reduced cost is minimized that is, you want to improve your master model as much as you could. But in your case I suppose you have some other objective for your slave model so you just have to post a constraint saying that the reduced cost is less then 0, that is, the new column will be better than some in the master.

I hope it helps

cheers



#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[shadi said:]

Dear katai,
I implemented a similar algorithm, here is a peudo code of this algorithm:
for(,,){
findNewColumn()
addThisColumnToTheSetTuples()
lpModel.generate();

var lObj = lpConfig.cplex.getObjValue();
if(lObj < LastBetterObj){<br />LastBetterObj=lObj;
}
else{

DeleteTheLastAddedColumnsFromtheSetOfTuples();
}

}


Can I get the optimimum solution using this stratrgy??
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[shadi said:]

Dear Katai,
i think that the algorithm that i suggested never terminate, i started to implement the reduced cost critirion, i understand the general concept, but i have new questions again:
as far as I understood i have first to convert the integer master model to linear master model, then i can use the primal variable values and reduced costs for every variable and the dual variable values and slack values for the every constraint which come with the LP solution,
  1. how to get this values from the master model in order to be used in the slave model?????
  2. how to convert the master model to linear? just by converting all discrete variables to continuous,  i tried this option but i see that the model is still    integer (the pair array gives 0 and 1 only).

  3. the formulas that you suggested me to calculate the reduced cost is:
      (cNew - sum(dualvectorI*aINew) 
      where:cNew is the coefficient in the goal function for the new column,
                aINew is a coefficient for the ith constraint for the new column,
                and dualvector is the dual vector of the actual solution).
[list]
[li]  what do you mean goal function for the new column, the model which find new column is a cp model how to calculate the coefficient in the goal function ?[/li]
[li]can you give me an example how to calculate the reduced cost![/li]
[/list]
   


thanks in advanced
Kshieboun Shadi
   
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[shadi said:]

Dear Katai,
i implemented the algorithm but i still try to find the correct expression of the reduced cost, i added the following constraint to my cp model:

  cNew - (sum(i in Trips) (Duals[i]*flagTripInColumn[i])) < 0;<br />where:

cNew is: drivingDistance(NewColumn)*CostPerKm + BusPrice,

Duals[i] is the dual variables and i get it by using the following script code:
  for ( t=0; t<nbTrips; t++) {<br /> 
      if (cpData0.Origin[t]!=cpData0.Destination[t]) {
      cpData0.Duals[t] = lpModel.cvr[t].dual;

      }
  }
         

and flagTripInColumn[i] is 1 if the trip i is consist in the NewDuty and 0 otherwise,  I use the following to assign it:
    forall (t in Trips)
    flagTripInColumn[t] == sum (i in tripRng)(tripSeq[i] == t);



what i did wrong?

thanks in advanced
Kshieboun Shadi
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

[shadi said:]

hello,
I still stuck with the reduced cost formulas , i used the following constraint of the reduced cost:
cNew - sum(i in Trips)Duals[i]*flagTripInColumn[i] < 0;<br />
where:
cNew is: drivingDistance(NewColumn)*CostPerKm + BusPrice
            it is like the cost function that is use in the Lp model.

Duals is the dual variables and i get it by using the following script code in the main model:
    for ( t=0; t<nbTrips; t++) {<br />              if (cpData0.Origin[t]!=cpData0.Destination[t]) {
                cpData0.Duals[t] = lpModel.cvr[t].dual;

            }
      }


and flagTripInColumn[i] : as i understood is equal to 1 if the trip i included in the new columns and 0 otherwise, so i assign it using the following command:
    forall (tr in Trips)
    flagTripInColumn[table][tr][td] == sum (i in tripRng)(tripSeq[i] == tr);
is that right?????

i tried this constraint for a small timetable that i know the otptimum solution, but i didnt get the optimum solution.

im sorry why i write almost the same question,  i feel that im very closed to the solution and i need a help to achieve it...

thanks again
kshieboun shadi


#DecisionOptimization
#OPLusingCPOptimizer