Skip to content

STMTS_VPSolver

Jump to bottom
Filipe Brandão edited this page May 20, 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("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: label for the source node;
    • T: label for the target node;
    • LOSS: label for loss arcs.

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 for the set of variables associated with each feedback arc;
  • Python:
    • Ws: list of bin capacities;
    • ws: list of lists of weights 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);
    • i0: initial index of zvars (zvars[i0], zvars[i0+1], ...).

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
instance = MVP.from_file("instance.mvp")
};
$PARAM[Cs{T}]{instance.Cs, i0=1};
$PARAM[Qs{^T}]{instance.Qs, i0=1};
$PARAM[b{I}]{instance.b, i0=1};
var Z{T}, integer, >= 0;
var x{I}, >= 0;
$MVP_FLOW[^Z{T}]{
    instance.Ws, instance.ws, 
    ["x[{0}]".format(i+1) for i in range(instance.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: $MVP_GRAPH[V_name, A_name]{Ws, ws, labels, bounds=None, binary=False, S="S", Ts=None, 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:
    • Ws: list of bin capacities;
    • ws: list of lists of weights of item incarnations;
    • labels: item labels;
    • bounds: maximum demand for each item;
    • binary: binary patterns (if True) or general integer patterns (if False);
    • S: label for the source node;
    • Ts: list of labels for the targets;
    • LOSS: label for loss arcs.

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 MVP
instance = MVP.from_file("instance.mvp")
};
$PARAM[Cs{T}]{instance.Cs, i0=1};
$PARAM[Qs{^T}]{instance.Qs, i0=1};
$PARAM[b{I}]{instance.b, i0=1};
$MVP_GRAPH[V, A]{
    instance.Ws, instance.ws,
    {(i, j): (i+1, j+1) 
        for i in range(instance.m) 
        for j in range(len(instance.ws[i]))
    },
    instance.b,
    S="S", 
    Ts=["T{}".format(i+1) for i in range(len(instance.Ws))], 
    LOSS=("LOSS", "ARC")
};
var f{(u, v, i, o) in A}, >= 0, <= (if i != 'LOSS' then b[i] else Infinity);
minimize obj: sum{t in T} Cs[t] * f['T'&t, 'S', 'LOSS', 'ARC'];
s.t. flow_con{k in V}:
    sum{(u, v, i, o) in A: v==k} f[u, v, i, o] - sum{(u, v, i, o) in A: u==k} f[u, v, i, o] = 0;
s.t. demand{it in I}: sum{(u, v, i, o) in A: i == it} f[u, v, i, o] >= b[it];

Copyright © 2015-2016 Filipe Brandão < [email protected] >. All rights reserved.

Clone this wiki locally