title: Precedence constrainted biknapsack
body: <p>I don't have a stong background in combinatorial optimization nor programming and I have to write some code to solve the bi knapsack (2 capacities ) with constraints of precedence.. I've been working on it for 3 months now and I can't debug it and find out why it doesn't return the right answers yet ... I used a CONCERT configuration on C++</p>
  
  <p>So here's how my program works :</p>
  
  <p>First I solve the linear relaxation using CPLEX, the output returns the value of the objective function + the index of the fractional variable + a variable that indicates if the relaxation is feasible + a variable that indicates if all variables are integer .</p>
  
  <p>Second I implemented a branch and bound function that does a BFS tree search</p>
  
  <p>so first it verifies if the relaxation is feasible and then if it is and there are fractional variables it branches on them ..</p>
  
  <p>each node has 2 caracteristics : its bound which means the value of the relaxation in this node + a list of values indicating if the decision was taken on a variable or not ( it is equal to 0 if we decide not to pick the element , 1 if we decide to pick it, and 2 if we have not yet taken any decision ...)</p>
  
  <p>So here's my code , problem is it branches ONLY on the first node </p>
  
  <pre><code>#include &lt;queue&gt;
  #include&lt;cmath&gt;
  #include&lt;ilcplex/ilocplex.h&gt;
  #include &lt;iostream&gt;
  #include&lt;typeinfo&gt;
  using namespace std;
  
  IloEnv env;
  IloCplex cplex;
  IloModel model;
  
  
  struct node
  {
      double bound;
      int val[100];
      int profit;
  
  };
  
  
  /***************************BORNE***************************/
  
  
  double *bound(node u,int T,int W,int n,int Pre[],int CapaciteTemps[],int CapaciteSac[],int CoutObj[]){
  
      int indicefrac=0;
      double *resultat=new double[4];
  
      try{
          env = IloEnv();
          model=IloModel(env);
  
  
          //définition des variables de décision
          IloNumVarArray x(env,n);
          for (IloInt i=0; i&lt;n;i++){
              x[i]=IloNumVar(env);
          }
  
  
          //contrainte 1: Capacité temps
          IloExpr Contr1(env);
          for (IloInt i=0; i&lt;n;i++){
  
              Contr1 += CapaciteTemps[i]*x[i];
  
          }
  
          model.add(Contr1&lt;=T);
  
  
  
          //contrainte 2: Capacité volume
          IloExpr Contr2(env);
          for (IloInt i=0; i&lt;n;i++){
  
              Contr2 += CapaciteSac[i]*x[i];
          }
          model.add(Contr2&lt;=W);
  
  
          //contrainte 3: Relaxation des variables entre 0 et 1 les variables peuvent prendre des valeurs continues mais que sur l'intervalle 0,1
  
          for (IloInt i=0; i&lt;n;i++){
              model.add(0&lt;=x[i]&lt;=1);
          }
  
  
          //contrainte 4: Contrainte de précédence si l'on veut prendre un élément il faut avoir nécéssairement avoir pris tout ses prédécesseurs
  
  /*
          for(IloInt i=0;i&lt;n;i++)
          {
              for(IloInt j=0;j&lt;n;j++){
  
                  if(Pre[i]&lt;=Pre[j])
  
                  {
                      model.add(x[i]&gt;=x[j]);
                  }
  
              }
          }
  
  
  
  */
  
          //élément pris ou non on force sa valeur a être égale à 0 ou à 1
  
          for (IloInt i=0;i&lt;n;i++){
              if(u.val[i]==0){
                  model.add(x[i]&lt;=0);}
              else if(u.val[i]==1){
                  model.add(x[i]&gt;=1);
              }
  
  
          }
  
          //fonction objectif
          IloExpr obj(env);
          for (IloInt i=0;i&lt;n;i++){
              obj += CoutObj[i]*x[i];
          }
          model.add(IloMaximize(env,obj));
  
          cplex=IloCplex(model);
  
          cplex.solve();
  
  
          //affichage de la valeur des variables
  
  
  
          for(IloInt i=0; i&lt;n; i++){
              cout&lt;&lt;"x["&lt;&lt;i&lt;&lt;"]= "&lt;&lt;cplex.getValue(x[i])&lt;&lt;endl;
          }
  
          if ( ! (cplex.getStatus() == IloAlgorithm::Infeasible ) ) {
              bool isfractionnelb=false;
              double isfractionneli;
  
              for(IloInt i=1;i&lt;n;i++){
  
                  if(cplex.getValue(x[i]) != (int)cplex.getValue(x[i]))
                      isfractionnelb=true;
              }
  
  
              if(isfractionnelb==true){
                  for(IloInt i=1;i&lt;n;i++){
  
  
                      if(abs(cplex.getValue(x[i])-0.5)&lt;abs(cplex.getValue(x[indicefrac])-0.5) ){
                          indicefrac=i;
                      }
                  }
              }
  
  
              if(isfractionnelb==true)
              {isfractionneli=1;}
              else{isfractionneli=0;}
  
  
  
              resultat[0]=cplex.getObjValue(); // borne , valeur de la relaxation
              resultat[1]=(double)indicefrac;  //indice fractionnaire
              resultat[2]=isfractionneli; // indique si une valeur fractionnaire existe après la relaxation
              resultat[3]=1;  // indique si la relaxation linéaire est réalisable
  
  
          }
          if (  (cplex.getStatus() == IloAlgorithm::Infeasible ) ){cout&lt;&lt;"infeasable";}
  
  
  
      }catch(IloException&amp; e){
  
  
          e.print(cout);
  
  
      }
  
  
      return resultat;
  
  }
  
  
  
  
  int knapsack(int n, int p[],int t[],int T,int w[], int W, int Pre[])
  {
      queue&lt;node&gt; Q;
      node v,ug,ud;
      vector&lt;int&gt; pV;
      vector&lt;int&gt; wV;
      vector&lt;int&gt; tV;
      vector&lt;int&gt; tPre;
      Q.empty();
  
      double *borneg;
      double *borned;
  
  
  
      for (int i = 0; i &lt; n; i++)
      {
          pV.push_back(p[i]);
          wV.push_back(w[i]);
          tV.push_back(t[i]);
          tPre.push_back(Pre[i]);
      }
  
  v.profit=0;
  
      for(int i=0;i&lt;n;i++)
      {v.val[i]=2;}
  
      int maxProfit = 0;
  
      double *borne=bound(v,T, W, n,Pre, t, w, p) ;
      v.bound=borne[0];
      cout&lt;&lt;"borne "&lt;&lt;borne[0]&lt;&lt;endl;
  
  
      if(borne[2]==1){
          cout&lt;&lt;"indice fractionnaire : "&lt;&lt;borne[1]&lt;&lt;endl;}
      Q.push(v); // adds at top of list
  
  
      if( borne[3]==1 ){
          if(borne[2]==0){
              cout&lt;&lt;"la solution optimale est : "&lt;&lt;endl;
              maxProfit=borne[0];
              v = Q.front(); // reference a l'élement suivant dans la liste
              Q.pop(); // supprime l'élément suivant de la liste
          }
  
          else{
              // v = Q.front(); // reference a l'élement suivant dans la liste
              // Q.pop(); // supprime l'élément suivant de la liste
              //Q.push(v); // adds at top of list
  
              while (!Q.empty())
              {
  
                  v = Q.front(); // reference a l'élement suivant dans la liste
                  Q.pop(); // supprime l'élément suivant de la liste
  
                  cout &lt;&lt; "Noeud courant:";
                  for(int i = 0 ; i &lt; n ; ++i)
                      cout &lt;&lt; " " &lt;&lt; v.val[i];
                  cout &lt;&lt; endl;
                  cout &lt;&lt; "Objet fractionnaire: " &lt;&lt; borne[1] &lt;&lt; endl;
  
  
                  int indice=(int)(borne[1]);
  
                  node ug;
                  node ud;
                  int k[n];
  
  for(int i=0;i&lt;n;i++)
  {
  if (ud.val[i]==0)
  k[i]=0;
  else if (ud.val[i]==1)
  k[i]=1;
  else
  k[i]=0;
  }
  
  for(int i=0;i&lt;n;i++)
  {ud.profit+=p[i]*k[i];}
  for(int i=0;i&lt;n;i++)
  {
      int k[n];
  if (ug.val[i]==0)
  k[i]=0;
  else if (ug.val[i]==1)
  k[i]=1;
  else
  k[i]=0;
  
  }
  
  for(int i=0;i&lt;n;i++)
  {ug.profit+=p[i]*k[i];}
  
                  for(int i=0;i&lt;n;i++)
                  {ug.val[i]=v.val[i];
                  ug.val[indice]=1;
                  }
  
  
                  for(int i=0;i&lt;n;i++)
                  {ud.val[i]=v.val[i];}
                  ud.val[indice]=0;
  
  
                  borneg=bound(ug,T, W, n,Pre, t, w, p) ;
                  borned=bound(ud,T, W, n,Pre, t, w, p) ;
  
  
  
  cout&lt;&lt;"borne fils gauche"&lt;&lt;borneg[0]&lt;&lt;endl;
  cout&lt;&lt;"borne fils droite"&lt;&lt;borned[0]&lt;&lt;endl;
  
  
                  if(borned[3]==1)
                  {if (borned[2]==0){
  if(ud.profit&gt;maxProfit)
  {maxProfit=ud.profit;}
                      if (borned[0]&gt;maxProfit)
                      {
  
                       borne[1]=borned[1];
              //  for(int i=0;i&lt;n;i++)
                          //      {v.val[i]=fil[1].val[i];}
                           //     v.bound=fil[1].bound;
  Q.push(ud);
                      }
  
                  }
  
                  }
  
              //  else {ud = Q.front(); // reference a l'élement suivant dans la liste
              //  Q.pop();
              //  cout&lt;&lt;"aaaaa";}
  
  
                  if(borneg[3]==1)
                  {if (borneg[2]==0){
                      if(ug.profit&gt;maxProfit)
                      {maxProfit=ug.profit;}
  
                      if (borneg[0]&gt;maxProfit)
                      {Q.push(ug);
                      borne[1]=borneg[1];
  
              //      for(int i=0;i&lt;n;i++)
              //      {v.val[i]=fil[0].val[i];}
               //     v.bound=fil[0].bound;
                 //   borne[1]=borneg[1];
                      }
                  }
  
                  }
  
                  //else {
                  //ug = Q.front(); // reference a l'élement suivant dans la liste
                  //Q.pop();
                  //}
  
  cout&lt;&lt;"debug1"&lt;&lt;endl;
  
  
              }
              cplex.exportModel("/net/cremi/sbounejmate/prog1.lp");
  
          }}
      else{cout &lt;&lt;"problème irréalisable"&lt;&lt;endl;
      maxProfit =0;
  
      }
  
      return maxProfit;
  }
  
  int main()
  {
  
      vector&lt;int&gt; pV;
      vector&lt;int&gt; wV;
      vector&lt;int&gt; tV;
      vector&lt;int&gt; tPre;
      int n = 6;
      int W = 6;
      int T= 3;
      int p[6]= {15,5,15,15,3,5};
      int w[6]= {1,5,5,10,2,3};
      int t[6]={2,1,3,2,2,3};
      int Pre[6]={1,1,5,1,18,1};
      for (int i = 0; i &lt; n; i++){
          pV.push_back(p[i]);
          wV.push_back(w[i]);
          tV.push_back(t[i]);
      }
  
      //double *b=bound(u,T, W, n, t, w, p) ;
      int k=knapsack(n,p,t,T,w,W,Pre);
      cout&lt;&lt;"knapsack"&lt;&lt;k&lt;&lt;endl;
  
      //cout&lt;&lt;"La valeur de la relaxation de l'objectif est : "&lt;&lt;b[0]&lt;&lt;endl;
      //cout&lt;&lt;"L'indice fractionnaire le plus proche de 0.5 est : "&lt;&lt;b[1]&lt;&lt;endl;
  
  
      return 0;
  
  
  }
  </code></pre>
  
  <p>I'd be very grateful if you help me find out where my logic went wrong</p>