53 const int p_num_nodes,
55 const vector< int >& p_demand,
56 const vector< vector<int> >& p_distance,
57 const vector< vector<SCIP_VAR*> >& p_arc_var,
58 const vector< vector<SCIP_CONS*> >& p_arc_con,
59 const vector<SCIP_CONS* >& p_part_con
62 _num_nodes(p_num_nodes),
63 _capacity(p_capacity),
65 _distance(p_distance),
85 for (
int i = 0;
i < num_nodes(); ++
i)
87 for (
int j = 0; j <
i; ++j)
93 for (
int i = 1;
i < num_nodes(); ++
i)
112 vector< vector<SCIP_Real> > red_length(
num_nodes());
114 red_length[
i].resize(
i, 0.0);
122 for (
int j = 0; j <
i; ++j)
132 red_length[
i][j] =
r;
141 for (
int j = 0; j <
i; ++j)
151 red_length[
i][j] =
r;
162 for (
int j = 0; j <
i; ++j)
171 for (
int j = 0; j <
i; ++j)
180 for (
int j = 0; j <
i; ++j)
189 for (
int j = 0; j <
i; ++j)
260 const list<int>& tour
267 for (list<int>::const_iterator it = tour.begin(); it != tour.end(); ++it)
269 strncpy(tmp_name, var_name, 255);
270 (void)
SCIPsnprintf(var_name, 255,
"%s_%d", tmp_name, *it);
290 for (list<int>::const_iterator it = tour.begin(); it != tour.end(); ++it)
298 for (list<int>::const_iterator it = tour.begin(); it != tour.end(); ++it)
322static const SCIP_Real
eps = 1e-9;
329 PQUEUE_KEY() : demand(0), length(0.0) {}
332bool operator< (
const PQUEUE_KEY& l1,
const PQUEUE_KEY& l2)
334 if ( l1.demand < l2.demand )
336 if ( l1.demand > l2.demand )
338 if ( l1.length < l2.length-
eps )
347typedef int PQUEUE_DATA;
349typedef PQUEUE::pqueue_item PQUEUE_ITEM;
353struct NODE_TABLE_DATA
357 PQUEUE::pqueue_item queue_item;
359 NODE_TABLE_DATA( ) : length(0.0), predecessor(-1), queue_item(
NULL ) {}
362typedef int NODE_TABLE_KEY;
363typedef std::map< NODE_TABLE_KEY, NODE_TABLE_DATA > NODE_TABLE;
374 const vector< vector<SCIP_Real> >& length,
387 PQUEUE_KEY queue_key;
388 PQUEUE_DATA queue_data = 0;
389 PQUEUE_ITEM queue_item = PQ.insert(queue_key, queue_data);
391 NODE_TABLE_KEY table_key = 0;
392 NODE_TABLE_DATA table_entry;
395 while ( ! PQ.empty() )
398 queue_item = PQ.top();
399 queue_key = PQ.get_key (queue_item);
400 queue_data = PQ.get_data(queue_item);
404 const int curr_node = queue_data;
405 const SCIP_Real curr_length = queue_key.length;
406 const int curr_demand = queue_key.demand;
409 if ( curr_node == 0 && curr_length < -
eps )
413 if ( curr_node == 0 && curr_demand != 0 )
417 for (
int next_node = 0; next_node <
num_nodes(); ++next_node)
419 if ( next_node == curr_node )
421 if (
have_edge( next_node, curr_node ) ==
false )
424 const int next_demand = curr_demand +
demand(next_node);
429 const SCIP_Real next_length = curr_length + ( curr_node > next_node ?
430 length[curr_node][next_node] :
431 length[next_node][curr_node] );
433 NODE_TABLE& next_table = table[next_node];
437 list<NODE_TABLE::iterator> dominated;
439 for (NODE_TABLE::iterator it = next_table.begin(); it != next_table.end() && ! skip; ++it)
441 if ( next_demand >= it->first && next_length >= it->second.length -
eps )
444 if ( next_demand <= it->first && next_length <= it->second.length +
eps )
445 dominated.push_front( it );
451 for (list<NODE_TABLE::iterator>::iterator it = dominated.begin(); it != dominated.end(); ++it)
453 PQ.remove( (*it)->second.queue_item );
454 next_table.erase( *it );
458 queue_key.demand = next_demand;
459 queue_key.length = next_length;
460 queue_data = next_node;
462 queue_item = PQ.insert(queue_key, queue_data);
464 table_key = next_demand;
465 table_entry.length = next_length;
466 table_entry.predecessor = curr_node;
467 table_entry.queue_item = queue_item;
469 next_table[table_key] = table_entry;
472 printf(
"new entry node = %d demand = %d length = %g pref = %d\n", next_node, next_demand, next_length, curr_node);
479 table_entry.predecessor = -1;
480 table_entry.length = 0;
484 for (NODE_TABLE::iterator it = table[0].begin(); it != table[0].end(); ++it)
486 if ( it->second.length < table_entry.length )
488 table_key = it->first;
489 table_entry = it->second;
492 SCIP_Real tour_length = table_entry.length;
494 while ( table_entry.predecessor > 0 )
496 table_key -=
demand(curr_node);
497 curr_node = table_entry.predecessor;
498 tour.push_front(curr_node);
499 table_entry = table[curr_node][table_key];
ObjPricerVRP(SCIP *scip, const char *p_name, const int p_num_nodes, const int p_capacity, const vector< int > &p_demand, const vector< vector< int > > &p_distance, const vector< vector< SCIP_VAR * > > &p_arc_var, const vector< vector< SCIP_CONS * > > &p_arc_con, const vector< SCIP_CONS * > &p_part_con)
SCIP_RETCODE pricing(SCIP *scip, bool isfarkas) const
bool have_edge(const int i, const int j) const
SCIP_RETCODE add_tour_variable(SCIP *scip, const list< int > &tour) const
SCIP_CONS * arc_con(const int i, const int j) const
int demand(const int i) const
double find_shortest_tour(const vector< vector< double > > &length, list< int > &tour) const
SCIP_CONS * part_con(const int i) const
C++ wrapper for variable pricer.
Constraint handler for linear constraints in their most general form, .
SCIP_Real SCIPgetDualsolLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddCoefLinear(SCIP *scip, SCIP_CONS *cons, SCIP_VAR *var, SCIP_Real val)
SCIP_Real SCIPgetDualfarkasLinear(SCIP *scip, SCIP_CONS *cons)
SCIP_RETCODE SCIPaddPricedVar(SCIP *scip, SCIP_VAR *var, SCIP_Real score)
SCIP_RETCODE SCIPwriteTransProblem(SCIP *scip, const char *filename, const char *extension, SCIP_Bool genericnames)
void SCIPinfoMessage(SCIP *scip, FILE *file, const char *formatstr,...)
SCIP_RETCODE SCIPgetTransformedCons(SCIP *scip, SCIP_CONS *cons, SCIP_CONS **transcons)
SCIP_Real SCIPinfinity(SCIP *scip)
SCIP_Bool SCIPisNegative(SCIP *scip, SCIP_Real val)
SCIP_RETCODE SCIPreleaseVar(SCIP *scip, SCIP_VAR **var)
SCIP_RETCODE SCIPcreateVar(SCIP *scip, SCIP_VAR **var, const char *name, SCIP_Real lb, SCIP_Real ub, SCIP_Real obj, SCIP_VARTYPE vartype, SCIP_Bool initial, SCIP_Bool removable, SCIP_DECL_VARDELORIG((*vardelorig)), SCIP_DECL_VARTRANS((*vartrans)), SCIP_DECL_VARDELTRANS((*vardeltrans)), SCIP_DECL_VARCOPY((*varcopy)), SCIP_VARDATA *vardata)
SCIP_RETCODE SCIPgetTransformedVar(SCIP *scip, SCIP_VAR *var, SCIP_VAR **transvar)
int SCIPsnprintf(char *t, int len, const char *s,...)
assert(minobj< SCIPgetCutoffbound(scip))
class for priority queues
#define SCIP_DECL_PRICERINIT(x)
#define SCIP_DECL_PRICERREDCOST(x)
#define SCIP_DECL_PRICERFARKAS(x)
enum SCIP_Retcode SCIP_RETCODE
@ SCIP_VARTYPE_CONTINUOUS