VrpGraph(model::VrpModel, nodes::Array{Int}, source::Int, sink::Int, multiplicity::Tuple{Int,Int})

Create a graph for pricing.

In the VRPSolver, the pricing subproblem is modeled as a Resource Constrained Shortest Problem (RCSP). VRPSolver will produce paths for the RCSP over the VrpGraph to generate the columns. Each VrpGraph has special source and sink vertices. The source and sink may be distinct vertices, but may also be the same vertex.

This function does not create a complete VrpGraph, it is necessary to create the arcs, a set of resources and to define the resource consumption intervals. In addition, it is necessary to map some formulation variables to the arcs of this graph.

See also: add_arc!, add_resource!, set_resource_bounds!, set_arc_resource_bounds!, set_arc_consumption!, add_arc_var_mapping!

Arguments

• nodes::Array{Int}: list of nodes (id's) of the VrpGraph
• source::Int: id of the source node
• sink::Int: id of the sink node
• multiplicity::Tuple{Int,Int}: multiplicity of the pricing subproblem, i.e., is given lower and upper bounds, respectively, on the number of paths from this graph in a solution.

Examples

# let `model` be a VrpModel
# Creates a VrpGraph with 5 nodes, where at most 2 paths in this graph may appear in the solution
graph1 = VrpGraph(model, [1,2,3,4,5], 1, 5, (0,2)) # paths must start at 1 and end at 5
graph2 = VrpGraph(model, [1,2,3,4,5], 1, 1, (0,2)) # another graph whose paths must start and end at 1 (cycles)

add_arc!(graph::VrpGraph, tail::Int, head::Int, vars::Array{Tuple{JuMP.Variable, Float64}} = Tuple{JuMP.Variable, Float64}[])

Add arc (tail,head) to graph and return the arc id.

Adding parallel arcs is allowed, since they will have different identifiers in graph.

Optional argument

• vars::Array{Tuple{JuMP.Variable, Float64}}: variables to be mapped to the arc (tail,head). It is a set of pairs of variable and coefficient. There are extensions where vars is Array{JuMP.Variable} and JuMP.Variable which consider all coefficients as 1.0.

Examples

# let `x1` and `x2` two decision variables
add_arc!(graph, 1, 2, [(x1,1.0), (x2,2.0)]) # add (1,2) mapped to x1 with coefficient 1 and to x2 with coefficient 2 
add_arc!(graph, 2, 1, [x1, x2]) # add (2,1) mapped to x1 and x2
arc_id = add_arc!(graph, 1, 2, x1) # add (1,2) mapped to x and get the arc id
arc_id = add_arc!(graph, 1, 2) # add (1,2) without mapped variable

add_arc_var_mapping!(graph::VrpGraph, arc_id::Int, vars::Array{Tuple{JuMP.Variable, Float64}})

Define variable mapping for an existing arc.

Arguments

• arc_id::Int: id of the arc
• vars::Array{Tuple{JuMP.Variable, Float64}}: variables to be mapped to the arc. It is a set of pairs of variable and coefficient. There are extensions where vars is Array{JuMP.Variable} and JuMP.Variable which consider all coefficients as 1.0.

Examples

add_arc_var_mapping!(graph, arc_id, [(x1,2.0), (x2,2.0)]) # map 2x1 and 2x2 to the arc in `graph` with id 1
add_arc_var_mapping!(graph, arc_id, [x1, x2]) # map x1 and x2
add_arc_var_mapping!(graph, arc_id, x) # map x

add_resource!(graph::VrpGraph; main = false, binary = false, disposable = true, step_size = 0.0)

Add a resource to the VrpGraph graph.

Optional arguments

• main::Bool: indicates that the resource is main or secondary.
• binary::Bool: indicates that the resource is binary, i.e., its accumulated consumption can only be 0 or 1.
• disposable::Bool: indicates that the resource is disposable or non-disposable.
• step_size::Float64: only for main resources, this advanced parameter is used for determining the resource consumption intervals that define each bucket on the labeling algorithm during the pricing.

if step_size is not given, it is determined automatically for main resources, based on the parameter RCSPnumberOfBucketsPerVertex.

Examples

# let `graph` be a VrpGraph
r1 = add_resource!(graph) # create a secondary, disposable, non-binary resource
r2 = add_resource!(graph, main=true, disposable=false) # create a main, non-disposable, non-binary resource

set_resource_bounds!(graph::VrpGraph, vertex::Int, res_id::Int, lb::Float64, ub::Float64)

Set the resource bounds to a vertex of the VrpGraph graph.

Defining the interval $[lb,ub]$ for res_id at vertex is equivalent to defining the same interval for every incoming arc of vertex.

Arguments

• vertex::Int: vertex id in the VrpGraph graph.
• res_id::Int: resource id in the VrpGraph graph.
• lb::Float64: lower bound on the resource consumption at the vertex.
• ub::Float64: upper bound on the resource consumption at the vertex.

set_arc_consumption!(graph::VrpGraph, arc_id::Int, res_id::Int, value::Union{Int,Float64})

Set the arc consumption for a specific resource.

Arguments

• graph::VrpGraph: graph to be considered
• arc_id::Int: arc to be considered
• res_id::Int: resource id to define consumption
• value::Union{Int,Float64}: consumption value which can be integer or real

Example

set_arc_consumption!(graph, 3, 1, 2.5) # define a consumption of 2.5 for the resource 1 when passing by the arc 3 

get_arc_consumption(graph::VrpGraph, arc_id::Int, res_id::Int)

Get the arc consumption value for a specific resource.

get_arc_set(graph::VrpGraph)

Return the set of arcs of a VrpGraph as an array of triples, where each triple contains the arc (first two elements) and its id (third element).

For example, if the function returns [(1,2,1), (2,1,2)], it must be interpreted as graph having two arcs: (1,2) with id 1 and (2,1) with id 2.

set_arc_packing_sets!(user_model::VrpModel, collection::Array{Array{Tuple{VrpGraph,Int}, 1}, 1})

Define a collection of packing sets on arcs. For each defined packing set, VRPSolver automatically will create an equivalent elementarity set on arcs.

The collection must be a set of mutually disjoint subsets of arcs. Not all arcs need to belong to some packing set. The index of a packing set in the array defines its packing set id.

Examples

# let `G` be an array of VrpGraph and `model` the VrpModel
# A packing set is a list of pairs of VrpGraph and arc id
ps_1 = [(G[1],1),(G[2],1),(G[3],1)] # packing set composed by arcs of different graphs
ps_2 = [(G[2],2),(G[2],4)] # packing set composed by arcs of the same graph
ps_3 = [(G[2],3),(G[3],2)] # another packing set
set_arc_packing_sets!(model, [ps_1, ps_2, ps_3]) # passing the collection of packing sets to the model

set_vertex_packing_sets!(user_model::VrpModel, collection::Array{Array{Tuple{VrpGraph,Int}, 1}, 1})

Define a collection of packing sets on vertices. For each defined packing set, VRPSolver automatically will create an equivalent elementarity set on vertices.

The collection must be a set of mutually disjoint subsets of vertices. Not all vertices need to belong to some packing set. The index of a packing set in the array defines its packing set id.

Examples

# let `G` be an array of VrpGraph and `model` the VrpModel
# A packing set is a list of pairs of VrpGraph and vertex id
ps_1 = [(G[1],1),(G[2],1),(G[3],1)] # packing set composed by vertices of different graphs
ps_2 = [(G[2],2),(G[2],4)] # packing set composed by vertices of the same graph
ps_3 = [(G[2],3),(G[3],2)] # another packing set
set_vertex_packing_sets!(model, [ps_1, ps_2, ps_3]) # passing the collection of packing sets to the model

set_additional_arc_elementarity_sets!(user_model::VrpModel, collection::Array{Tuple{VrpGraph,Array{Int,1}}, 1})

Define an additional collection of elementarity sets on arcs.

The collection must be a set of mutually disjoint subsets of arcs. Not all arcs need to belong to some elementarity set. The index $i$ of a elementarity set in the array defines its elementarity set id as $|\mathcal{P}|+i$ because there are $|\mathcal{P}|$ automatic elementarity sets (one for each packing set) created with set_arc_packing_sets!.

Examples

# let `G` be an array of VrpGraph and `model` the VrpModel
# An elementarity set is a pair of VrpGraph and a list of arc ids
es_1 = (G[1],[1,2,4]) # elem. set on graph G[1] composed by the arcs 1, 2, and 4  
es_2 = (G[2],[2,3,5,9]) # elem. set on G[2] with 4 arcs
es_3 = (G[2],[1,4,6,7]) # another elem. set on G[2]
set_additional_arc_elementarity_sets!(model, [es_1, es_2, es_3]) # passing the collection of elem. sets to the model

set_additional_vertex_elementarity_sets!(user_model::VrpModel, collection::Array{Tuple{VrpGraph,Array{Int,1}}, 1})

Define an additional collection of elementarity sets on vertices.

The collection must be a set of mutually disjoint subsets of vertices. Not all vertices need to belong to some elementarity set. The index $i$ of a elementarity set in the array defines its elementarity set id as $|\mathcal{P}^V|+i$ because there are $|\mathcal{P}^V|$ automatic elementarity sets (one for each packing set) created with set_vertex_packing_sets!.

Examples

# let `G` be an array of VrpGraph and `model` the VrpModel
# An elementarity set is a pair of VrpGraph and a list of vertex ids
es_1 = (G[1],[1,2,4]) # elem. set on graph G[1] composed by the vertices 1, 2, and 4  
es_2 = (G[2],[2,3,5,9]) # elem. set on G[2] with 4 vertices
es_3 = (G[2],[1,4,6,7]) # another elem. set on G[2]
set_additional_vertex_elementarity_sets!(model, [es_1, es_2, es_3]) # passing the collection of elem. sets to the model

define_elementarity_sets_distance_matrix!(model::VrpModel, graph::VrpGraph, matrix::Array{Array{Float64,1},1})

Define distance matrix between the elementarity sets for a specific graph.

This is a convenient way of defining the initial ng-sets for pricing over $\mathcal{E}$-ng-paths: the ng-set of each vertex (arc) is defined as being the ng-size elementarity sets that are closer to its own elementarity set, according to the given distance matrix. The element matrix[i][j] represents the distance between the elementarity set $i$ to the elementarity set $j$. An index of an elementarity set is defined during its creation: automatic elementarity sets (one for each packing set) has the indexes $\{1,2,\dots,|\mathcal{P}|\}$, whereas the additional elementarity sets has the indexes $\{|\mathcal{P}|+1,|\mathcal{P}|+2,\dots\}$ (these indexes consider $|\mathcal{P}^V|$ instead of $|\mathcal{P}|$ for packing sets on vertices). To define the distance between two elementarity sets, it is recommended to consider some metric which involves all elements (vertices or arcs) of both elementarity sets.

add_elem_set_to_vertex_init_ng_neighbourhood!(model::VrpModel, graph::VrpGraph, vertex_id::Int, es_id::Int)

Add elementarity set to the vertex ng-set.

This is an explicit way to set initial ng-neighbourhoods, which has priority over the definition with define_elementarity_sets_distance_matrix!. In fact, distance matrix is taken into account only if user-defined ng-sets are empty.

Arguments

• model::VrpModel: model
• graph::VrpGraph: graph
• vertex_id::Int: vertex id
• es_id::Int: elementarity set id. The valid ids are $\{1,2,\dots,|\mathcal{P}^V|,|\mathcal{P}^V|+1,|\mathcal{P}^V|+2,\dots,|\mathcal{P}^V|+|\mathcal{E}^V|\}$ (considering automatic and additional elem. sets)

add_elem_set_to_arc_init_ng_neighbourhood!(model::VrpModel, graph::VrpGraph, arc_id::Int, es_id::Int)

Add elementarity set to the arc ng-set.

This is an explicit way to set initial ng-neighbourhoods, which has priority over the definition with define_elementarity_sets_distance_matrix!. In fact, distance matrix is taken into account only if user-defined ng-sets are empty.

Arguments

• model::VrpModel: model
• graph::VrpGraph: graph
• arc_id::Int: arc id
• es_id::Int: elementarity set id. The valid ids are $\{1,2,\dots,|\mathcal{P}|,|\mathcal{P}|+1,|\mathcal{P}|+2,\dots,|\mathcal{P}|+|\mathcal{E}|\}$ (considering automatic and additional elem. sets)

add_graph!(model::VrpModel, graph::VrpGraph)

Add VrpGraph to a VrpModel.

This function should be called once for each graph in the model.

add_capacity_cut_separator!(model::VrpModel, demands::Array{Tuple{Array{Tuple{VrpGraph,Int}, 1},Float64},1}, capacity::Float64)

Define a rounded capacity cut (RCC) separator over a collection of packing sets defined on vertices. RCC separators cannot be used if the packings sets are defined on arcs.

Arguments

• model::VrpModel: model to be added the RCC separator.
• demands::Array{Tuple{Array{Tuple{VrpGraph,Int}, 1},Float64},1}: array of pairs of packing set and demand.
• capacity::Float64: capacity considered in the RCC separator.

Examples

# Let PS be an array of `n` packing sets in vertices, where PS[i] is the i-th packing set
# Let d[i] be the demand associated with the i-th packing set
# Let `model` be a VrpModel and Q the capacity to be used in the RCC
add_capacity_cut_separator!(model, [(PS[i], d[i]) for i in 1:n], Q) # add a RCC separator

set_branching_priority!(model::VrpModel, var_container_name::String, priority::Int)

Set the branching priority for a decision variable.

Branching is performed on a variable with priority $k$ only when there is no possible branching for variables with priority higher than $k$.

Arguments

• var_container_name::String: JuMP decision variable name.
• priority::Int: the priority of the variable, which is higher when this value is increased.

Example

model = VrpModel()
@variable(model.formulation, x[i in 1:10] >= 0, Int)
@variable(model.formulation, y[i in 1:20] >= 0, Int)
... 
set_branching_priority!(model, "x", 2) # x has higher priority
set_branching_priority!(model, "y", 1) # than y

function set_branching_priority!(model::VrpModel, exps_family, name::String, priority::Int)

Set the branching priority for a set of JuMP expressions.

Arguments

• exps_family: set of expressions created with JuMP macro @expression
• name::String: JuMP expression name.
• priority::Int: the priority of the expressions, which is higher when this value is increased.

function set_branching_priority!(model::VrpModel, exp::JuMP.GenericAffExpr{Float64,JuMP.Variable}, name::String, priority::Int)

Set the branching priority for a JuMP expression.

Arguments

• exp: expression created with JuMP macro @expression
• name::String: JuMP expression name.
• priority::Int: the priority of the expression, which is higher when this value is increased.

Example

model = VrpModel()
@variable(model.formulation, x[i in 1:10] >= 0, Int)
@expression(model.formulation, exp, sum(x[i] for i in 1:5))
... 
set_branching_priority!(model, "x", 2) # x has higher priority
set_branching_priority!(model, exp, "exp", 1) # than exp

function enable_resource_consumption_branching!(model::VrpModel, priority::Int)

Enable the accumulated resource consumption branching. Given a packing set $S \in \mathcal{P}$, a main resource $r \in R^k_M$, and a certain threshold value $t^*$: in the left child make $u_{a,r}=t^*$, for all $a \in S$; in the right child make $l_{a,r}=t^*$, for all $a \in S$. The packing set, the main resource, and the threshold are automatically chosen by VRPSolver during the execution. The branching is not likely to be complete, in the sense that some fractional $\lambda$ solutions can not be eliminated by it. However, it does not increase the pricing difficulty and it may work well in practice, postponing (and even avoiding) the use of a branching that makes pricing harder.

Arguments

• priority::Int: the branching priority, which is higher when this value is increased.

Example

model = VrpModel()
... 
enable_resource_consumption_branching!(model, 1) 

function enable_packset_ryanfoster_branching!(model::VrpModel, priority::Int)

Enable the Ryan and Foster branching. Given two distinct packing sets $S$ and $S'$ in $\mathcal{P}$, let $P(S,S') \subseteq P$ be the subset of the paths that contain arcs in both $S$ and $S'$. The branching is over the value of $\sum_{p\in P(S,S')} \lambda_p$, either 0 or 1. The packing sets are automatically chosen by VRPSolver during the execution. This branching is still to be avoided if possible, because it makes the pricing harder. However, using that scheme leads to more balanced search trees.

