STMTS_VPSolver

VPSolver: Vector Packing Solver

• $VBP_FLOW[...]{...};
• $VBP_GRAPH[...]{...};
• $MVP_FLOW[...]{...};
• $MVP_GRAPH[...]{...};
• Return to the index

VBP_FLOW

Usage: $VBP_FLOW[zvar_name]{W, w, b, bounds=None, binary=False};

Description: generates arc-flow models with graph compression for vector packing instances.

Requirements: VPSolver

Parameters:

• AMPL:
  • zvar_name: variable name for the amount of flow in the feedback arc (which corresponds to the number of bins used);
• Python:
  • W: bin capacity;
  • w: item weights;
  • b: item demands (may include strings with variable names if the demand is not fixed);
  • bounds: maximum demand for each item;
  • binary: binary patterns (if True) or general integer patterns (if False).

Creates:

• AMPL:
  • an arc-flow model with graph compression for the vector packing instance (variables and constraints);
  • a variable 'zvar_name' for the amount of flow in the feedback arc.
• Python:
  • stores information for solution extraction.

Examples:

$EXEC{
from pyvpsolver import VBP
instance = VBP.from_file("instance.vbp")
};
$PARAM[b{I}]{instance.b, i0=1};
var x{I}, >= 0;
$VBP_FLOW[Z]{instance.W, instance.w, ["x[{}]".format(i) for i in range(1, instance.m+1)]};    

minimize obj: Z;
s.t. demand{i in I}: x[i] >= instance1_b[i]; # demand constraints
end;

is replaced by:

param b{I};
var x{I}, >= 0;  
/* arc-flow model with graph compression for instance.vbp */
/* Z is the amount of flow on the feedback arc */
/* x[i] = amount of flow on arcs associated with item i */
minimize obj: Z;
s.t. demand{i in I}: x[i] >= b[i]; # demand constraints
end;

VBP_GRAPH

Usage: $VBP_GRAPH[V_name, A_name]{W, w, labels, bounds=None, binary=False, S="S", T="T", LOSS="LOSS"};

Requirements: VPSolver

Description: generates compressed arc-flow graphs for vector packing instances.

Parameters:

• AMPL:
  • V_name: name for the set of vertices;
  • A_name: name for the set of arcs.
• Python:
  • W: bin capacity;
  • w: item weights;
  • labels: item labels;
  • bounds: maximum demand for each item;
  • binary: binary patterns (if True) or general integer patterns (if False);
  • S: source node label;
  • T: target node label;
  • LOSS: loss arcs label.

Creates:

• AMPL:
  • set 'V_name': set of vertices;
  • set 'A_name': set of arcs.
• Python:
  • _sets['V_name']: set of vertices;
  • _sets['A_name']: set of arcs.

Examples:

$EXEC{
from pyvpsolver import VBP
instance = VBP.from_file("instance.vbp")
};
$PARAM[b{I}]{instance.b, i0=1};
$VBP_GRAPH[V,A]{instance.W, instance.w, range(1, instance.m+1)};

# Variables:
var Z, integer, >= 0; # amount of flow in the feedback arc
var f{A}, integer, >= 0; # amount of flow in each arc
# Objective:
maximize obj: f['T', 'S', 'LOSS'];
# Flow conservation constraints:
s.t. flowcon{k in V}: 
    sum{(u,v,i) in A: v == k} f[u,v,i]  - sum{(u,v,i) in A: u == k} f[u, v, i] = 0;
# Demand constraints:
s.t. demand{k in I}: sum{(u,v,i) in A: i == k} >= b[i];

MVP_FLOW

Usage: $MVP_FLOW[zvars_name]{Ws, ws, b, bounds=None, binary=False, i0=0};

Description: generates arc-flow models with graph compression for multiple-choice vector packing instances.

Requirements: VPSolver

Parameters:

• AMPL:
  • zvars_name: name of the set of variables associated with each feedback arc;
• Python:
  • Ws: list of bin capacities;
  • ws: list of lists of item incarnations;
  • b: item demands (may include strings with variable names if the demand is not fixed);
  • bounds: maximum demand for each item;
  • binary: binary patterns (if True) or general integer patterns (if False).

Creates:

• AMPL:
  • an arc-flow model with graph compression for the multiple-choice vector packing instance (variables and constraints);
  • a set of variables 'zvars_name' for the amount of flow in each feedback arc.
• Python:
  • stores information for solution extraction.

Examples:

$EXEC{
from pyvpsolver import MVP
inst = MVP.from_file("instance.mvp")
};
$PARAM[Cs{T}]{inst.Cs, i0=1};
$PARAM[Qs{^T}]{inst.Qs, i0=1};
$PARAM[b{I}]{inst.b, i0=1};
var Z{T}, integer, >= 0;
var x{I}, >= 0;

$MVP_FLOW[^Z{T}]{inst.Ws, inst.ws, ["x[{0}]".format(i+1) for i in range(inst.m)], i0=1};
minimize obj: sum{t in T} Z[t]*Cs[t];
s.t. demand{i in I}: x[i] >= b[i];
s.t. zub{t in T: Qs[t] != -1}: Z[t] <= Qs[t];
end;

is replaced by:

param Cs{T};
param Qs{T};
param b{I};
var Z{T}, integer, >= 0;
var x{I}, >= 0;
/* arc-flow model with graph compression for instance.mvp */
/* Z[t] is the amount of flow on the feedback arc for bins of type t */
/* x[i] = amount of flow on arcs associated with items of type i */
minimize obj: sum{t in T} Z[t]*Cs[t];
s.t. demand{i in I}: x[i] >= b[i];
s.t. zub{t in T: Qs[t] != -1}: Z[t] <= Qs[t];
end;

MVP_GRAPH

Usage: $VBP_GRAPH[V_name, A_name]{W, w, labels, bounds=None, binary=False, S="S", T="T", LOSS="LOSS"};

Requirements: VPSolver

Description: generates compressed arc-flow graphs for vector packing instances.

Parameters:

• AMPL:
  • V_name: name for the set of vertices;
  • A_name: name for the set of arcs.
• Python:
  • W: bin capacity;
  • w: item weights;
  • labels: item labels;
  • bounds: maximum demand for each item;
  • binary: binary patterns (if True) or general integer patterns (if False);
  • S: source node label;
  • T: target node label;
  • LOSS: loss arcs label.

Creates:

• AMPL:
  • set 'V_name': set of vertices;
  • set 'A_name': set of arcs.
• Python:
  • _sets['V_name']: set of vertices;
  • _sets['A_name']: set of arcs.

Examples:

$EXEC{
from pyvpsolver import VBP
instance = VBP.from_file("instance.vbp")
};
$PARAM[b{I}]{instance.b};
$VBP_GRAPH[V,A]{instance.W, instance.w, range(1, instance.m+1)};

# Variables:
var Z, integer, >= 0; # amount of flow in the feedback arc
var f{A}, integer, >= 0; # amount of flow in each arc
# Objective:
maximize obj: f['T', 'S', 'LOSS'];
# Flow conservation constraints:
s.t. flowcon{k in V}: 
    sum{(u,v,i) in A: v == k} f[u,v,i]  - sum{(u,v,i) in A: u == k} f[u, v, i] = 0;
# Demand constraints:
s.t. demand{k in I}: sum{(u,v,i) in A: i == k} >= b[i];

---

Copyright © Filipe Brandão. All rights reserved.
E-mail: [email protected]. [Homepage]