Main Page   Class Hierarchy   Compound List   File List   Contact   Download   Symbolic Constraints   Examples

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); 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++) for(j=i+1;j<num_jobs;j++)
vertex_descriptor home = ref;
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) {
}

// 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++) {
};
```

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()));
}
```

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];
}
```

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){
}
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);
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
Generated on Mon Mar 28 22:03:47 2011 for SCIL by 1.6.3