Arguments

• priority::Int: the branching priority, which is higher when this value is increased.

Example

model = VrpModel()
... 
enable_packset_ryanfoster_branching!(model, 2) 

set_arc_resource_bounds!(graph::VrpGraph, arc_id::Int, res_id::Int, lb::Float64, ub::Float64)

Set the resource bounds for an arc of the VrpGraph graph.

Arguments

• arc::Int: arc id in the VrpGraph graph.
• res_id::Int: resource id in the VrpGraph graph.
• lb::Float64: lower bound on the resource consumption at the vertex.
• ub::Float64: upper bound on the resource consumption at the vertex.

enable_rank1_cuts!(model::VrpModel)

Enable use of limited memory rank-1 cuts during the execution.

These cuts depends of the collection of packing sets (whether in arcs or vertices). Therefore, it will not be applied if you do not define packing sets. These cuts are potentially very strong, but each added cut can make the pricing subproblems harder.

VrpModel()

Create an empty VRPSolver model.

It is the main object of the VRPSolver. It is responsible to keep the RCSP graphs (of type VrpGraph), formulation, packing sets, rounded capacity cuts and other definitions (like branching).

VrpOptimizer(user_model::VrpModel, param_file::String, instance_name = "")

Build an optimizer for a VrpModel.

Arguments

