建模：高效建模子集选择

Question

我想使用 Optaplanner 建模和解决的问题是为运动队（此处：足球）创建花名册。也就是说：根据几个标准，从所有可用的玩家中，select 11 人。我使用 hard/medium/soft 分数来定义有效的解决方案，例如一个硬性标准，指定一名守门员必须出现在名单中。玩家的 selected 顺序无关紧要。

我目前有这个作为我的 PlanningEntity:

@PlanningEntity
public class Roster
{
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member1;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member2;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member3;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member4;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member5;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member6;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member7;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member8;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member9;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member10;
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member11;

    public List<RosterMember> getMembers()
    {
        return Lists.newArrayList(member1, member2, member3, member4, member5, member6, member7, member8, member9, member10, member11);
    }
}

对于得分计算，我只使用 getMembers，即我不关心玩家是分配给 member1 还是 member2。求解器主要使用默认配置，并配置为在 100 秒后超时，或者在 10 秒后没有任何改进。

在一些示例数据集上尝试过之后，我注意到求解器在大多数情况下找不到最优解（但至少有效），例如不是最好的守门员 selected（这通常很容易看出，因为可用的人不多，应该只选一个）。

我怀疑这与我对 PlanningEntity 的建模方式有关：由于所有花名册成员都可以单独设置，这似乎使解决方案 space 变得不必要地大。如前所述，将成员分配到哪个字段并不重要。仅当（或更确切地说，谁）被指派以及谁没有被指派时才重要。所以我基本上需要select一部分玩家，同时满足一些约束和优化标准。

然而，简单地将 List of RosterMember 注释为 @PlanningVariable 似乎不起作用。我在示例中也找不到类似的情况。我想这应该是一个简单的建模示例？

到目前为止，我能想到的唯一想法是对一些（硬）约束进行显式建模，例如将其中一个规划变量的范围限制为 goalkeeper，同时将所有其他变量限制为 non-goalkeeper（或者甚至更远）。根据文档 (4.3.5.2.3.)，应该避免这种情况。

编辑： 我只有一个花名册实例。我假设不同团队的花名册不相关，并按顺序计划运行每个团队的求解器。

编辑 2: 按照建议，我现在有了这个而不是以前的 Roster:

@PlanningEntity
public class RosterAssignment
{
    @PlanningVariable(valueRangeProviderRefs = {"candidates"})
    private RosterMember member;
}

在创建初始未解决的解决方案时，我添加了 11 个空的 RosterAssignment。但是，在创建起始解决方案后，求解器似乎无法改进任何内容：

(DefaultConstructionHeuristicPhase.java:158) Construction Heuristic phase (0) ended: step total (11), time spent (111), best score (-1hard/-2medium/1275soft).
(DefaultLocalSearchPhase.java:152) Local Search phase (1) ended: step total (375104), time spent (10111), best score (-1hard/-2medium/1275soft).
(DefaultSolver.java:238)       Solving ended: time spent (10129), best score (-1hard/-2medium/1275soft), average calculate count per second (75545), environment mode (REPRODUCIBLE).

Answer 1

参见网球示例：对于每个 Day 实例，有 4 个 TeamAssignment 实例，而不是 Day 本身的 4 个规划变量。

尽管搜索 space 相同，但默认移动（changeMove 和 swapMove）效果更好，因为您将在 TeamAssignment "day1-spot1" 和 TeamAssignment "day2-spot3" 之间进行交换。

建模：高效建模子集选择

Modeling: Efficiently model subset selection

optimization

modeling

optaplanner

constraint-satisfaction