DDO 是一个基于 MDD 优化的通用且高效的框架

DDO 是一个真正的通用框架，用于在 Rust 中开发基于 MDD 的组合优化求解器。其目标是让您将优化问题描述为一个动态规划程序，以及一个松弛。

当将问题的动态规划视为一个状态转换系统时，松弛的作用是将转换系统的不同节点合并成一个代表它们的节点。在这种情况下，确保优化算法正确性的唯一条件是替换节点必须是合并节点的所有可行性的上近似。

额外优势： 通过使用 ddo，您将能够利用所有硬件并行解决您的优化问题。

设置

此库是用稳定的 Rust（1.41，撰写时）编写的。因此，它应该使用 cargo（与您的 Rust 工具链一起安装）进行编译。感谢它，无论您在哪个平台上工作，编译和使用 ddo 都会非常简单。

一旦您安装了 Rust 工具链，将 ddo 添加为 Cargo.toml 文件中的依赖项并构建您的项目即可使用 ddo。

[dependencies]
ddo = "1.0.0"

简单而完整的示例

以下示例说明了如何构建一个基于 DDO 的完整求解器，用于解决 二进制背包问题。

第一步始终是使用动态规划术语描述您尝试解决的优化问题。然后，您还应为问题提供一个松弛。

从对问题的描述中，ddo将推导出一个MDD，并将其用于找到您问题的最优解。然而，对于一个合理规模的问题，在内存中展开完整的状态空间是不可行的。因此，您还应该向ddo提供一个松弛。在这个上下文中，松弛意味着一种将MDD中的多个节点合并的策略，以便生成一个对合并节点的过近似（状态 + 最长路径，其中最长路径是您尝试优化的目标函数的值）。

将问题描述为动态规划

在这个示例中要做的第一件事是用动态规划术语描述二进制背包问题。这意味着描述DP模型的状态以及DP模型本身。

/// In our DP model, we consider a state that simply consists of the remaining 
/// capacity in the knapsack. Additionally, we also consider the *depth* (number
/// of assigned variables) as part of the state since it useful when it comes to
/// determine the next variable to branch on.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct KnapsackState {
    /// the number of variables that have already been decided upon in the complete
    /// problem.
    depth: usize,
    /// the remaining capacity in the knapsack. That is the maximum load the sack
    /// can bear without cracking **given what is already in the sack**.
    capacity: usize
}

/// This structure represents a particular instance of the knapsack problem.
/// This is the structure that will implement the knapsack model.
/// 
/// The problem definition is quite easy to understand: there is a knapsack having 
/// a maximum (weight) capacity, and a set of items to chose from. Each of these
/// items having a weight and a profit, the goal is to select the best subset of
/// the items to place them in the sack so as to maximize the profit.
struct Knapsack {
    /// The maximum capacity of the sack (when empty)
    capacity: usize,
    /// the profit of each item
    profit: Vec<usize>,
    /// the weight of each item.
    weight: Vec<usize>,
}

/// For each variable in the decision problem, there are two possible choices:
/// either we take the item in the sack, or we decide to leave it out. This
/// constant is used to indicate that the item is to be taken in the sack.
const TAKE_IT: isize = 1;
/// For each variable in the decision problem, there are two possible choices:
/// either we take the item in the sack, or we decide to leave it out. This
/// constant is used to indicate that the item is to be left out of the sack.
const LEAVE_IT_OUT: isize = 0;

/// This is how you implement the labeled transition system (LTS) semantics of
/// a simple dynamic program solving the knapsack problem. The definition of
/// each of the methods should be pretty clear and easy to grasp. Should you
/// want more details on the role of each of these methods, then you are 
/// encouraged to go checking the documentation of the `Problem` trait.
impl Problem for Knapsack {
    type State = KnapsackState;

    fn nb_variables(&self) -> usize {
        self.profit.len()
    }
    fn for_each_in_domain(&self, variable: Variable, state: &Self::State, f: &mut dyn DecisionCallback)
    {
        if state.capacity >= self.weight[variable.id()] {
            f.apply(Decision { variable, value: TAKE_IT });
            f.apply(Decision { variable, value: LEAVE_IT_OUT });
        } else {
            f.apply(Decision { variable, value: LEAVE_IT_OUT });
        }
    }
    fn initial_state(&self) -> Self::State {
        KnapsackState{ depth: 0, capacity: self.capacity }
    }
    fn initial_value(&self) -> isize {
        0
    }
    fn transition(&self, state: &Self::State, dec: Decision) -> Self::State {
        let mut ret = state.clone();
        ret.depth  += 1;
        if dec.value == TAKE_IT { 
            ret.capacity -= self.weight[dec.variable.id()] 
        }
        ret
    }
    fn transition_cost(&self, _state: &Self::State, dec: Decision) -> isize {
        self.profit[dec.variable.id()] as isize * dec.value
    }