• model::VrpModel: model to be considered
• param_file::String: path for the VRPSolver parameters file

Optional arguments

• instance_name::String: the instance name to be shown in the results line (line with execution statistics).

optimize!(optimizer::VrpOptimizer)

Solve a VRPSolver problem.

It returns a pair with the status of the execution and a flag indicating whether a solution was found, respectively.

Example

# let model be a VrpModel
optimizer = VrpOptimizer(model, "path_to_config/config.cfg")
(status, solution_found) = optimize!(optimizer)

add_cut_callback!(user_model::VrpModel, callback::Any, constr_name::String)

Add user cut callback for separation during the execution.

Cuts must be added through the function add_dynamic_constr!.

Arguments

• model::VrpModel: model to be added the cut callback.
• callback::Any: function with the separation algorithm
• constr_name::String: a nome for the cut callback

Example

# let model be a VrpModel and x a set of variables for edges
function edge_ub_callback()
   for (i,j) in E
     e = (i,j)
      if i != 0 && get_value(model.optimizer, x[e]) > 1.001
         println("Adding edge ub cut for e = ", e)
         add_dynamic_constr!(model.optimizer, [x[e]], [1.0], <=, 1.0, "edge_ub")
      end
   end 
end 
add_cut_callback!(model, edge_ub_callback, "edge_ub")

