ナップサック問題を制約充足ソルバーを使って解く OptaPlanner チュートリアル

この記事は FastDOCTOR After Advent Calendar 26日の記事です。次の日の記事は 外注で初期開発したシステムを内製化するためにやったこと です。

概要

ナップサック問題は比較的簡単な問題であって、特別な道具は必要ないのですが、あえてそういう問題を制約充足ソルバーで解くことによって、やさしく学ぶことができるのでは、と考えています。

FastDOCTOR Technologies のテックブログでは、 OptaPlanner について実践的なケースを紹介していますので、よければご覧ください。

【最適化問題】「医療の往診サービスで、医師とドライバーのペアが特定のエリアを巡回する最善のルートを考えよ」をソルバープログラムで解いてみた

ナップサック問題

ナップサック問題とは、容量が決まっている入れ物のなかに、合計金額が最大になるように、品物を詰める、という問題です。以下のような問題文のものです。

以下のように、品物の重さと価格が与えられている。

- a [kg] の k [円] の品物
- b [kg] の l [円] の品物
- c [kg] の m [円] の品物
- d [kg] の o [円] の品物
- e [kg] の p [円] の品物
- f [kg] の q [円] の品物

weight [kg] まで入れることができるナップサックに詰めるとき、その最大の価格はいくらか？

いってみれば「コスパ」の問題なのですが、では価格を重さで割ったコスパが大きいものから詰めていったからといって、常に最大値になるとは限らないというのが難しいところでもあり、面白いところでもあります。

この問題は組合せ最適化の代表的なものですが、競技プログラミングにおいても入門的な位置付けで、よく知られています。この問題には、ただただ繰り返しや配列や関数などのプログラミングの基礎概念を知っているだけではなかなか解けず、問題に応じた考え方をしないと上手に解くことができないところがあって、それが競技プログラミングの問題としてよく出題されているのだと思います。

通常の解き方

通常は、動的計画法という方法を使って解きます。

うまい再帰関数を実装することで解くのですが、再帰関数ゆえに計算量が多くなってしまいます。そこでメモ化というテクニックを使い、この引数を受けたらこの値を返す、というキャッシュのようなものを作ります。ここで、問題文で求められているものが最大値だということを思い出すと、この関数を実行する前に、キャッシュをあらかじめ計算して埋めることができてしまうのです。

配列や関数など、ふつうのプログラミング言語なら必ず備えている機能だけを使って実装でき、特別なライブラリは必要ありません。

この記事で紹介する解き方

制約充足ソルバーというソフトウェアを使って、このナップサック問題を解いてみます。

ナップサック問題は、上述のとおり、すでに無駄のないエレガントな解き方が知られているので、ソルバーなどという特別な道具は必要ありません。

しかし、 OptaPlanner というソルバーを紹介するにあたって、あえてナップサック問題という古典的で比較的やさしい問題をあげることで、ソルバーの機能に注目して学ぶことができると考えています。

リポジトリ

この記事でとりあげているコードは、以下のリポジトリで公開しているものです。

Item

まずは「品物」をあらわす Item クラスを Plain Old Java Object で実装していきます。

品物 Item は、価格 value と重さ weight をフィールドとして持ちます。そして「ナップサックに入っている (選ばれた) かどうか」をあらわすため、knapsack フィールドもつくります。

そのあとは単純にゲッター・セッターを定義しています。

id というフィールド、引数をもたないコンストラクタがあり、不自然に感じるかもしれませんが、これはソルバーのためのもので、あとで必要になります。

package org.example;

public class Item {

    private Integer id;
    private Integer value;
    private Integer weight;
    private Knapsack knapsack;

    Item() {
    }

    Item(Integer id, Integer value, Integer weight) {
        this.id = id;
        this.value = value;
        this.weight = weight;
    }

    public boolean belongsToKnapsack() {
        return Objects.nonNull(this.knapsack);
    }

    public Integer getId() {
        return this.id;
    }

    public Integer getValue() {
        return this.value;
    }

    public Integer getWeight() {
        return this.weight;
    }

    public Knapsack getKnapsack() {
        return this.knapsack;
    }

    public void setKnapsack(Knapsack knapsack) {
        this.knapsack = knapsack;
    }

}

Knapsack

品物をしまう容器としてのナップサックは、当然 capacity をもちます。 id と引数が空のコンストラクタは、上述したように、ソルバーのための準備です。

package org.example;

public class Knapsack {

    private Integer id;
    private Integer capacity;

    Knapsack() {
    }

    Knapsack(Integer id, Integer capacity) {
        this.id = id;
        this.capacity = capacity;
    }

    public Integer getId() {
        return this.id;
    }

    public Integer getCapacity() {
        return this.capacity;
    }

}

制約の準備

制約充足ソルバーと呼ばれるので、当然制約をコードとして書いていきます。 defineConstraints メソッドで、ソルバーに「こういう制約を満たしてほしい！」と伝えることができます。

package org.example;

import org.optaplanner.core.api.score.stream.ConstraintProvider;
import org.optaplanner.core.api.score.stream.ConstraintFactory;
import org.optaplanner.core.api.score.stream.Constraint;

public class OrtizConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
        };
    }

}