    fn next_variable(&self, next_layer: &mut dyn Iterator<Item = &Self::State>) -> Option<Variable> {
        let n = self.nb_variables();
        next_layer.filter(|s| s.depth < n).next().map(|s| Variable(s.depth))
    }
}

为问题提供松弛

我们将定义的松弛可能是你能想到的最简单的。当需要定义一个新的状态来替换那些超过MDD最大宽度的情况时，我们将简单地保留具有最大容量的状态，因为它至少使所有具有较小容量的可能行为都是可行的。

可选地，我们还可以在我们的松弛中实现一个粗略的上界估计器。然而，在这个最小化示例中我们不会这样做，因为框架为您提供了默认实现。如果您要覆盖默认实现，则需要实现fast_upper_bound()方法，这是Relaxation特质的。

/// In addition to a dynamic programming (DP) model of the problem you want to solve, 
/// the branch and bound with MDD algorithm (and thus ddo) requires that you provide
/// an additional relaxation allowing to control the maximum amount of space used by
/// the decision diagrams that are compiled. 
/// 
/// That relaxation requires two operations: one to merge several nodes into one 
/// merged node that acts as an over approximation of the other nodes. The second
/// operation is used to possibly offset some weight that would otherwise be lost 
/// to the arcs entering the newly created merged node.
/// 
/// The role of this very simple structure is simply to provide an implementation
/// of that relaxation.
/// 
/// # Note:
/// In addition to the aforementioned two operations, the KPRelax structure implements
/// an optional `fast_upper_bound` method. Which one provides a useful bound to 
/// prune some portions of the state-space as the decision diagrams are compiled.
/// (aka rough upper bound pruning).
struct KPRelax;
impl Relaxation for KPRelax {
    type State = KnapsackState;

    fn merge(&self, states: &mut dyn Iterator<Item = &Self::State>) -> Self::State {
        states.max_by_key(|node| node.capacity).copied().unwrap()
    }

    fn relax(&self, _source: &Self::State, _dest: &Self::State, _merged: &Self::State, _decision: Decision, cost: isize) -> isize {
        cost
    }
}

注入支配关系

可选地，定义在整个搜索过程中获得的各个状态之间的支配关系。在这种情况下，如果s1的容量大于或等于s2的容量，并且s1的值大于s2，则s1支配s2。

pub struct KPDominance;
impl Dominance for KPDominance {
    type State = KnapsackState;
    type Key = usize;

    fn get_key(&self, state: Arc<Self::State>) -> Option<Self::Key> {
        Some(state.depth)
    }

    fn nb_dimensions(&self, _state: &Self::State) -> usize {
        1
    }

    fn get_coordinate(&self, state: &Self::State, _: usize) -> isize {
        state.capacity as isize
    }

    fn use_value(&self) -> bool {
        true
    }
}

状态排序

为了创建一个基于ddo的高效求解器，您需要提供的最后一个要素是状态排序。这是一个启发式方法，用于比较状态以确定哪些是最有希望的，哪些是最不利的。这样，每当MDD需要执行限制或松弛时，它只需保留最有希望的节点并丢弃其他节点。

/// The last bit of information which we need to provide when implementing a ddo-based
/// solver is a `StateRanking`. This is an heuristic which is used to select the most
/// and least promising nodes as a means to only delete/merge the *least* promising nodes
/// when compiling restricted and relaxed DDs.
struct KPranking;
impl StateRanking for KPranking {
    type State = KnapsackState;

    fn compare(&self, a: &Self::State, b: &Self::State) -> std::cmp::Ordering {
        a.capacity.cmp(&b.capacity)
    }
}

解决问题