add_dynamic_constr!(optimizer::VrpOptimizer, vars, coeffs, sense, rhs, constr_name::String)

Add user cut (dynamic constraint) to the formulation.

It should be called inside a cut callback function registered with add_cut_callback!.

Arguments

• vars: array of variables of the cut
• coeffs: array of coefficients, where coeffs[i] is the coefficient of vars[i]
• sense: sense of the cut: <=, >= or ==.
• rhs: right-hand side value
• constr_name: a name for the cut

Example

# let model be a VrpModel and x a set of variables
function my_callback()
   # add cut 1.0*x[1] + 2.0*x[2] <= 1.0
   add_dynamic_constr!(model.optimizer, [x[1],x[2]], [1.0,2.0], <=, 1.0, "my_cut")
end 
add_cut_callback!(model, my_callback, "my_callback")

get_value(optimizer::VrpOptimizer, user_var::JuMP.Variable)

Get the value for a decision variable after optimization.

get_value(optimizer::VrpOptimizer, user_var::JuMP.Variable, path_id::Int)

Get the value for a decision variable due to a specific path.

path_id shoul be a value between 1 and the number of positive paths.

get_value(optimizer::VrpOptimizer, path_id::Int)

Get the value for a path variable (λ variable created internally due to the mapping).

get_values(optimizer::VrpOptimizer, user_vars::Array{JuMP.Variable})