制約 (1) ナップサックの容量を超えないこと

「ナップサックの容量を超えないこと」という意味を penalizeKnapsackCapacityOver というメソッド名で表現しています。

この制約のなかにある forEach, filter, groupBy, penalize などの DSL が、 初出では面食らうのですが、同時に OptaPlanner の面白いところでもあります。

    Constraint penalizeKnapsackCapacityOver(ConstraintFactory constraintFactory) {
        return constraintFactory
                .forEach(Item.class)
                .filter((item) -> item.belongsToKnapsack())
                .groupBy(Item::getKnapsack, sum(Item::getWeight))
                .penalize(HardSoftScore.ONE_HARD, (knapsack, weight) -> knapsack.getCapacity() < weight ? weight - knapsack.getCapacity() : 0)
                .asConstraint("penalize knapsack capacity over");
    }

forEach はオブジェクトをひとつずつ選ぶものです。「選ぶぞ！」と考えてこう書いているというより、まずはここから書いていく、という発想で書いています。

filter はその名の通り、条件を満たしたものだけをこのあと対象にしていくためのものです。

groupBy は、ここまで forEach したり filter したりしたオブジェクトに対して、グループ化していきます。面白いのは、ただグループ化するのではなく、グループ化しながら、今回のように sum 関数でグループごとの合計値をもつことができる、ということです。ナップサック問題ではナップサックはひとつしか登場しないので、ナップサックに入った品物とそうでないもののグループしかないのですが、あえて groupBy を紹介するためにこうしていた、ということもあります。

penalize は、これもその名の通り、もしそういうものがあれば罰となるスコアをつける、というものです。

制約 (2) 価格を最大にすること

ナップサック問題らしい、価格を最大にすることを制約として表現すると、以下のようになります。

    Constraint rewardKnapsackValue(ConstraintFactory constraintFactory) {
        return constraintFactory
                .forEach(Item.class)
                .filter((item) -> item.belongsToKnapsack())
                .groupBy(Item::getKnapsack, sum(Item::getValue))
                .reward(HardSoftScore.ONE_SOFT, (knapsack, value) -> value)
                .asConstraint("reward knapsack value");
    }

forEach, filter, groupBy は前述したとおりでした。 reward というのは、 penalize の逆になります。

Item クラスにアノテーションをつける

さきほど POJO として実装した Item クラスを OptaPlanner がよしなに取り扱えるようにするため、アノテーションをつけていきます。

今回は、 id が PlanningId であるということと、 knapsack がどの値をとるか、 null を許すか、ということを指定しています。

Item.java

+    @PlanningId
     private Integer id;
     private Integer value;
     private Integer weight;
+     @PlanningVariable(valueRangeProviderRefs = { "knapsackRange" }, nullable = true)

Main.java を書く

ようやく Main.java の main 関数を書いていきます。が、ここは OptaPlanner のチュートリアルのままです。

withTerminationSpentLimit のところでソルバーの実行時間を指定しています。

package org.example;

import org.optaplanner.core.api.solver.SolverFactory;
import org.optaplanner.core.config.solver.SolverConfig;

import java.time.Duration;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
        var solution = new OrtizSolution();
        var solverConfig = new SolverConfig()
                .withSolutionClass(OrtizSolution.class)
                .withEntityClasses(Item.class)
                .withConstraintProviderClass(OrtizConstraintProvider.class)
                .withTerminationSpentLimit(Duration.ofSeconds(10));
        SolverFactory<OrtizSolution> solverFactory = SolverFactory.create(solverConfig);
        var solver = solverFactory.buildSolver();
        var sol = solver.solve(solution);

        System.out.println(sol.getScore());
    }
}

実行してみる

ふつうなら標準入力から受け取ってデシリアライズするべきところですが、今回は Main.java に問題を手で書いていきます。 AtCoder Beginner Contest 032 D 問題の入力例 1 を解いてみます。

ナップサックの容量は 10 で、3つの品物があり、

id: 1, 価格 15, 重さ 9
id: 2, 価格 10, 重さ 6
id: 31, 価格 6, 重さ 4

となる。

これをコードであらわすと、このようになります。

        solution.addKnapsack(new Knapsack(1, 10));
        solution.addItem(new Item(1, 15, 9));
        solution.addItem(new Item(2, 10, 6));
        solution.addItem(new Item(3, 6, 4));

実行すると、このように表示されます。

0hard/16soft

Process finished with exit code 0

制約のスコアづけの際に hard 制約と soft 制約に分かれていて、「ナップサックの容量を超えない」というのを hard 制約として、「できるだけ価格を最大化する」を soft 制約として表現しました。今回の 16soft の部分が「最大の詰め方をすると価格が16になるよ」ということを表しています。

まとめ

ナップサック問題という比較的簡単な問題を、制約充足ソルバーという鈍重なツールを使って解くという、いささか牛刀割鶏な解法を紹介しました。こんなことをしても競技プログラミングのスコアはまったく上がりませんが、競技プログラミングの問題は整数計画問題なのだと理解したり、こういった簡単な問題を入り口として OptaPlanner を知ったり、ということは価値のあることだと思います。

お読みくださりありがとうございました！