Crate dypdl

Expand description

§DyPDL

A library for Dynamic Programming Description Language (DyPDL).

§Examples

Example to model TSPTW.

use dypdl::prelude::*;

// TSPTW instance.
// 0 is the depot, and 1, 2, and 3 are customers.
let n_customers = 4;
// Beginnings of time windows.
let ready_time = vec![0, 5, 0, 8];
// Ends of time windows.
let due_date = vec![0, 16, 10, 14];
// Travel time.
let distance_matrix = vec![
    vec![0, 3, 4, 5],
    vec![3, 0, 5, 4],
    vec![4, 5, 0, 3],
    vec![5, 4, 3, 0],
];

// Minimization and integer cost by default.
let mut model = Model::default();

// Define an object type.
let customer = model.add_object_type("customer", n_customers).unwrap();

// Define state variables.
// Unvisited customers, initially 1, 2, and 3.
let unvisited = model.create_set(customer, &[1, 2, 3]).unwrap();
let unvisited = model.add_set_variable("U", customer, unvisited).unwrap();
// Current location, initially 0.
let location = model.add_element_variable("i", customer, 0).unwrap();
// Current time, less is better, initially 0.
let time = model.add_integer_resource_variable("t", true, 0).unwrap();

// Define tables of constants.
let ready_time: Table1DHandle<Integer> = model.add_table_1d("a", ready_time).unwrap();
let due_date: Table1DHandle<Integer> = model.add_table_1d("b", due_date).unwrap();
let distance: Table2DHandle<Integer> = model.add_table_2d(
    "c", distance_matrix.clone()
).unwrap();

// Define transitions.
let mut visits = vec![];

// Returning to the depot;
let mut return_to_depot = Transition::new("return to depot");
// The cost is the sum of the travel time and the cost of the next state.
return_to_depot.set_cost(distance.element(location, 0) + IntegerExpression::Cost);
// Update the current location to the depot.
return_to_depot.add_effect(location, 0).unwrap();
// Increase the current time.
return_to_depot.add_effect(time, time + distance.element(location, 0)).unwrap();
// Add the transition to the model.
// When this transition is applicable, no need to consider other transitions.
model.add_forward_forced_transition(return_to_depot.clone());
visits.push(return_to_depot);

for j in 1..n_customers {
    // Visiting each customer.
    let mut visit = Transition::new(format!("visit {j}"));
    visit.set_cost(distance.element(location, j) + IntegerExpression::Cost);
    // Remove j from the set of unvisited customers.
    visit.add_effect(unvisited, unvisited.remove(j)).unwrap();
    visit.add_effect(location, j).unwrap();
    // Wait until the ready time.
    let arrival_time = time + distance.element(location, j);
    let start_time = IntegerExpression::max(arrival_time.clone(), ready_time.element(j));
    visit.add_effect(time, start_time).unwrap();
    // The time window must be satisfied.
    visit.add_precondition(
        Condition::comparison_i(ComparisonOperator::Le, arrival_time, due_date.element(j))
    );
    // Add the transition to the model.
    model.add_forward_transition(visit.clone()).unwrap();
    visits.push(visit);
}

// Define a base case.
// If all customers are visited and the current location is the depot, the cost is 0.
let is_depot = Condition::comparison_e(ComparisonOperator::Eq, location, 0);
model.add_base_case(vec![unvisited.is_empty(), is_depot.clone()]).unwrap();

// Define redundant information, which is possibly useful for a solver.
// Define state constraints.
for j in 1..n_customers {
    // The shortest arrival time, assuming the triangle inequality.
    let arrival_time = time + distance.element(location, j);
    // The salesperson must be able to visit each unvisited customer before the deadline.
    let on_time = Condition::comparison_i(
        ComparisonOperator::Le, arrival_time, due_date.element(j)
    );
    model.add_state_constraint(!unvisited.contains(j) | on_time).unwrap();
}

// Define a dual bound.
// The minimum distance to each customer.
let min_distance_to = distance_matrix.iter()
    .enumerate()
    .map(|(j, row)| row.iter().enumerate().filter_map(|(k, d)| {
            if j == k {
               None
            } else {
               Some(*d)
            }
        })
    .min().unwrap()).collect();
let min_distance_to: Table1DHandle<Integer> = model.add_table_1d(
    "c_min", min_distance_to
).unwrap();
let to_depot: IntegerExpression = is_depot.if_then_else(0, min_distance_to.element(0));
let dual_bound: IntegerExpression = min_distance_to.sum(unvisited) + to_depot;
model.add_dual_bound(dual_bound).unwrap();

// Solution.
let solution = [visits[2].clone(), visits[3].clone(), visits[1].clone(), visits[0].clone()];
// Solution cost.
let cost = 14;
// Verify the solution.
assert!(model.validate_forward(&solution, cost, true));

Re-exports§

pub use variable_type::Continuous;
pub use variable_type::Element;
pub use variable_type::Integer;
pub use variable_type::Set;
pub use variable_type::Vector;

Modules§

expression: A module for expressions.
prelude: DyPDL’s prelude.
variable_type: A module defining types of values of state variables.

Structs§

BaseCase: Base case.
BooleanStateFunction: A struct wrapping an id.
ContinuousResourceVariable: A struct wrapping an id.
ContinuousStateFunction: A struct wrapping an id.
ContinuousVariable: A struct wrapping an id.
Effect: Effect in a transition.
ElementResourceVariable: A struct wrapping an id.
ElementStateFunction: A struct wrapping an id.
ElementVariable: A struct wrapping an id.
GroundedCondition: Condition with element parameters.
IntegerResourceVariable: A struct wrapping an id.
IntegerStateFunction: A struct wrapping an id.
IntegerVariable: A struct wrapping an id.
Model: DyPDL model.
ModelErr: Error in modeling.
ObjectType: A struct wrapping an id.
ResourceVariables: Resource variables.
SetStateFunction: A struct wrapping an id.
SetVariable: A struct wrapping an id.
SignatureVariables: State variables other than resource variables.
State: State in DyPDL.
StateFunctionCache: Data structure to cache the values of state functions.
StateFunctions: Definition of state functions.
StateMetadata: Information about state variables.
Table: Table of constants.
Table1D: 1D table of constants.
Table1DHandle: A struct wrapping the id of a table.
Table2D: 2D table of constants.
Table2DHandle: A struct wrapping the id of a table.
Table3D: 3D table of constants.
Table3DHandle: A struct wrapping the id of a table.
TableData: Tables of constants havint a particular type.
TableHandle: A struct wrapping the id of a table.
TableRegistry: Tables of constants.
Transition: Transition.
TransitionDominance: Transition dominance.
TransitionId: ID of a transition.
VectorVariable: A struct wrapping an id.

Enums§

CostExpression: Wrapper for an integer expression or a continuous expression.
CostType: Type of numeric values to represent the costs of states.
ReduceFunction: How to compute the value of a state given applicable transitions.

Traits§

AccessPreference: Trait for accessing preference of resource variables.
AccessTarget: Trait for accessing the values in the target state.
AddDualBound: Trait for adding a dual bound.
AddEffect: Trait for adding an effect.
CheckExpression: Trait for checking if an expression is valid.
CheckVariable: Trait for checking if a variable is defined.
GetObjectTypeOf: Trait for getting the object type.
HasShape
StateInterface: Trait representing a state in DyPDL.
TableInterface: Trait for adding and updating tables of constants.
TransitionInterface: Trait representing a transition.

Crate dypdl

Crate dypdl Copy item path

§DyPDL

§Examples

Re-exports§

Modules§

Structs§

Enums§

Traits§

Crate dypdl