Topic
  • 4 replies
  • Latest Post - ‏2014-04-02T12:29:13Z by DanielJunglas
prasenjit mandal
prasenjit mandal
7 Posts

Pinned topic Generating cover Inequality for a 0-1 Knapsack problem and adding it to the problem using concert technology

‏2014-03-27T18:28:01Z |

I am new to CPLEX. I need help. I shall be highly obliged for that.

I am facing a problem to implement cut generation procedure in C++-Cplex concert. I was trying to generate the cover inequality and then adding it as another additional constraint to the Knapsack Problem.

Here are the steps I am following :

  1. Constructing a sample 0-1 Knapsack Problem.
  2. Relaxing the IP as LP and solving it to get a fractional solution.
  3. Now, I was trying to use USERCUTCALLBACK to generate cut. I followed a greedy heuristic to generate a sample cover inequality. So, firstly I sorted the a_j (the co-efficients in the knapsack constraints) value in non-ascending order. I tool a cover vector which consists of first K number of x-variables for which sum_(j in K) a_j > b. Then, I tried to add that cover to the model (in cplex), but I was unsuccessful to do so.

 

The code is not executing the part which are inside of the ILOUSERCUTCALLBACK5. When I tried to run the code without the ILOUSERCUTCALLBACK5,it was working fine, showing me the LP relaxed value. But, I feel that I did a mistake somewhere in the ILOUSERCUTCALLBACK5 part.

Could you Please help me to figure out what I can I do correct my code. I am herewith attaching the .cpp file.

 

**********************************************************

KnapsackItem.h

 

#ifndef KNAPSACKITEM_H
#define    KNAPSACKITEM_H

class KnapsackItem {
    
private:
    size_t idx;
    int value;
    int weight;
public:
    KnapsackItem (size_t idx_, int value_, int weight_) {
        idx= idx_;
        value = value_;
        weight = weight_;
    }
    
public:
    size_t getIDx () const {
        return idx;
    }
    
    int getValue () const {
        return value;
    }
    
    int getWeight () const {
        return weight;
    }
};

#endif    /* KNAPSACKITEM_H */

 

 

 

 

 

 

 

 

 

Main.cpp

#include <ilcplex/ilocplex.h>
#include <iostream>
#include <vector>
#include <algorithm>

#include "KnapsackItem.h"

ILOSTLBEGIN

#define epsilon 0.0000001
#define epsilon2_ 0.000000001

IloInt numCuts = 0;

vector<KnapsackItem> knapsackConstraint;

bool compareWeight (const KnapsackItem &item1, const KnapsackItem & item2 ) {
    
    return (item1.getWeight() > item2.getWeight() );
}

ILOUSERCUTCALLBACK5(greedyCoverCuts, IloModel, model, vector<KnapsackItem>, krow, IloNumArray, Xstar,IloInt, b, IloNumVarArray, Xvar) {
    try{
        IloInt j; 
        IloEnv env = getEnv();
        vector<KnapsackItem> cover;
        vector<KnapsackItem> remainder;

        vector<KnapsackItem> sortedKnapsack(krow);

        sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

        double greedyElementSum = 0.0;
        double greedyXstarSum = 0.0;


        env.out() << "1"  << endl;

        for (j = 0; j < sortedKnapsack.size(); j++) {
            // if Xstar is fractional and no cover cuts yet, consider it for the cover
            if ( (Xstar[sortedKnapsack[j].getIDx()] >= epsilon) && 
                (Xstar[sortedKnapsack[j].getIDx()] <= 1 - epsilon) &&
                !numCuts) {
                    greedyElementSum += sortedKnapsack[j].getWeight();
                    greedyXstarSum += Xstar[sortedKnapsack[j].getIDx()];

                    cover.push_back(KnapsackItem(sortedKnapsack[j].getIDx(),sortedKnapsack[j].getValue(),sortedKnapsack[j].getWeight()));

                    if (greedyElementSum > b + epsilon2_) {
                        numCuts = 1;
                    }
            }

            else {
                remainder.push_back(KnapsackItem(sortedKnapsack[j].getIDx(),sortedKnapsack[j].getValue(),sortedKnapsack[j].getWeight()));
            }
        }

        int size = remainder.size() + cover.size();;
        int krowsize = sortedKnapsack.size();
        assert (size == krowsize);

        
        //if no violated minimal cover

        if ( (greedyXstarSum <= (cover.size() -1) + epsilon2_) ||
             (!numCuts) ||
             (cover.size() < 2) ) {
                 throw (-1);
        }
        else {
         IloInt coverrhs = cover.size() - 1;

         
          IloExpr expr(env);
          for(j = 0; j < cover.size(); j++) {
             //model.add(IloScalProd(weight, pickItem) <= capacity);
             expr += cover[j].getWeight()*Xvar[cover[j].getIDx()];
             env.out() << "index: " << cover[j].getIDx() << "Element Weight: " << cover[j].getWeight();
          } 

          env.out() << "RHS : " << coverrhs << endl;
          model.add(expr <= coverrhs);
          expr.end();
        }

    }
    catch (IloException &e){
        cerr<<"Error in callback: "<< e << endl;
        throw;
    }

}

