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-boun...@gecode.org [mailto:users-boun...@gecode.org] De la part de Sebastien Delmotte Envoyé : mardi 20 septembre 2016 10:37 À : cschu...@kth.se Cc : users@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:cschu...@kth.se] Envoyé : vendredi 16 septembre 2016 13:18 À : 'Sebastien Delmotte'; users@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, cschu...@kth.se Expert Researcher, SICS, cschu...@sics.se -----Original Message----- From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Sebastien Delmotte Sent: Friday, September 16, 2016 13:08 To: cschu...@kth.se; users@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:cschu...@kth.se] Envoyé : jeudi 15 septembre 2016 17:03 À : 'Sebastien Delmotte'; users@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, cschu...@kth.se Expert Researcher, SICS, cschu...@sics.se -----Original Message----- From: users-boun...@gecode.org [mailto:users-boun...@gecode.org] On Behalf Of Sebastien Delmotte Sent: Tuesday, September 13, 2016 14:55 To: users@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@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users _______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