Get the values for an array of decision variables after optimization.

get_values(optimizer::VrpOptimizer, user_vars::Array{JuMP.Variable}, path_id::Int)

Get the values for an array of decision variables that would be obtained from mapping only a single specific path variable (with value 1) to them. Necessary for identifying which paths are part of the solution in some models.

get_number_of_positive_paths(optimizer::VrpOptimizer)

Get the number of paths (lambda variables) with positive value in the solution. Those paths will be numbered from 1 to getnumberofpositivepaths for the purpose of retrieving the value of the lambda variables and for identifying the path.

set_cutoff!(optimizer::VrpOptimizer, ub::Float64)

Set an upper bound (primal bound) for the execution.

get_objective_value(optimizer::VrpOptimizer)

Get the objective function value after optimization.

show(io::IO, graph::VrpGraph)

Show a VrpGraph.

get_complete_formulation(model::VrpModel, paramfile::String)

Get the complete formulation, which includes mapping constraints with λ variables (for paths).

The enumerated paths and the complete formulation are returned. It has all enumerated paths for all graphs and a JuMP.Model. This function can be seen as a tool for debugging the VRPSolver model, for example, when applied to small instances to check the correctness of the final model produced. The user may solve it with another solver option in JuMP 0.18 (e.g. for Gurobi, Coin CBC or CPLEX).