void knapsackLPSolve (IloNumArray& Xstar, 
    vector<KnapsackItem>& knapsackConstraint,
    IloInt capacity,
    IloInt nbItem) {
    IloEnv env;
   try {
      IloInt i;


      //Create the variables
      IloNumVarArray pickItem(env, nbItem, 0, 1, ILOFLOAT);

      //create Model
      IloModel model(env);

      IloExpr expr(env);
      for(i = 0; i < nbItem; i++) {
         //model.add(IloScalProd(weight, pickItem) <= capacity);
         expr += knapsackConstraint[i].getWeight()*pickItem[i];
      }
      model.add(expr <= capacity);
      expr.end();

      
      
      //IloExpr obj = IloScalProd(value, pickItem);
      IloExpr obj(env);
      for(i = 0; i < nbItem; i++) {
         obj += knapsackConstraint[i].getValue()*pickItem[i];
      }
      model.add(IloMaximize(env, obj));
      obj.end();

      IloCplex cplex(env);


      //vector<KnapsackItem> sortedKnapsack(knapsackConstraint);
      //sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

      /*for(int x =0; x < sortedKnapsack.size(); x++) {
        cout << "Sorted Item ID: " << sortedKnapsack[x].getIDx()
                << "Value: " << sortedKnapsack[x].getValue()
                << "Weight: " << sortedKnapsack[x].getWeight()
                << endl;
      }*/

      //cplex.use(greedyCoverCuts(env, model, sortedKnapsack, capacity, pickItem));
      
      cplex.out() << "extracting model ..." << endl;
      cplex.extract(model);

      cplex.exportModel("knapsack.lp");

      cplex.solve();

      //cplex.setParam(IloCplex::Param::MIP::Interval, 1000);
      //cplex.setParam(IloCplex::Param::MIP::Strategy::Search, IloCplex::Traditional);
    
      cplex.out() << "Solution status: " << cplex.getStatus() << endl;

      IloNum tolerance = cplex.getParam(IloCplex::Param::MIP::Tolerances::Integrality);
      cplex.out() << "Optimal value: " << cplex.getObjValue() << endl;
      cplex.getValues(Xstar, pickItem);
      
   }
   catch(IloException& e) {
      cerr  << " LP relaxation ERROR : " << e << endl;   
   }
   catch(...) {
      cerr  << "LP relaxation ERROR" << endl;   
   }
   env.end();
}

int
main(int argc, char **argv)
{
   IloEnv env;
   try {
      IloInt i;

      IloInt capacity;
      IloIntArray value(env), weight(env);

      IloInt      nbItem;

      const char* filename  = "knapsack.dat";
      if (argc > 1) 
         filename = argv[1];
      ifstream file(filename);
      if (!file) {
         cerr << "ERROR: could not open file '" << filename
              << "' for reading" << endl;
         cerr << "usage:   " << argv[0] << " <file>" << endl;
         throw(-1);
      }

      file >> value >> weight >> capacity;
      nbItem = value.getSize();

      IloBool consistentData = (weight.getSize() == nbItem);
      if (!consistentData) {
         cerr << "ERROR: data file '" 
              << filename << "' contains inconsistent data" << endl;
         throw(-1);
      }

      
      //vector<KnapsackItem> knapsackConstraint;

      //Instantiate the KnapsackItem Objects
      for(i = 0; i < nbItem; i++) {
          knapsackConstraint.push_back(KnapsackItem(i,value[i],weight[i]));
      }

      

      //Call the LP procedure 
      IloNumArray relaxedSol(env);
      knapsackLPSolve (relaxedSol, knapsackConstraint, capacity, nbItem);

      for(i = 0; i < nbItem; i++) {
          env.out() << "Xstar [" << i+1 << "] = " << relaxedSol[i] << endl;
      }
      
      //Create the variables
      IloNumVarArray pickItem(env, nbItem, 0, 1, ILOFLOAT);

      //create Model
      IloModel model(env);

      IloExpr expr(env);
      for(i = 0; i < nbItem; i++) {
         //model.add(IloScalProd(weight, pickItem) <= capacity);
         expr += knapsackConstraint[i].getWeight()*pickItem[i];
      }
      model.add(expr <= capacity);
      expr.end();

      
      
      //IloExpr obj = IloScalProd(value, pickItem);
      IloExpr obj(env);
      for(i = 0; i < nbItem; i++) {
         obj += knapsackConstraint[i].getValue()*pickItem[i];
      }
      model.add(IloMaximize(env, obj));
      obj.end();

      IloCplex cplex(env);


      //vector<KnapsackItem> sortedKnapsack(knapsackConstraint);
      //sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

      /*for(int x =0; x < sortedKnapsack.size(); x++) {
        cout << "Sorted Item ID: " << sortedKnapsack[x].getIDx()
                << "Value: " << sortedKnapsack[x].getValue()
                << "Weight: " << sortedKnapsack[x].getWeight()
                << endl;
      }*/

      cplex.use(greedyCoverCuts(env, model, knapsackConstraint, relaxedSol, capacity, pickItem));
      
      cplex.out() << "extracting model2 ..." << endl;
      cplex.extract(model);

      //cplex.exportModel("knapsack.lp");

      cplex.solve();

      //cplex.setParam(IloCplex::Param::MIP::Interval, 1000);
      //cplex.setParam(IloCplex::Param::MIP::Strategy::Search, IloCplex::Traditional);
    
      cplex.out() << "Solution status: " << cplex.getStatus() << endl;

      IloNum tolerance = cplex.getParam(IloCplex::Param::MIP::Tolerances::Integrality);
      cplex.out() << "Optimal value: " << cplex.getObjValue() << endl;
      for(i = 0; i < nbItem; i++) {
         if (cplex.getValue(pickItem[i]) >= 1 - tolerance) {
            cplex.out() << "Item " << i+1 << " is picked into the Kanpsack ";
            cplex.out() << endl; 
         }
      }

   }
   catch(IloException& e) {
      cerr  << " ERROR: " << e << endl;   
   }
   catch(...) {
      cerr  << " ERROR" << endl;   
   }
   env.end();
   return 0;
}

 

 