/// Then instantiate a solver and spawn as many threads as there are hardware
/// threads on the machine to solve the problem.
fn main() {
    // 1. Create an instance of our knapsack problem
    let problem = Knapsack {
        capacity: 50,
        profit  : vec![60, 100, 120],
        weight  : vec![10,  20,  30]
    };

    // 2. Create a relaxation of the problem
    let relaxation = KPRelax;

    // 3. Create a ranking to discriminate the promising and uninteresting states
    let heuristic = KPRanking;

    // 4. Define the policy you will want to use regarding the maximum width of the DD
    let width = FixedWidth(100); // here we mean max 100 nodes per layer
    
    // 5. Add a dominance relation checker
    let dominance = SimpleDominanceChecker::new(KPDominance, problem.nb_variables());

    // 6. Decide of a cutoff heuristic (if you don't want to let the solver run for ever)
    let cutoff = NoCutoff; // might as well be a TimeBudget (or something else)

    // 7. Create the solver fringe
    let mut fringe = SimpleFringe::new(MaxUB::new(&heuristic));
    
    // 8. Instantiate your solver
    let mut solver = DefaultSolver::new(
          &problem, 
          &relaxation, 
          &heuristic, 
          &width, 
          &dominance,
          &cutoff, 
          &mut fringe);

    // 9. Maximize your objective function
    // the outcome provides the value of the best solution that was found for
    // the problem (if one was found) along with a flag indicating whether or
    // not the solution was proven optimal. Hence an unsatisfiable problem
    // would have `outcome.best_value == None` and `outcome.is_exact` true.
    // The `is_exact` flag will only be false if you explicitly decide to stop
    // searching with an arbitrary cutoff.
    let outcome = solver.maximize();
    // The best solution (if one exist) is retrieved with
    let solution = solver.best_solution();

    // 10. Do whatever you like with the optimal solution.
    assert_eq!(Some(220), outcome.best_value);
    println!("Solution");
    for decision in solution.unwrap().iter() {
        if decision.value == 1 {
            println!("{}", decision.variable.id());
        }
    }
}

构建更高级的示例（配套二进制文件）

上述（简单）示例的源代码提供在本项目的示例部分。同时，这些示例提供了更高级求解器的实现。具体来说，它提供了以下实现：

• 最大独立集问题（MISP）
• 最大2可满足性（MAX2SAT）
• 最大切割问题（MCP）
• 二进制背包

这些示例使用以下命令用cargo编译：cargo build --release --all-targets。编译完成后，您将在

• $project/target/release/examples/knapsack
• $project/target/release/examples/max2sat
• $project/target/release/examples/mcp
• $project/target/release/examples/misp

如果您对使用这些程序有任何疑问，只需运行<程序> -h，它应显示一条有用的消息，解释如何使用它。

注意

MISP、MAX2SAT和MCP的实现对应于Bergman等人提出的公式和松弛。

引用DDO

如果您使用DDO，或者发现它对您有用（研究、教学、商业等），请引用

@misc{gillard:20:ddo,
    author       = {Xavier Gillard, Pierre Schaus, Vianney Coppé},
    title        = {Ddo, a generic and efficient framework for MDD-based optimization},
    howpublished = {IJCAI-20},
    year         = {2020},
    note         = {Available from \url{https://github.com/xgillard/ddo}},
}

变更日志

• 版本 0.3.0 添加了截止机制，这可能会迫使求解器停止尝试证明最优解。一些返回类型已经进行了调整，以考虑这种可能性。

参考文献

• David Bergman, Andre A. Cire, Ashish Sabharwal, Samulowitz Horst, Saraswat Vijay，以及 Willem-Jan 和 van Hoeve。在 Helmut Simonis 编著的《约束规划中人工智能和运筹技术的整合》（Integration of AI and OR Techniques in Constraint Programming），第 8451 卷，第 351–367 页。Springer，2014 年。
• David Bergman 和 Andre A. Cire。在《决策图优化中的理论洞察和算法工具》（Theoretical insights and algorithmic tools for decision diagram-based optimization）中，Constraints，21(4):533–556，2016 年。
• David Bergman, Andre A. Cire, Willem-Jan van Hoeve，以及 J. N. Hooker。在《决策图优化》（Decision Diagrams for Optimization）中，Springer，2016 年。
• David Bergman, Andre A. Cire, Willem-Jan van Hoeve，以及 J. N. Hooker。在《决策图进行离散优化》（Discrete optimization with decision diagrams）中，INFORMS Journal on Computing，28(1):47–66，2016 年。