FIT5216：离散优化问题建模课业1：动物捕捉
1概述
对于这项任务，您的任务是为给定的问题规范编写一个MiniZinc模型。•将您的作品提交到MiniZinc自动评分系统（使用中的提交按钮MiniZinc IDE）。
您必须在截止日期（2024年3月22日星期五晚上11:55）前提交，使用MiniZinc获得满分。您可以在截止日期前随时提交。逾期提交在没有特殊考虑的情况下，天将收到可用分数的10%的罚款。提交的资料在原始截止日期后7天内不接受。是一项个人课业。你的投稿必须完全是你自己的作品。我们
将使用相似性检测软件来检测任何共谋企图，处罚为相当苛刻。请注意，我们将把您保存的所有模型与其他模型进行比较。您可以不使用
大型语言模型，如ChatGPT，用于此任务的任何部分。如有疑问，请联系你的教学团队有任何问题！该评估的学习成果包括：
•使用基本建模和更高级建模相结合的方法对离散优化问题进行建模高级建模语言中的技术；
•识别并修复模型中的错误；
2问题陈述
你负责在森林地区建立一个动物监测项目。你需要建立一个摄像头陷阱的无线网络，以检测尽可能多的野生动物预算限制。输入数据采用MiniZinc数据格式：LOC=⟨可以放置陷阱和基地的位置集⟩；代 写FIT5216base=⟨您收集信息的基本位置⟩；n=⟨可使用的相机陷阱的数量⟩；野生动物=⟨每个位置的野生动物密度⟩；cost=在每个位置设置陷阱的成本⟩；d=从每个位置到另一个位置的距离矩阵；move=⟨动物移动距离⟩；=⟨无线链路距离⟩；mind=⟨两个陷阱之间的最小距离⟩；每个陷阱的操作成本；预算=⟨建立系统的预算⟩；
1.
请注意，基地位置总是LOC中的第一个。如果在某个位置设置陷阱的成本为如果是否定的，那么我们就不能在那里设下陷阱。
以下是一个示例数据集：LOC={碱基，A，B，C，D，E，F，G，H}；
base=base；
n=3；
野生=[0，10，7，3，2，8，6，4，9]；
成本=[0，6，4，5，-1，3，2，2，4]；
d=[|0，4，8，12，16，18，19，14，5
| 4, 0, 5, 9, 12, 17, 20, 7, 9
| 8, 5, 0, 5, 8, 12, 14, 15, 12
|12, 9, 5, 0, 3, 6, 8, 10, 11
|16, 12, 8, 3, 0, 9, 2, 6, 8
|18, 17, 12, 6, 9, 0, 5, 8, 15
|19, 20, 14, 8, 2, 5, 0, 8, 12
|14, 7, 15, 10, 6, 8, 8, 0, 9
| 5, 9, 12, 11, 8, 15, 12, 9, 0 |];
move=7；
链接=6；
心智=3；
opcost=8；
预算=26；
有9个地点，第一个地点是行动基地，那里不能有相机陷阱放置。有三个相机陷阱可供使用。每个地点都有野生动物密度和在那里设置陷阱的成本。请注意，由于D的成本为-1，我们无法设置陷阱那里距离矩阵是对称的，对角线上有0（到一个位置的距离自其本身总是0）。动物可以移动到距离7，而无线链路的范围为6。每对存水弯必须放置在相距至少3米的位置。每个存水弯的操作成本为8运营和建立该系统的总预算为26。
有两个决定要做
var LOC:x的数组[0.n]；%放置陷阱的位置，但x[0]=基础
var 0..n:s的数组[1.n]；%发送位置（仅用于C部分）
其目的是覆盖尽可能多的野生动物。如果某个位置有陷阱，则该位置被“覆盖”位置最多从此位置移动。A部分-使用所有陷阱创建一个模型animal.mzn，该模型以上面指定的格式获取数据，并准确地决定n个不同的相机陷阱位置。目前，我们忽略了预算限制。因此，目标是在x[1..n]中选择n个不同的位置。第0个位置必须设置为基准并且没有其他位置设置为基准。对于部分A和部分B，只需为所有i设置s[i]=0。请记住，您可以使用表达式d[u，v]来查找两个位置之间的距离，甚至如果位置u和v是决策。您需要决定覆盖哪些地点，以及2.您可能需要构建一个辅助决策变量来存储这些信息，或者对每个信息进行计数位置多少陷阱覆盖它。这是一个溶液样本。
x=[0:底座，1:H，2:C，3:A]；
s=[0，0，0]；
total_wild=43；
我们选择在位置{A，C，H}放置陷阱。此设置覆盖的野生动物总数是43，是位置{A、B、C、D、E、G、H}（在其中一个陷阱的7个范围内）的野生动物。请注意，没有两个存水弯的间距小于3，并且在具有负成本。请注意，仅仅回答A部分是无法获得很多分数的。有些问题将没有解决方案，而使用部分B，他们有解决方案。
B部分-可能使用更少的陷阱修改你的模型animal.mzn，将n视为最大可能数量的设备的边界。
我们将使用基准位置作为伪值。所以如果x[i]=基数，那么这表示没有陷阱放置。我们必须强制所有伪位置位于x数组的末尾（除了x[0]=始终为基数）。
现在你必须考虑到预算限制：即陷阱的总运营成本安装加上安装成本不得超过预算。请注意，您应该尽量只使用一种方式来表示每一组可能的安装的存水弯。这通常会使模型更有效率。这是B部分的溶液样本。
x=[0:基础，1:B，2:F，3:基础]；
s=[0，0，0]；
total_wild=36；
现在我们只在位置{B，F}放置陷阱。x数组中的最后一个条目表示我们没有放置第三个陷阱。覆盖的野生动物总数为36种，为{A、B、C、D、E、F}位置的野生动物（在其中一个陷阱的7个范围内）。这两个陷阱相距14个，远远超出了最小值距离使用的总预算为16的运营成本（运行两台摄像机）加上4+2=6的设置成本，在26的预算范围内。请注意，上一个解决方案的总成本{A，C，H}×8+6+5+4=39。注意，你不能只回答A和B部分就获得满分，但你可以获得好成绩。要获得满分，你需要正确完成C部分，但它的设计具有挑战性。
C部分-连接网络
相机陷阱必须将照片发送到基地，系统才能工作。要做到这一点，每个trap必须将其信息直接发送到基地，或者发送到另一个trap，然后在进一步的信息。为了表示这个网络，我们使用s[i]来表示位置（从0到n）我的相机在哪里第th个地方发送其信息。请注意，发送到位置0表示3.发送到基站（x[0]＝基站）。为了确保网络是一棵树，我们要求我发送信息的位置比我小。注意，我们需要位置发送和接收信息不过是一条链路。对于x[i]=base的伪位置i，我们应该将发送位置设置为0，但没有距离限制，因为我们实际上并没有设置相机。C部分的解决方案由下式给出
x=[0:基础，1:A，2:B，3:基础]；
s=[0，1，0]；
total_wild=24；
同样，我们只在{A，B}处使用两个相机陷阱。A处的陷阱将其信息发送到位置0，在距离4处；而B处的陷阱将其信息发送到距离5处的位置1，A（然后由A发送到基地）；因此满足了链路约束。请注意，前面的解决方案｛B，F｝不再有效，因为F与BASE相距19，与B相距14，因此没有发送链路
可用。覆盖的野生动物总数为24种，由｛A、B、C、G｝组成。预算限制是满足成本2×8+6+4=26。
3说明
编辑提供的mzn模型文件以解决上述问题。为您提供一些示例数据文件可以用来尝试您的模型。您的实现可以通过使用MiniZinc IDE中的Run+check图标。请注意，此分配的检查器将仅测试您的模型是否以所需的格式生成输出，它不会检查您的解决方案是正确的。服务器上的评分员会给你反馈你的提交的解决方案和模型。
4标记
标记是自动计算的。只有A部分，你可以获得几个满分实例，大多数将获得0。有了A部分和B部分，你可以在很多情况下获得满分，
否则最大值为0.75。自动分级器将实例分级为：0.25适用于任何解决方案，0.5适用于一个合理的解，0.75表示一个好的解，满分表示最优解。因为C部分添加了可以删除解的约束，而忽略C部分的B部分解可能会给出超最优答案（违反C约束），这些答案将获得最多0.75分。到得到最大的分数你的模型必须是有效的和正确的。提高效率的方法是
•确保只有一种（或至少尽可能少的）方式来表示相同解决方案（放置一组陷阱）。
•以最简单的形式表达您需要的约束条件提交的本地测试数据和模型测试分别得10分和10分，共计20分标志。对于模型测试，您将只能获得每次测试的分数反馈，而不能请参阅测试数据。集中精力让本地测试的数据首先工作，因为这更容易以进行调试