Tool_Switching

In this example we solve the Tool Switching Problem.

Instances have to provide the number of jobs, the number of tools, a capacity and a matrix which shows the needed tools for every job.

First of all we have to read the instance and create a complete undirected Graph with a vertex for each job.

  scanf("n=%d\n",&num_jobs);
  scanf("m=%d\n",&num_tools);
  scanf("min=%d\n",&f);
  scanf("max=%d\n",&f);
  scanf("c=%d\n",&capacity);
  for( int i = 1; i <= atoi(argv[1]); i++ ) {
  do scanf("%500s %d:\n",line,&f);
  while(strcmp(line,"problem"));
  }
  printf("======================================================================\n");
  printf("Solving problem %d (%d jobs, %d tools, capacity %d)\n",
         f,num_jobs,num_tools,capacity);
  printf("======================================================================\n");
  scanf("%500s\n",line);
  scanf("\n");

  Graph G;
  vector<vertex_descriptor> ref(num_jobs+1);
  for(i=0;i<num_jobs;i++) ref[i]=add_vertex(G);
  for(i=0;i<num_jobs;i++) for(j=i+1;j<num_jobs;j++)
    add_edge(ref[i],ref[j], G);
  vertex_descriptor home = ref[0];
  bool cyclic = true;

  map<vertex_descriptor, list<int> > needed_tools;
  for(i=0;i<num_tools;i++) for(j=0;j<num_jobs;j++) {
    scanf("%d",&f);
    if(f) needed_tools[ref[j]].push_back(i);
  };

Then we have to create the initial ILP model with Optsense_Min

  ILP_Problem IP(Optsense_Min);

Now we are able to add for each edge a corresponding tour variable and for each combination of jobs and tools a corresponding tool variable to our model.

  // tour variables x_ij
  var_map<edge_descriptor> tour_vars;
  BGL_FORALL_EDGES(e,G, Graph) {
    tour_vars[e]=IP.add_binary_variable(0);
  }

  // tool variables y_it
  map<vertex_descriptor, var_map<int> > tool_vars;
  BGL_FORALL_VERTICES(v,G, Graph) if(cyclic || v!=home) for(i=0; i<num_tools; i++) {
    tool_vars[v][i]=IP.add_binary_variable(0);
  };

In every solution the tour variables have to form a hamiltonian cycle. Thus we add the symbolic constraint SCIL::TOUR to our model.

  IP.add_sym_constraint(new TOUR<Graph>(G,tour_vars));

For each job we have to add a basic constraint to model its capacity.

  // capacity constraints
  std::list<cons_obj*> lc;
  BGL_FORALL_VERTICES(v,G, Graph) if(cyclic || v!=home) {
     r=0;
     q=0;
     BOOST_FOREACH(i, needed_tools[v]) q+=tool_vars[v][i];
     for(i=0; i<num_tools; i++) r+=tool_vars[v][i];
     r-=q;
     rhs = (capacity-(needed_tools[v].size()));
     IP.add_basic_constraint(r<=rhs,Static);
  }

Then we specify the needed tools for each job and add a basic constraint for each corresponding variable.

  // tool constraints
  BGL_FORALL_VERTICES(v,G, Graph) if(cyclic || v!=home) BOOST_FOREACH(i,needed_tools[v]) {
    r=tool_vars[v][i];
    IP.add_basic_constraint(r==1,Static);
  }

Now the objective function has to be created which means adding the necessary polynomials to the ILP Problem.

  // monomials in objective function
  BGL_FORALL_EDGES(e,G, Graph) {
    for(i=0; i<num_tools; i++) {
      if(cyclic || (source(e, G)!=home && target(e, G)!=home))
        IP.add_polynomial(-1 * tour_vars[e] * tool_vars[source(e, G)][i] * tool_vars[target(e, G)][i]);
      if(cyclic || source(e, G)!=home)
        IP.add_polynomial(0.5 * tour_vars[e] * tool_vars[source(e, G)][i]);
      if(cyclic || target(e, G)!=home)
        IP.add_polynomial(0.5 * tour_vars[e] * tool_vars[target(e, G)][i]);
    }
  };

Finally we call IP.optimize to solve the problem.

  IP.optimize();

To speed up the optimization, this example defines a new symbolic constraint which reformulates the added capacity constraints and separates them during the optimization process. The reformulation takes place in the constructor of this symbolic constraint. Each reformulated constraint is not added directly to our model but added to a pool. From this pool the standard_separation separates only the necessary constraints during the branch and cut process.

class reformulation_constraint : public sym_constraint{
  private:
     std::list<cons_obj*> lc;
  public:
     reformulation_constraint(ILP_Problem &IP, Graph &G, map<vertex_descriptor, list<int> > &needed_tools, var_map<edge_descriptor> &tour_vars, map<vertex_descriptor, var_map<int> > &tool_vars, int capacity, bool cyclic, vertex_descriptor &home, int num_tools){
        row r,q;
        polynomial p;
        int i;
        vertex_descriptor v;
        edge_descriptor e;
        double rhs;
        BGL_FORALL_VERTICES(v,G, Graph) if(cyclic || v!=home) {
           r=0;
           q=0;
           BOOST_FOREACH(i, needed_tools[v]) q+=tool_vars[v][i];
           for(i=0; i<num_tools; i++) r+=tool_vars[v][i];
           r-=q;
           rhs = (capacity-(needed_tools[v].size()));
           BGL_FORALL_EDGES(e,G, Graph){
              if(source(e, G) == v || target(e, G) == v){
                 p = (r - rhs) * tour_vars[e];
                 std::list<monomial> mons = p.get_p();
                 row pl;
                 std::list<monomial>::const_iterator mo;
                 foreach(mo, mons){
                    pl += IP.add_polynomial(*mo, false);
                 }
                 lc.push_back(pl<=0);
              }
           }
        }
     }

     ~reformulation_constraint(){
        for(std::list<cons_obj*>::iterator it = lc.begin(); it != lc.end(); it++)
           delete *it;
     }

     virtual void init(subproblem& S){
        return;
     }

     status feasible(solution& S){
        return feasible_solution;
     }

     status standard_separation(subproblem& S) {
        std::list<cons_obj*>::iterator c;
        cons_obj* cons;
        int num = 0;
        foreach(c, lc) {
           if( (*c)->violation(S) > 1.0e-4 ) {
              row r;
              (*c)->non_zero_entries(r);
              cons = r<=0;
              cons->set_qrStatus(NONE);
              S.add_basic_constraint(cons);
              num++;
           }
        }
        if( num ) {
           return constraint_found;
        }

        return no_constraint_found;
     }
};

If we want to use this reformulation we have to add the symbolic constraint to our model.

#ifdef USE_REFORMULATION
  //adds a symbolic constraint for reformulation of capacity constraints
  IP.add_sym_constraint(new reformulation_constraint(IP,G,needed_tools,tour_vars,tool_vars,capacity,cyclic,home,num_tools));
#endif