GAMS中如何为整数线性规划模型添加x(i,j)≠x(j,i)约束？

问题根源 #

直接写x(j,i)会报错，核心原因是GAMS要求变量的索引顺序必须和其定义时的集合维度顺序完全一致。比如如果x是基于集合(i,i)定义的二维变量，不能随意调换索引顺序调用。另外你原方程的x(i,j)+x(j,i)-1 =l=0逻辑也不对——这个约束会强制两者之和≤1，无法保证x(i,j)≠x(j,i)（比如两者都为0也满足）。

正确解决步骤 #

假设i是一个单集合（比如节点、元素集合），x(i,i)是0-1二进制变量（这类对称不等约束大多针对0-1变量），按以下方式处理：

1. 定义无重复的索引子集
   先生成一个只包含i≠j且ord(i)<ord(j)的子集ij(i,i)，避免重复生成约束（比如同时处理(i,j)和(j,i)）：

   set i /1*5/;  // 示例集合
   set ij(i,i) "i≠j且i在集合中的顺序早于j";
   loop((i,i)$(ord(i) < ord(i)), ij(i,i) = yes;);
   

   这里ord(i)是集合元素的顺序编号，用来判断元素的先后关系。

2. 添加正确的不等约束
   对0-1变量来说，x(i,j)≠x(j,i)等价于x(i,j)+x(j,i)=1（一个取0则另一个取1，反之亦然）。基于子集ij定义方程：

   binary variable x(i,i);
   equation diff_con(ij);
   diff_con(ij).. x(i,j) + x(j,i) =e= 1;
   

3. 完整代码示例

   set i /1*3/;
   set ij(i,i);
   loop((i,i)$(ord(i) < ord(i)), ij(i,i) = yes;);
   
   binary variable x(i,i);
   variable obj;  // 目标变量，按需定义
   equation obj_def, diff_con(ij);
   
   obj_def.. obj =e= sum(ij, x(i,j));  // 示例目标函数
   diff_con(ij).. x(i,j) + x(j,i) =e= 1;
   
   model mymodel /all/;
   solve mymodel min obj using mip;
   

非0-1变量的特殊处理 #

如果x是一般整数变量，x(i,j)≠x(j,i)需要转化为绝对值约束：|x(i,j)-x(j,i)| ≥1。在GAMS中可以通过引入二进制变量y(ij)实现：

integer variable x(i,i);
binary variable y(ij);
equation diff_con1(ij), diff_con2(ij);

diff_con1(ij).. x(i,j) - x(j,i) ≥ 1 - 1000*(1 - y(ij));  // 大M法，1000为足够大的数
diff_con2(ij).. x(j,i) - x(i,j) ≥ 1 - 1000*y(ij);

这里用大M法来实现二选一的约束，确保两个变量的差至少为1，从而满足不等条件。

内容的提问来源于stack exchange，提问作者Matthew