Warning 1: the enumeration procedure only produces $\mathcal{E}$-elementarity-paths. Moreover, for all paths that visit exactly the same elementarity sets, only a single least cost path is produced.

Warning 2: if some user cuts are essential for the correctness of the model (i.e., they are not only used to improve the linear relaxation), the corresponding cut callbacks should be called for solving the complete formulation.

Example

# Let `model` be a VrpModel and `path_to_params_file` the path for the parameters file
enum_paths, complete_form = get_complete_formulation(model, path_to_params_file)
complete_form.solver = CplexSolver() # set MIP solver (it can be another one than CPLEX)
print_enum_paths(enum_paths)
println(complete_form)
solve(complete_form)
println("Objective value: ", getobjectivevalue(complete_form))

print_enum_paths(paths)

Print the enumerated paths for all graphs.

Warning 1: the enumeration procedure only produces $\mathcal{E}$-elementarity-paths. Moreover, for all paths that visit exactly the same elementarity sets, only a single least cost path is produced.

Example

# Let `model` be a VrpModel and `path_to_params_file` the path for the parameters file
enum_paths, complete_form = get_complete_formulation(model, path_to_params_file)
complete_form.solver = CplexSolver() # set MIP solver (it can be another one than CPLEX)
print_enum_paths(enum_paths)