1 year ago
#110622
Med Tosby
Creating normally distributed Multi-dimensional Knapsack Problem (MKP) data from a basis one
I am trying to solve dynamic MKP for my thesis and I need to do the some calculations mentioned in the following passage of an article to create templates from a basis one:
2.3 The Dynamic MKP
In our study, we use a dynamic version of the MKP as proposed in [3] and described below. Basis is the first instance given in the file mknapcb4.txt which can be downloaded from [1]. It has 100 items, 10 knapsacks and a tightness ratio of 0.25. For every change, the profits, resource consumptions and the constraints are multiplied by a normally distributed random variable as follows:
pj ← pj ∗ (1 + N (0, σp))
rij ← rij ∗ (1 + N (0, σr))
ci ← ci ∗ (1 + N(0, σc))
Unless specified otherwise, the standard deviation of the normally distributed random variable used for the changes has been set to σp = σr = σc = 0.05 which requires on average 11 out of the 100 possible items to be added or removed from one optimal solution to the next. Each profit pj, resource consumption rij and constraint ci is restricted to an interval as determined in Eq. 11.
lbp ∗ pj ≤ pj ≤ > ubp ∗ pj
lbr ∗ rij ≤ rij ≤ ubp ∗ rij
lbc ∗ ci ≤ ci ≤ ubp ∗ ci
where lbp = lbr = lbc = 0.8 and ubp = ubr = ubc = 1.2. If any of the changes causes any of the lower or upper bounds to be exceeded, the value is bounced back from the bounds and set to a corresponding value within the allowed boundaries.
Link to full version of the above paper: https://web.itu.edu.tr/~etaner/evostoc06.pdf
And here is my C++ code to implement it:
void createTemplate()
{
double lb=0.8;
double ub=1.2;
double previous;
std::random_device generator;
default_random_engine eng{generator()};;
normal_distribution<double> distribution(0,0.05);
double number = distribution(generator);
//updating profits
for(int i=0;i<mkpInfo.numberOfItems;i++){
previous=mkpInfo.profits[i];
mkpInfo.profits[i]=mkpInfo.profits[i]*(1.0+number);
if(mkpInfo.profits[i]<previous*lb)
mkpInfo.profits[i]=lb*previous;
if(mkpInfo.profits[i]>ub*previous)
mkpInfo.profits[i]=ub*previous;
}
//updating weights
for(int i=0;i<mkpInfo.numberOfResources;i++)
{
for(int j=0;j<mkpInfo.numberOfItems;j++){
previous=mkpInfo.Rij[i][j];
mkpInfo.Rij[i][j]=mkpInfo.Rij[i][j]*(1.0+number);
if(mkpInfo.Rij[i][j]<previous*lb)
mkpInfo.Rij[i][j]=lb*previous;
if(mkpInfo.Rij[i][j]>ub*previous)
mkpInfo.Rij[i][j]=ub*previous;
}
}
//updating resources
for(int i=0;i<mkpInfo.numberOfResources;i++){
previous=mkpInfo.resources[i];
mkpInfo.resources[i]=mkpInfo.resources[i]*(1.0+number);
if(mkpInfo.resources[i]<previous*lb)
mkpInfo.resources[i]=lb*previous;
if(mkpInfo.resources[i]>ub*previous)
mkpInfo.resources[i]=ub*previous;
}
}
I have created 9 different environments by calling void createTemplate()
function according to the above code and solved them with CPLEX to find actual optimum values for each. Then, I tried to solve them with the algorithm that I developed for my thesis. Weirdly, either my algorithm is one of its kind, or I have done something really wrong while creating the templates. I mean I found very very good results according to previously studies in the literature. And I know my algorithm is fine because I have published it and solved similar problems before. For instance, the expression double number = distribution(generator);
always generates the same number in a run.
So, my questions are:
- Is it normal to generate the same number over and over with the above-mentioned code line?
- Considering the explanation in the article, am I doing right? Or I need to generate different random number for each variable in the data file? I mean do I need to put the expression
number=distribution(generator)
infor
loops?
genetic-algorithm
cplex
normal-distribution
evolutionary-algorithm
operations-research
0 Answers
Your Answer