-1

这就是问题

因此，鉴于此，如果我想制定一个 ILP 模型来确定成本最低的路线，以防有以下附加限制：

- 如果使用 arc (1,4)，则也必须使用 arc (4,6)；-另一方面，如果不使用弧（1,4），则路线必须通过节点9。

如何在 ILP 模型中实现这两个新约束？

我想出了如何通过 AMPL 实现 ILP 模型，而不考虑这两个额外的约束，而是限制以这种方式最小化从底特律到查尔斯顿的路线：这些是这样做所必需的 2 个文件 .mod 和 .dat。文件 .mod 在这里

#model
set Nodes;
set Origins within (Nodes);
set Destinations within (Nodes);
set Link within (Nodes cross Nodes);

param Costs {Link};
param Balancies {Nodes};

var ConstrCost{Link} >=0;

minimize Total_Cost: sum{(i,j) in Link} Costs[i,j]*ConstrCost[i,j];

subject to StartingBalance {i in Origins}:-sum {(i,k) in Link} ConstrCost[i,k] == Balancies [i];
subject to FinalBalance {i in Destinations}:sum {(j,i) in Link} ConstrCost[j,i]-sum {(i,k) in Link} ConstrCost[i,k] == Balancies[i];

文件.dat 在这里。

data;
set Nodes := Detroit Due Tre Quattro Cinque Sei Sette Otto Nove Dieci Undici Charleston;
set Origins:= Detroit;
set Destinations:= Due Tre Quattro Cinque Sei Sette Otto Nove Dieci Undici Charleston;
set Link:=(Detroit,Due)
(Detroit,Tre)
(Detroit,Quattro)
(Due, Cinque)
(Due, Sei)
(Tre, Sei)
(Quattro, Sei)
(Quattro, Sette)
(Quattro, Nove)
(Cinque, Sei)
(Cinque, Otto)
(Cinque, Nove)
(Sei, Nove)
(Sette, Nove)
(Sette, Dieci)
(Otto, Undici)
(Nove, Undici)
(Nove, Charleston)
(Dieci, Undici)
(Dieci, Charleston)
(Undici, Charleston);

param Costs:=
Detroit,Due 1
Detroit,Tre 3
Detroit,Quattro 2
Due, Cinque 4
Due, Sei 3
Tre, Sei 2
Quattro, Sei 2
Quattro, Sette 3
Quattro, Nove 4 
Cinque, Sei 1
Cinque, Otto 3
Cinque, Nove 3
Sei, Nove 2
Sette, Nove 2
Sette, Dieci 3
Otto, Undici 2
Nove, Undici 1
Nove, Charleston 2
Dieci, Undici 3
Dieci, Charleston 5
Undici, Charleston 3;

param Balancies :=
Detroit -1
Due 0
Tre 0
Quattro 0
Cinque 0
Sei 0
Sette 0
Otto 0
Nove 0
Dieci 0
Undici 0
Charleston 1;

现在，给定这 2 个文件，我该如何实现这 2 个附加约束？

4

1 回答 1

0

因为你的变量是：ConstrCost

  1. 约束 1：

如果使用 arc (1,4)，这意味着 ConsrCost[1,4]>0，那么也必须使用 arc (4,6)，即 ConsrCost[4,6]>0

subject to {if ConstrCost[1,4]>0}:
   ConstrCost[4,6]>0;
  1. 约束2：如果没有使用arc(1,4)（即ConstrCost[1,4]=0），那么路由必须经过节点9，这意味着节点9必须至少使用一次作为起点或终点：
subject to {if ConstrCost[1,4]==0}:
   sum{i in Origins} ConstrCost[i,9]+sum{j in Destinations} ConstrCost[9,j]>0

考虑到您的模型无法识别 (1,4)，因此您应该替换为 Origins 和 destinations 名称...

于 2021-01-09T18:59:58.070 回答