[gecode-users] Cost optimization problem
Sebastien Delmotte
delmotte at mad-environnement.com
Thu Sep 22 11:59:02 CEST 2016
Dear All,
I'm back with my issue of cost optimization with float variables.
I can't solve my problem with integers because : (i) the transformation of
my model from float to integer makes me using coefficients with high value
which cause the overtaking of int size; (ii) even with smaller values, the
time of optimization is around 11h20 for optimizing only 6 coefficients (and
I have more to optimize).
So, I've tested another example: (i) I've taken the Hakank diet code
(http://www.hakank.org/gecode/) written with integer variables; (ii) I've
transformed the code to solve the model with float variables instead of
integer variables.
The result is similar than with my model: an exception occurs about
"unassigned variable" which is probably the cost variable. (I put the code
at the end of this message).
So it seems that the issue is not a modelling one. Do you have an idea about
the origin of this exception which occurs with the two models I've tested?
Do you known some other float optimization examples which are solved with
gecode?
Thank you in advance.
Best regards,
S. D.
Adapted Hakank Code:
#include <gecode/driver.hh>
#include <gecode/float.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
class Tests : public FloatMinimizeScript {
protected:
FloatVarArray x; // amount of each product
FloatVar t_cost; // total cost to minimize
static const int n = 4; // number of products
public:
Tests(const Options& o) :FloatMinimizeScript(o),
x(*this, n, 0, 1000),
t_cost(*this, 0, 1000)
{
float _price[] = { 50.f, 20.f, 30.f, 80.f}; // in cents
float limits[] = {500.f, 6.f, 10.f, 8.f}; // requirements for
each nutrition type
// nutritions for each product
float _calories[] = {400.f, 200.f, 150.f, 500.f};
float _chocolate[] = { 3.f, 2.f, 0.f, 0.f};
float _sugar[] = { 2.f, 2.f, 4.f, 4.f};
float _fat[] = { 2.f, 4.f, 1.f, 5.f};
FloatVarArgs v_calories;
FloatVarArgs v_chocolate;
FloatVarArgs v_fat;
FloatVarArgs v_sugar;
FloatVarArgs v_costs;
for(int i = 0;i<4;++i)
{
v_calories << expr(*this,x[i]*_calories[i]);
v_chocolate << expr(*this,x[i]*_chocolate[i]);
v_fat << expr(*this,x[i]*_fat[i]);
v_sugar << expr(*this,x[i]*_sugar[i]);
v_costs << expr(*this,x[i]*_price[i]);
}
rel(*this,expr(*this,sum(v_calories)),FRT_GQ,limits[0]);
rel(*this,expr(*this,sum(v_chocolate)),FRT_GQ,limits[1]);
rel(*this,expr(*this,sum(v_sugar)),FRT_GQ,limits[2]);
rel(*this,expr(*this,sum(v_fat)),FRT_GQ,limits[3]);
t_cost = expr(*this,sum(v_costs));
branch(*this, x, FLOAT_VAR_NONE(), FLOAT_VAL_SPLIT_MIN());
}
// Prfloat solution
virtual void
prfloat(std::ostream& os) const {
os << "\t" << x << " t_cost: " << t_cost << std::endl;
}
virtual FloatVar cost(void) const{
return t_cost;
}
Tests(bool share, Tests& s) : FloatMinimizeScript(share,s) {
x.update(*this, share, s.x);
t_cost.update(*this, share, s.t_cost);
}
virtual Space*
copy(bool share) {
return new Tests(share,*this);
}
};
float main(float argc, char* argv[]) {
Options opt("Test");
opt.solutions(1e9);
//opt.threads(8);
FloatMinimizeScript::run<Tests,BAB,Options>(opt);
return 0;
}
-----Message d'origine-----
De : users-bounces at gecode.org [mailto:users-bounces at gecode.org] De la part
de Sebastien Delmotte
Envoyé : mardi 20 septembre 2016 10:37
À : cschulte at kth.se
Cc : users at gecode.org
Objet : Re: [gecode-users] Cost optimization problem
Dear Christian,
I've tried to play with the step value but it doesn't change anything. An
exception related to an unassigned variable (cost) still occurs and it
prevents the search to be processed. I really don't understand why it works
with exactly the same code with floats converted to integers, but I surely
don't use correctly the gecode options.
I think I will continue with integers for the moment.
Thank you very much.
S. D.
-----Message d'origine-----
De : Christian Schulte [mailto:cschulte at kth.se] Envoyé : vendredi 16
septembre 2016 13:18 À : 'Sebastien Delmotte'; users at gecode.org Objet : RE:
[gecode-users] Cost optimization problem
Hi,
That's strange... Did you try to play with the step value as explained in
MPG 7.3?
Cheers
Christian
--
Christian Schulte, www.gecode.org/~schulte Professor of Computer Science,
KTH, cschulte at kth.se Expert Researcher, SICS, cschulte at sics.se
-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Sebastien Delmotte
Sent: Friday, September 16, 2016 13:08
To: cschulte at kth.se; users at gecode.org
Subject: Re: [gecode-users] Cost optimization problem
Dear Christian,
Thank you for your answer.
When I transform all the code from float variables to integer variables (in
changing the constraints from 1 to 100 for example), that works perfectly.
So maybe my implementation for float variables is not good. I will try to
find why.
Best regards,
SD
-----Message d'origine-----
De : Christian Schulte [mailto:cschulte at kth.se] Envoyé : jeudi 15 septembre
2016 17:03 À : 'Sebastien Delmotte'; users at gecode.org Objet : RE:
[gecode-users] Cost optimization problem
Hi,
Sorry but I think this is really a modelling issue and not a Gecode issue,
as you have already figured out 3).
Cheers
Christian
--
Christian Schulte, www.gecode.org/~schulte Professor of Computer Science,
KTH, cschulte at kth.se Expert Researcher, SICS, cschulte at sics.se
-----Original Message-----
From: users-bounces at gecode.org [mailto:users-bounces at gecode.org] On Behalf
Of Sebastien Delmotte
Sent: Tuesday, September 13, 2016 14:55
To: users at gecode.org
Subject: [gecode-users] Cost optimization problem
Dear All,
I have a problem with using Gecode to solve an optimization problem.
Problem description:
- I have a recipe with two sub-components. Each component has a coefficient
corresponding to its amount in the recipe. So the sum of the sub-components
coefficients must be equal to 1;
- Each of the two sub-components is composed of several raw materials. Each
raw material has a coefficient corresponding to its amount in its
sub-component. So, for each sub-component, the sum of the raw materials
coefficients is equal to 1;
- At the recipe level, I have some constraints on the raw materials amount
(e.g. raw material 1 must be in a given interval). The amount of each raw
material in the recipe is equal to the product of the coefficient of this
raw material by the coefficient of its sub-component
- I have to minimize the cost of the recipe accounting for the cost of each
raw materials. This cost is equal to the sum of the product of each raw
material coefficient by its unit cost.
Code
#include <gecode/driver.hh>
#include <gecode/int.hh>
#include <gecode/minimodel.hh>
using namespace Gecode;
class Tests : public FloatMinimizeScript {
protected:
FloatVarArray _rms_in_sub_c_1; // raw mat in sub-comp1
FloatVarArray _rms_in_sub_c_2; // raw mat in sub-comp2
FloatVarArray _sub_c; // 2 sub-comp
FloatVar _cost; // cost
public:
Tests(const Options& o)
:FloatMinimizeScript(o),_rms_in_sub_c_1(*this,4,0,1),_rms_in_sub_c_2(*this,3
,0,1),_sub_c(*this,2,0,1),_cost(*this,0,1000)
{
//sum of raw mat in sub-comp =1
FloatVar all_rms_sub1 = expr(*this,sum(_rms_in_sub_c_1));
rel(*this,all_rms_sub1 ,FRT_EQ,1);
FloatVar all_rms_sub2 = expr(*this,sum(_rms_in_sub_c_2));
rel(*this,all_rms_sub2 ,FRT_EQ,1);
// sum of sub-comp =1
FloatVar sm = expr(*this,sum(_sub_c));
rel(*this,sm ,FRT_EQ,1);
// Global constraints on raw mat in recipe FloatVar rm_0_sub_coef1=
expr(*this,_rms_in_sub_c_1[0]*_sub_c[0]);
rel(*this,rm_0_sub_coef1,FRT_GQ,0);
FloatVar rm_1_sub_coef1= expr(*this,_rms_in_sub_c_1[1]*_sub_c[0]);
rel(*this,rm_1_sub_coef1,FRT_GQ,0);
FloatVar rm_2_sub_coef1= expr(*this,_rms_in_sub_c_1[2]*_sub_c[0]);
rel(*this,rm_2_sub_coef1,FRT_GQ,0);
FloatVar rm_3_sub_coef1= expr(*this,_rms_in_sub_c_1[3]*_sub_c[0]);
rel(*this,rm_3_sub_coef1,FRT_GQ,0);
FloatVar rm_0_sub_coef2= expr(*this,_rms_in_sub_c_2[0]*_sub_c[1]);
rel(*this,rm_0_sub_coef2,FRT_GQ,0);
FloatVar rm_1_sub_coef2= expr(*this,_rms_in_sub_c_2[1]*_sub_c[1]);
rel(*this,rm_1_sub_coef2,FRT_GQ,0);
FloatVar rm_2_sub_coef2= expr(*this,_rms_in_sub_c_2[2]*_sub_c[1]);
rel(*this,rm_2_sub_coef2,FRT_GQ,0);
// Cost
_cost = expr(*this,_sub_c[0]*(_rms_in_sub_c_1[0]*12 +_rms_in_sub_c_1[1]*14 +
_rms_in_sub_c_1[2] * 22 +_rms_in_sub_c_1[3] * 17 )
+_sub_c[1]*(_rms_in_sub_c_2[0]*9 +_rms_in_sub_c_2[1]*2 +
+_rms_in_sub_c_2[2]
* 18 ));
FloatVarArgs all;
for(int i = 0; i <4; i++) all << _rms_in_sub_c_1[i]; for(int i = 0; i <3;
i++) all << _rms_in_sub_c_2[i]; for(int i = 0; i <2; i++) all <<
i++_sub_c[i];
branch(*this, all, FLOAT_VAR_NONE(), FLOAT_VAL_SPLIT_MIN());
}
virtual void
print(std::ostream& os) const {
os << "sub-component : " << _sub_c << "\nrms 1 : "<< _rms_in_sub_c_1<<
"\nrms2 : "<< _rms_in_sub_c_2 <<"\ncost : "<< _cost << std::endl;
}
virtual FloatVar cost(void) const{
return _cost;
}
Tests(bool share, Tests& s) : FloatMinimizeScript(share,s) { _sub_c.update
(*this, share, s._sub_c); _rms_in_sub_c_1.update(*this, share,
s._rms_in_sub_c_1); _rms_in_sub_c_2.update(*this, share, s._rms_in_sub_c_2);
_cost.update(*this, share, s._cost);
}
virtual Space*
copy(bool share) {
return new Tests(share,*this);
}
};
int main(int argc, char* argv[]) {
Options opt("Test");
opt.solutions(0);
FloatMinimizeScript::run<Tests,BAB,Options>(opt);
return 0;
}
When executing this code, the result is :
sub-component : {0, 1}
rms in sub-component 1 : {0, 0, 0, 1}
rms in sub-component 2 : {0, 0, 1}
cost : [18..18]
Exception: FloatVar::val: Attempt to access value of unassigned variable.
Problems:
1- The resulting solution is trivial but absolutely not optimal for the
cost: only the second sub-component has a positive coefficient (=1) with
only one raw material which is not the cheapest one;
2- In this example, all the constraints for the raw materials are: greater
than 0. But if I change the value of the constraints (e.g. greater than
0.1), I don't get any solution;
3- There is an exception error: FloatVar::val: Attempt to access value of
unassigned variable. This error disappears when I add the variable cost in
the branching, but the solution is still non optimal.
I think I have a problem with handling gecode because the problem is simple,
but I have no idea about the origin of the problem.
With many thanks in advance.
Best regards,
S.D.
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
_______________________________________________
Gecode users mailing list
users at gecode.org
https://www.gecode.org/mailman/listinfo/gecode-users
More information about the users
mailing list