Skip to content

STMTS_VPSolver

Jump to bottom
Filipe Brandão edited this page Feb 19, 2016 · 25 revisions

VPSolver: Vector Packing Solver

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("data/instance.vbp")
};
$SET[I]{range(instance.m)};
$PARAM[b{^I}]{instance.b};
var x{I}, >= 0;
$VBP_FLOW[Z]{instance.W, instance.w, ["x[%d]"%i for i in range(instance.m)]};    

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

is replaced by:

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("data/instance.vbp")
};
$SET[I]{range(instance.m)};
$PARAM[b{^I}]{instance.b};
$VBP_GRAPH[V,A]{instance.W, instance.w, _sets['I']};

# 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: $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("data/instance.vbp")
};
$SET[I]{range(instance.m)};
$PARAM[b{^I}]{instance.b};
var x{I}, >= 0;
$VBP_FLOW[Z]{instance.W, instance.w, ["x[%d]"%i for i in range(instance.m)]};    

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

is replaced by:

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;

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("data/instance.vbp")
};
$SET[I]{range(instance.m)};
$PARAM[b{^I}]{instance.b};
$VBP_GRAPH[V,A]{instance.W, instance.w, _sets['I']};

# 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]

Clone this wiki locally