Updated on 2014-03-27T18:35:36Z at 2014-03-27T18:35:36Z by prasenjit mandal
  • prasenjit mandal
    prasenjit mandal
    7 Posts

    Re: Generating cover Inequality for a 0-1 Knapsack problem and adding it to the problem using concert technology

    ‏2014-03-27T22:37:55Z  

    I have changed a bit in the main code. Please find it as following…

    ****************************************************************************

    KnapsackItem.h

     

    ****************************************************************************

    #ifndef KNAPSACKITEM_H
    #define    KNAPSACKITEM_H

    class KnapsackItem {
        
    private:
        size_t idx;
        int value;
        int weight;
    public:
        KnapsackItem (size_t idx_, int value_, int weight_) {
            idx= idx_;
            value = value_;
            weight = weight_;
        }
        
    public:
        size_t getIDx () const {
            return idx;
        }
        
        int getValue () const {
            return value;
        }
        
        int getWeight () const {
            return weight;
        }
    };

    #endif    /* KNAPSACKITEM_H */

    *********************************************************************************

    *********************************************************************************

    Main.cpp

    *********************************************************************************

    #include<ilcplex/ilocplex.h>

    #include<iostream>

    #include<vector>

    #include<algorithm>

     

    #include"KnapsackItem.h"

     

    ILOSTLBEGIN

     

    #define epsilon 0.0000001

    #define epsilon2_ 0.000000001

     

    IloInt numCuts = 0;

     

    vector<KnapsackItem> knapsackConstraint;

     

    ILOUSERCUTCALLBACK3(greedyCoverCuts, IloExprArray, lhs, IloNumArray, rhs, IloNum, eps) {

       try {

              IloEnv env;

              env.out() << "In cutcallback" << endl;

              IloInt n = lhs.getSize();

              for (IloInt i = 0; i < n; i++) {

                     IloNum xrhs = rhs[i];

                     if ( xrhs < IloInfinity  &&  getValue(lhs[i]) > xrhs + eps ) {

                            IloRange cut;

                            numCuts++;

                            cut = (lhs[i] <= xrhs);

                            add(cut).end();

                            rhs[i] = IloInfinity;

                            cut.end();

                     }

          }

       }

       catch (IloException &e){

              cerr<<"Error in callback: "<< e << endl;

              throw;

       }

    }

     

    boolcompareWeight (const KnapsackItem &item1, const KnapsackItem & item2 ) {

       

        return (item1.getWeight() > item2.getWeight() );

    }

     

     

    voidmakecuts (const vector<KnapsackItem> krow, IloNumArray Xstar,

                         const IloNumVarArray Xvar,

                  IloInt b, vector<KnapsackItem>& cover) {

           try{

            IloInt j;

                  IloBool gocover = false;

     

            IloEnv env;

            vector<KnapsackItem> remainder;

     

            vector<KnapsackItem> sortedKnapsack(krow);

     

            sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

     

            double greedyElementSum = 0.0;

            double greedyXstarSum = 0.0;

     

                  for (j = 0; j < sortedKnapsack.size(); j++) {

                // if Xstar is fractional and no cover cuts yet, consider it for the cover

     

                if ( (Xstar[sortedKnapsack[j].getIDx()] >= epsilon) &&

                    (Xstar[sortedKnapsack[j].getIDx()] <= 1 + epsilon) &&

                    !gocover) {

                        greedyElementSum += sortedKnapsack[j].getWeight();

                        greedyXstarSum += Xstar[sortedKnapsack[j].getIDx()];

     

                        cover.push_back(KnapsackItem(sortedKnapsack[j].getIDx(),sortedKnapsack[j].getValue(),sortedKnapsack[j].getWeight()));

     

                        if (greedyElementSum > b + epsilon2_) {

                            gocover = true;

     

                                             env.out() << "In time"<< j << endl;

                        }

                }

     

                else {

     

                              

                    remainder.push_back(KnapsackItem(sortedKnapsack[j].getIDx(),sortedKnapsack[j].getValue(),sortedKnapsack[j].getWeight()));

     

                }

            }

     

            //int size = remainder.size() + cover.size();;

            //int krowsize = sortedKnapsack.size();

            //assert (size == krowsize);

     

           

            //if no violated minimal cover

     

            if ( (greedyXstarSum <= (cover.size() -1) + epsilon2_) ||

                 (!gocover) ||

                 (cover.size() < 2) ) {

                     throw (-1);

            } else {

             IloInt coverrhs = cover.size() - 1;

     

     

                  //env.out() << "coverrhs " << coverrhs << endl;

       //     

       //       IloExpr expr1(env);

       //       for(j = 0; j < cover.size(); j++) {

     

                         //  env.out() << "over[j].getWeight()" << cover[j].getWeight() << endl;

                         //  env.out() << "Xvar[cover[j].getIDx()]" << Xvar[cover[j].getIDx()] << endl;

     

       //          //model.add(IloScalProd(weight, pickItem) <= capacity);

       //          expr1 += cover[j].getWeight() * Xvar[cover[j].getIDx()];

       //          env.out() << "index: " << cover[j].getIDx() << "Element Weight: " << cover[j].getWeight();

       //       }

     

       //       env.out() << "RHS : " << coverrhs << endl;

              //lhs.add(expr1);

              //expr1.end();

            }

     

     

                  }

        catch (IloException &e){

            cerr<<"Error in Make cuts: "<< e << endl;

            throw;

        }

     

    }

     

     

    voidknapsackLPSolve (IloNumArray& Xstar,

        vector<KnapsackItem>& knapsackConstraint,

        IloInt capacity,

        IloInt nbItem) {

        IloEnv env;

       try {

          IloInt i;

     

     

          //Create the variables

          IloNumVarArray pickItem(env, nbItem, 0, 1, ILOFLOAT);

     

          //create Model

          IloModel model(env);

     

          IloExpr expr(env);

          for(i = 0; i < nbItem; i++) {

             //model.add(IloScalProd(weight, pickItem) <= capacity);

             expr += knapsackConstraint[i].getWeight()*pickItem[i];

          }

          model.add(expr <= capacity);

          expr.end();

     

         

          

          //IloExpr obj = IloScalProd(value, pickItem);

          IloExpr obj(env);

          for(i = 0; i < nbItem; i++) {

             obj += knapsackConstraint[i].getValue()*pickItem[i];

          }

          model.add(IloMaximize(env, obj));

         obj.end();

     

          IloCplex cplex(env);

     

     

          //vector<KnapsackItem> sortedKnapsack(knapsackConstraint);

          //sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

     

          /*for(int x =0; x < sortedKnapsack.size(); x++) {

            cout << "Sorted Item ID: " << sortedKnapsack[x].getIDx()

                    << "Value: " << sortedKnapsack[x].getValue()

                    << "Weight: " << sortedKnapsack[x].getWeight()

                    << endl;

          }*/

     

          //cplex.use(greedyCoverCuts(env, model, sortedKnapsack, capacity, pickItem));

         

          cplex.out() << "extracting model ..." << endl;

          cplex.extract(model);

     

          cplex.exportModel("knapsack.lp");

     

          cplex.solve();

     

          //cplex.setParam(IloCplex::Param::MIP::Interval, 1000);

          //cplex.setParam(IloCplex::Param::MIP::Strategy::Search, IloCplex::Traditional);

       

          cplex.out() << "Solution status: " << cplex.getStatus() << endl;

     

          IloNum tolerance = cplex.getParam(IloCplex::Param::MIP::Tolerances::Integrality);

          cplex.out() << "Optimal value: " << cplex.getObjValue() << endl;

          cplex.getValues(Xstar, pickItem);

         

       }

       catch(IloException& e) {

          cerr  << " LP relaxation ERROR : " << e << endl;  

       }

       catch(...) {

          cerr  << "LP relaxation ERROR" << endl;  

       }

       env.end();

    }

     

    int

    main(int argc, char **argv)

    {

       IloEnv env;

       try {

          IloInt i;

     

          IloInt capacity;

          IloIntArray value(env), weight(env);

     

          IloInt      nbItem;

     

          const char* filename  = "knapsack.dat";

          if (argc > 1)

             filename = argv[1];

          ifstream file(filename);

          if (!file) {

             cerr << "ERROR: could not open file '" << filename

                  << "' for reading" << endl;

             cerr << "usage:   " << argv[0] << " <file>" << endl;

             throw(-1);

          }

     

          file >> value >> weight >> capacity;

          nbItem = value.getSize();

     

          IloBool consistentData = (weight.getSize() == nbItem);

          if (!consistentData) {

             cerr << "ERROR: data file '"

                  << filename << "' contains inconsistent data" << endl;

             throw(-1);

          }

     

         

          //vector<KnapsackItem> knapsackConstraint;

     

          //Instantiate the KnapsackItem Objects

          for(i = 0; i < nbItem; i++) {

              knapsackConstraint.push_back(KnapsackItem(i,value[i],weight[i]));

          }

     

         

     

          //Call the LP procedure

          IloNumArray relaxedSol(env);

          knapsackLPSolve (relaxedSol, knapsackConstraint, capacity, nbItem);

         

          //Create the variables

          IloNumVarArray pickItem(env, nbItem, 0, 1, ILOFLOAT);

     

          //create Model

          IloModel model(env);

     

          IloExpr expr(env);

          for(i = 0; i < nbItem; i++) {

             //model.add(IloScalProd(weight, pickItem) <= capacity);

             expr += knapsackConstraint[i].getWeight()*pickItem[i];

          }

          model.add(expr <= capacity);

          expr.end();

     

         

          

          //IloExpr obj = IloScalProd(value, pickItem);

          IloExpr obj(env);

          for(i = 0; i < nbItem; i++) {

             obj += knapsackConstraint[i].getValue()*pickItem[i];

          }

          model.add(IloMaximize(env, obj));

          obj.end();

     

          IloCplex cplex(env);

     

     

          //vector<KnapsackItem> sortedKnapsack(knapsackConstraint);

          //sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

     

          /*for(int x =0; x < sortedKnapsack.size(); x++) {

            cout << "Sorted Item ID: " << sortedKnapsack[x].getIDx()

                    << "Value: " << sortedKnapsack[x].getValue()

                    << "Weight: " << sortedKnapsack[x].getWeight()

                    << endl;

          }*/

     

             IloExprArray lhs(env);

             IloNumArray  rhs(env);

             vector<KnapsackItem> cover;

     

             makecuts (knapsackConstraint, relaxedSol, pickItem,capacity, cover);

     

             IloInt coverrhs = cover.size() - 1;

             IloExpr expr1(env);

             for (i = 0; i < cover.size() ; i++) {

                    expr1 += cover[i].getWeight() * pickItem[cover[i].getIDx()];

             }

     

             lhs.add(expr1);

             expr1.end();

             rhs.add( coverrhs);

     

             cplex.use(greedyCoverCuts(env, lhs, rhs, cplex.getParam(IloCplex::EpRHS)));

         

          cplex.extract(model);

            

             cplex.out() << "extracting model2 ..." << endl;

         

          //cplex.setParam(IloCplex::Param::MIP::Interval, 1000);

          //cplex.setParam(IloCplex::Param::MIP::Strategy::Search, IloCplex::Traditional);

     

            

     

          //cplex.exportModel("knapsack.lp");

     

          cplex.solve();

       

          cplex.out() << "Solution status: " << cplex.getStatus() << endl;

     

          IloNum tolerance = cplex.getParam(IloCplex::Param::MIP::Tolerances::Integrality);

          cplex.out() << "Optimal value: " << cplex.getObjValue() << endl;

             cplex.out() << "Number of cuts: " << numCuts << endl;

     

          for(i = 0; i < nbItem; i++) {

             if (cplex.getValue(pickItem[i]) >= 1 - tolerance) {

                cplex.out() << "Item " << i+1 << " is picked into the Kanpsack ";

                cplex.out() << endl;

             }

          }

     

       }

       catch(IloException& e) {

          cerr  << " ERROR: " << e << endl;  

       }

       catch(...) {

          cerr  << " ERROR" << endl;  

       }

       env.end();

       return 0;

    }

    *******************************************************************************************************************************

    But, still I am getting the same result. The code is not executing the part which are inside of the ILOUSERCUTCALLBACK3

    Updated on 2014-03-27T22:39:43Z at 2014-03-27T22:39:43Z by prasenjit mandal
  • DanielJunglas
    DanielJunglas
    117 Posts

    Re: Generating cover Inequality for a 0-1 Knapsack problem and adding it to the problem using concert technology

    ‏2014-03-28T05:34:20Z  

    I have changed a bit in the main code. Please find it as following…

    ****************************************************************************

    KnapsackItem.h

     

    ****************************************************************************

    #ifndef KNAPSACKITEM_H
    #define    KNAPSACKITEM_H

    class KnapsackItem {
        
    private:
        size_t idx;
        int value;
        int weight;
    public:
        KnapsackItem (size_t idx_, int value_, int weight_) {
            idx= idx_;
            value = value_;
            weight = weight_;
        }
        
    public:
        size_t getIDx () const {
            return idx;
        }
        
        int getValue () const {
            return value;
        }
        
        int getWeight () const {
            return weight;
        }
    };

    #endif    /* KNAPSACKITEM_H */

    *********************************************************************************

    *********************************************************************************

    Main.cpp

    *********************************************************************************

    #include<ilcplex/ilocplex.h>

    #include<iostream>

    #include<vector>

    #include<algorithm>

     

    #include"KnapsackItem.h"

     

    ILOSTLBEGIN

     

    #define epsilon 0.0000001

    #define epsilon2_ 0.000000001

     

    IloInt numCuts = 0;

     

    vector<KnapsackItem> knapsackConstraint;

     

    ILOUSERCUTCALLBACK3(greedyCoverCuts, IloExprArray, lhs, IloNumArray, rhs, IloNum, eps) {

       try {

              IloEnv env;

              env.out() << "In cutcallback" << endl;

              IloInt n = lhs.getSize();

              for (IloInt i = 0; i < n; i++) {

                     IloNum xrhs = rhs[i];

                     if ( xrhs < IloInfinity  &&  getValue(lhs[i]) > xrhs + eps ) {

                            IloRange cut;

                            numCuts++;

                            cut = (lhs[i] <= xrhs);

                            add(cut).end();

                            rhs[i] = IloInfinity;

                            cut.end();

                     }

          }

       }

       catch (IloException &e){

              cerr<<"Error in callback: "<< e << endl;

              throw;

       }

    }

     

    boolcompareWeight (const KnapsackItem &item1, const KnapsackItem & item2 ) {

       

        return (item1.getWeight() > item2.getWeight() );

    }

     

     

    voidmakecuts (const vector<KnapsackItem> krow, IloNumArray Xstar,

                         const IloNumVarArray Xvar,

                  IloInt b, vector<KnapsackItem>& cover) {

           try{

            IloInt j;

                  IloBool gocover = false;

     

            IloEnv env;

            vector<KnapsackItem> remainder;

     

            vector<KnapsackItem> sortedKnapsack(krow);

     

            sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

     

            double greedyElementSum = 0.0;

            double greedyXstarSum = 0.0;

     

                  for (j = 0; j < sortedKnapsack.size(); j++) {

                // if Xstar is fractional and no cover cuts yet, consider it for the cover

     

                if ( (Xstar[sortedKnapsack[j].getIDx()] >= epsilon) &&

                    (Xstar[sortedKnapsack[j].getIDx()] <= 1 + epsilon) &&

                    !gocover) {

                        greedyElementSum += sortedKnapsack[j].getWeight();

                        greedyXstarSum += Xstar[sortedKnapsack[j].getIDx()];

     

                        cover.push_back(KnapsackItem(sortedKnapsack[j].getIDx(),sortedKnapsack[j].getValue(),sortedKnapsack[j].getWeight()));

     

                        if (greedyElementSum > b + epsilon2_) {

                            gocover = true;

     

                                             env.out() << "In time"<< j << endl;

                        }

                }

     

                else {

     

                              

                    remainder.push_back(KnapsackItem(sortedKnapsack[j].getIDx(),sortedKnapsack[j].getValue(),sortedKnapsack[j].getWeight()));

     

                }

            }

     

            //int size = remainder.size() + cover.size();;

            //int krowsize = sortedKnapsack.size();

            //assert (size == krowsize);

     

           

            //if no violated minimal cover

     

            if ( (greedyXstarSum <= (cover.size() -1) + epsilon2_) ||

                 (!gocover) ||

                 (cover.size() < 2) ) {

                     throw (-1);

            } else {

             IloInt coverrhs = cover.size() - 1;

     

     

                  //env.out() << "coverrhs " << coverrhs << endl;

       //     

       //       IloExpr expr1(env);

       //       for(j = 0; j < cover.size(); j++) {

     

                         //  env.out() << "over[j].getWeight()" << cover[j].getWeight() << endl;

                         //  env.out() << "Xvar[cover[j].getIDx()]" << Xvar[cover[j].getIDx()] << endl;

     

       //          //model.add(IloScalProd(weight, pickItem) <= capacity);

       //          expr1 += cover[j].getWeight() * Xvar[cover[j].getIDx()];

       //          env.out() << "index: " << cover[j].getIDx() << "Element Weight: " << cover[j].getWeight();

       //       }

     

       //       env.out() << "RHS : " << coverrhs << endl;

              //lhs.add(expr1);

              //expr1.end();

            }

     

     

                  }

        catch (IloException &e){

            cerr<<"Error in Make cuts: "<< e << endl;

            throw;

        }

     

    }

     

     

    voidknapsackLPSolve (IloNumArray& Xstar,

        vector<KnapsackItem>& knapsackConstraint,

        IloInt capacity,

        IloInt nbItem) {

        IloEnv env;

       try {

          IloInt i;

     

     

          //Create the variables

          IloNumVarArray pickItem(env, nbItem, 0, 1, ILOFLOAT);

     

          //create Model

          IloModel model(env);

     

          IloExpr expr(env);

          for(i = 0; i < nbItem; i++) {

             //model.add(IloScalProd(weight, pickItem) <= capacity);

             expr += knapsackConstraint[i].getWeight()*pickItem[i];

          }

          model.add(expr <= capacity);

          expr.end();

     

         

          

          //IloExpr obj = IloScalProd(value, pickItem);

          IloExpr obj(env);

          for(i = 0; i < nbItem; i++) {

             obj += knapsackConstraint[i].getValue()*pickItem[i];

          }

          model.add(IloMaximize(env, obj));

         obj.end();

     

          IloCplex cplex(env);

     

     

          //vector<KnapsackItem> sortedKnapsack(knapsackConstraint);

          //sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

     

          /*for(int x =0; x < sortedKnapsack.size(); x++) {

            cout << "Sorted Item ID: " << sortedKnapsack[x].getIDx()

                    << "Value: " << sortedKnapsack[x].getValue()

                    << "Weight: " << sortedKnapsack[x].getWeight()

                    << endl;

          }*/

     

          //cplex.use(greedyCoverCuts(env, model, sortedKnapsack, capacity, pickItem));

         

          cplex.out() << "extracting model ..." << endl;

          cplex.extract(model);

     

          cplex.exportModel("knapsack.lp");

     

          cplex.solve();

     

          //cplex.setParam(IloCplex::Param::MIP::Interval, 1000);

          //cplex.setParam(IloCplex::Param::MIP::Strategy::Search, IloCplex::Traditional);

       

          cplex.out() << "Solution status: " << cplex.getStatus() << endl;

     

          IloNum tolerance = cplex.getParam(IloCplex::Param::MIP::Tolerances::Integrality);

          cplex.out() << "Optimal value: " << cplex.getObjValue() << endl;

          cplex.getValues(Xstar, pickItem);

         

       }

       catch(IloException& e) {

          cerr  << " LP relaxation ERROR : " << e << endl;  

       }

       catch(...) {

          cerr  << "LP relaxation ERROR" << endl;  

       }

       env.end();

    }

     

    int

    main(int argc, char **argv)

    {

       IloEnv env;

       try {

          IloInt i;

     

          IloInt capacity;

          IloIntArray value(env), weight(env);

     

          IloInt      nbItem;

     

          const char* filename  = "knapsack.dat";

          if (argc > 1)

             filename = argv[1];

          ifstream file(filename);

          if (!file) {

             cerr << "ERROR: could not open file '" << filename

                  << "' for reading" << endl;

             cerr << "usage:   " << argv[0] << " <file>" << endl;

             throw(-1);

          }

     

          file >> value >> weight >> capacity;

          nbItem = value.getSize();

     

          IloBool consistentData = (weight.getSize() == nbItem);

          if (!consistentData) {

             cerr << "ERROR: data file '"

                  << filename << "' contains inconsistent data" << endl;

             throw(-1);

          }

     

         

          //vector<KnapsackItem> knapsackConstraint;

     

          //Instantiate the KnapsackItem Objects

          for(i = 0; i < nbItem; i++) {

              knapsackConstraint.push_back(KnapsackItem(i,value[i],weight[i]));

          }

     

         

     

          //Call the LP procedure

          IloNumArray relaxedSol(env);

          knapsackLPSolve (relaxedSol, knapsackConstraint, capacity, nbItem);

         

          //Create the variables

          IloNumVarArray pickItem(env, nbItem, 0, 1, ILOFLOAT);

     

          //create Model

          IloModel model(env);

     

          IloExpr expr(env);

          for(i = 0; i < nbItem; i++) {

             //model.add(IloScalProd(weight, pickItem) <= capacity);

             expr += knapsackConstraint[i].getWeight()*pickItem[i];

          }

          model.add(expr <= capacity);

          expr.end();

     

         

          

          //IloExpr obj = IloScalProd(value, pickItem);

          IloExpr obj(env);

          for(i = 0; i < nbItem; i++) {

             obj += knapsackConstraint[i].getValue()*pickItem[i];

          }

          model.add(IloMaximize(env, obj));

          obj.end();

     

          IloCplex cplex(env);

     

     

          //vector<KnapsackItem> sortedKnapsack(knapsackConstraint);

          //sort(sortedKnapsack.begin(), sortedKnapsack.end(), compareWeight);

     

          /*for(int x =0; x < sortedKnapsack.size(); x++) {

            cout << "Sorted Item ID: " << sortedKnapsack[x].getIDx()

                    << "Value: " << sortedKnapsack[x].getValue()

                    << "Weight: " << sortedKnapsack[x].getWeight()

                    << endl;

          }*/

     

             IloExprArray lhs(env);

             IloNumArray  rhs(env);

             vector<KnapsackItem> cover;

     

             makecuts (knapsackConstraint, relaxedSol, pickItem,capacity, cover);

     

             IloInt coverrhs = cover.size() - 1;

             IloExpr expr1(env);

             for (i = 0; i < cover.size() ; i++) {

                    expr1 += cover[i].getWeight() * pickItem[cover[i].getIDx()];

             }

     

             lhs.add(expr1);

             expr1.end();

             rhs.add( coverrhs);

     

             cplex.use(greedyCoverCuts(env, lhs, rhs, cplex.getParam(IloCplex::EpRHS)));

         

          cplex.extract(model);

            

             cplex.out() << "extracting model2 ..." << endl;

         

          //cplex.setParam(IloCplex::Param::MIP::Interval, 1000);

          //cplex.setParam(IloCplex::Param::MIP::Strategy::Search, IloCplex::Traditional);

     

            

     

          //cplex.exportModel("knapsack.lp");

     

          cplex.solve();

       

          cplex.out() << "Solution status: " << cplex.getStatus() << endl;

     

          IloNum tolerance = cplex.getParam(IloCplex::Param::MIP::Tolerances::Integrality);

          cplex.out() << "Optimal value: " << cplex.getObjValue() << endl;

             cplex.out() << "Number of cuts: " << numCuts << endl;

     

          for(i = 0; i < nbItem; i++) {

             if (cplex.getValue(pickItem[i]) >= 1 - tolerance) {

                cplex.out() << "Item " << i+1 << " is picked into the Kanpsack ";

                cplex.out() << endl;

             }

          }

     

       }

       catch(IloException& e) {

          cerr  << " ERROR: " << e << endl;  

       }

       catch(...) {

          cerr  << " ERROR" << endl;  

       }

       env.end();

       return 0;

    }

    *******************************************************************************************************************************

    But, still I am getting the same result. The code is not executing the part which are inside of the ILOUSERCUTCALLBACK3

    You may want to take a look at the iloadmipex5.cpp example that is shipped with CPLEX and illustrates how to use cuts.

    So far I can see two problems with your code:

    1. You never tell CPLEX to use your callback. At some place you need to call
      cplex.use(greedyCoverCuts(...))
      to create a new instance of your callback and register that with CPLEX.
    2. Your model does not contain any integer variables, so CPLEX will solve it as an LP and will never invoke a cut callback (cuts are only considered for MIPs). You need to change the variable type to ILOBOOL. With that change CPLEX will solve your problem as a MIP. That means it will solve the linear relaxation (in which all variables are relaxed to be continuous) and will then invoke your callback with the solution to that relaxation.
  • prasenjit mandal
    prasenjit mandal
    7 Posts

    Re: Generating cover Inequality for a 0-1 Knapsack problem and adding it to the problem using concert technology

    ‏2014-03-28T10:11:06Z  

    You may want to take a look at the iloadmipex5.cpp example that is shipped with CPLEX and illustrates how to use cuts.

    So far I can see two problems with your code:

    1. You never tell CPLEX to use your callback. At some place you need to call
      cplex.use(greedyCoverCuts(...))
      to create a new instance of your callback and register that with CPLEX.
    2. Your model does not contain any integer variables, so CPLEX will solve it as an LP and will never invoke a cut callback (cuts are only considered for MIPs). You need to change the variable type to ILOBOOL. With that change CPLEX will solve your problem as a MIP. That means it will solve the linear relaxation (in which all variables are relaxed to be continuous) and will then invoke your callback with the solution to that relaxation.

    Dear Daniel Junglas,

    I already looked into the iloadmipex5.cpp. Actually, I followed that to create my own cut.

    1. But, I did use cplex.use(greedyCoverCuts(..)) to callback for both of the program;

    In the first problem: cplex.use(greedyCoverCuts(env, model, knapsackConstraint, relaxedSol, capacity, pickItem));

    In the second problem: cplex.use(greedyCoverCuts(env, lhs, rhs, cplex.getParam(IloCplex::EpRHS)));

     

     

    2. Now, today I implement the 2nd code (last one I put here) with making pickitem as integer variable:

    IloNumVarArray pickItem(env, nbItem, 0, 1, ILOINT);

    But, result is showing the same as it was showing without using USERCUTCALLBACK. I took a sample problem.

    1)  ...      max 4x_1+ 6x_2 + 5x_3

                    s.t. 3x_1+ 8x_2 + 5x_3 <= 9

    If x_1,x_2,x_3 is 0-1 integer, then objective function value is 9. If I relax the it to LP, then objective function value is 9.75.

    By applying the logic of generating greedy cover (what i used here), the only cover that I can get is x_2 + x_3 <= 1;

    I just run a problem in cplex.

    2.           max 4x_1+ 6x_2 + 5x_3

                 s.t. 3x_1+ 8x_2 + 5x_3 <= 9

                  x_2 + x_3 <= 1

                 0<=x_1,x_2,x_3 <=1

    showing me the result of the optimal objective function = 9.33.

    But, using the USERCUTCALLBACK, and making pickitem as integer variable, I am getting the objective function same as 1) (when pickitem is integer)...which is 9.

     

    Also, for debugging purpose, I used a comment inside USERCUTCALLBACK, which was not getting printed.

    env.out() << "In cutcallback" << endl;

    I used a counter variable numCuts; which is initialized as zero. It should increase it value if any cut is being added. But, the value numCuts variable remains as 0.

     

    I am herewith attaching the log life which is created after making pickitem as an integer variable. Please find the file

    Attachments

  • DanielJunglas
    DanielJunglas
    117 Posts

    Re: Generating cover Inequality for a 0-1 Knapsack problem and adding it to the problem using concert technology

    ‏2014-04-02T12:29:13Z  

    Dear Daniel Junglas,

    I already looked into the iloadmipex5.cpp. Actually, I followed that to create my own cut.

    1. But, I did use cplex.use(greedyCoverCuts(..)) to callback for both of the program;

    In the first problem: cplex.use(greedyCoverCuts(env, model, knapsackConstraint, relaxedSol, capacity, pickItem));

    In the second problem: cplex.use(greedyCoverCuts(env, lhs, rhs, cplex.getParam(IloCplex::EpRHS)));

     

     

    2. Now, today I implement the 2nd code (last one I put here) with making pickitem as integer variable:

    IloNumVarArray pickItem(env, nbItem, 0, 1, ILOINT);

    But, result is showing the same as it was showing without using USERCUTCALLBACK. I took a sample problem.

    1)  ...      max 4x_1+ 6x_2 + 5x_3

                    s.t. 3x_1+ 8x_2 + 5x_3 <= 9

    If x_1,x_2,x_3 is 0-1 integer, then objective function value is 9. If I relax the it to LP, then objective function value is 9.75.

    By applying the logic of generating greedy cover (what i used here), the only cover that I can get is x_2 + x_3 <= 1;

    I just run a problem in cplex.

    2.           max 4x_1+ 6x_2 + 5x_3

                 s.t. 3x_1+ 8x_2 + 5x_3 <= 9

                  x_2 + x_3 <= 1

                 0<=x_1,x_2,x_3 <=1

    showing me the result of the optimal objective function = 9.33.

    But, using the USERCUTCALLBACK, and making pickitem as integer variable, I am getting the objective function same as 1) (when pickitem is integer)...which is 9.

     

    Also, for debugging purpose, I used a comment inside USERCUTCALLBACK, which was not getting printed.

    env.out() << "In cutcallback" << endl;

    I used a counter variable numCuts; which is initialized as zero. It should increase it value if any cut is being added. But, the value numCuts variable remains as 0.

     

    I am herewith attaching the log life which is created after making pickitem as an integer variable. Please find the file

    Sorry for overlooking the cplex.use() statement in your code.

    I am not clear what the remaining problem is. After turning the variables into integer variables you get the expected/corrected results, right?

    That your callback is not invoked for this easy problem is expected: CPLEX can solve the problem before it even considers using cuts. If you want to make sure that your callback is invoked then you have to use more complicated problems or turn off several features (for example heuristics and presolve) of CPLEX to force CPLEX to be less clever than it actually is.