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 << _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
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Gecode users mailing list users@gecode.org https://www.gecode.org/mailman/listinfo/gecode-users
