Scippy

SCIP

Solving Constraint Integer Programs

pricer_vrp.cpp File Reference

Detailed Description

VRP pricer plugin.

Author
Andreas Bley
Marc Pfetsch

Definition in file pricer_vrp.cpp.

#include "pricer_vrp.h"
#include "pqueue.h"
#include <iostream>
#include <map>
#include <vector>
#include "scip/cons_linear.h"

Go to the source code of this file.

Functions

 SCIP_DECL_PRICERINIT (ObjPricerVRP::scip_init)
 
 SCIP_DECL_PRICERREDCOST (ObjPricerVRP::scip_redcost)
 
 SCIP_DECL_PRICERFARKAS (ObjPricerVRP::scip_farkas)
 

Function Documentation

◆ SCIP_DECL_PRICERINIT()

SCIP_DECL_PRICERINIT ( ObjPricerVRP::scip_init  )

initialization method of variable pricer (called after problem was transformed)

Because SCIP transformes the original problem in preprocessing, we need to get the references to the variables and constraints in the transformed problem from the references in the original problem.

Definition at line 83 of file pricer_vrp.cpp.

References ObjPricerVRP::num_nodes(), SCIP_CALL, SCIP_OKAY, SCIPgetTransformedCons(), and SCIPgetTransformedVar().

◆ SCIP_DECL_PRICERREDCOST()

SCIP_DECL_PRICERREDCOST ( ObjPricerVRP::scip_redcost  )

Pricing of additional variables if LP is feasible.

  • get the values of the dual variables you need
  • construct the reduced-cost arc lengths from these values
  • find the shortest admissible tour with respect to these lengths
  • if this tour has negative reduced cost, add it to the LP

possible return values for *result:

  • SCIP_SUCCESS : at least one improving variable was found, or it is ensured that no such variable exists
  • SCIP_DIDNOTRUN : the pricing process was aborted by the pricer, there is no guarantee that the current LP solution is optimal

Definition at line 225 of file pricer_vrp.cpp.

References ObjPricerVRP::pricing(), SCIP_CALL, SCIP_OKAY, SCIP_SUCCESS, and SCIPdebugMsg.

◆ SCIP_DECL_PRICERFARKAS()

SCIP_DECL_PRICERFARKAS ( ObjPricerVRP::scip_farkas  )

Pricing of additional variables if LP is infeasible.

  • get the values of the dual Farks multipliers you need
  • construct the reduced-cost arc lengths from these values
  • find the shortest admissible tour with respect to these lengths
  • if this tour has negative reduced cost, add it to the LP

Definition at line 246 of file pricer_vrp.cpp.

References ObjPricerVRP::pricing(), SCIP_CALL, SCIP_OKAY, and SCIPdebugMsg.