Minizinc 约束公式

Question

我是 OR 和 Minizinc 的初学者，我正在尝试修改 Håkan Kjellerstrand 提供的示例，crew.mzn

我想添加一个限制条件，说明如果前一个未完成，飞行员将无法开始飞行。我创建了一个数组“FDP”，其中包含每个航班、开始时间戳、结束时间戳、持续时间。（休息被认为包括在开始和结束之间）。

我一直在写我的限制条件，并且有点迷失了将一个人完成的飞行与飞行特性联系起来。

能否请您确认我正在尝试做的事情是否可行。谢谢！

注意：约束 @ line72

% Pilots list

int: Tom     = 1;
int: David   = 2;
int: Jeremy  = 3;
int: Ron     = 4;
int: Joe     = 5;
int: Bill    = 6;
int: Fred    = 7;
int: Bob     = 8;
int: Mario   = 9;
int: Ed      = 10;

int: Carol   = 11;
int: Janet   = 12;
int: Tracy   = 13;
int: Marilyn = 14;
int: Carolyn = 15;
int: Cathy   = 16;
int: Inez    = 17;
int: Jean    = 18;
int: Heather = 19;
int: Juliet  = 20;

int: numPersons = 20; % number of persons
array[1..numPersons, 1..2] of int: attributes =  
array2d(1..numPersons, 1..2, [ %Capt or First Officer
  1,0,   % Tom     = 1
  1,0,  % David   = 2
  1,0,   % Jeremy  = 3
  1,0,   % Ron     = 4
  1,0,   % Joe     = 5
  1,0,  % Bill    = 6
  0,1,   % Fred    = 7
  0,1,   % Bob     = 8
  0,1,   % Mario   = 9
  0,1,   % Ed      = 10
  0,1,   % Carol   = 11
  0,1,   % Janet   = 12
  0,1,   % Tracy   = 13
  0,1,   % Marilyn = 14
  0,1,   % Carolyn = 15
  0,1,   % Cathy   = 16
  0,1,   % Inez    = 17
  0,1,   % Jean    = 18
  0,1,   % Heather = 19
  0,1   % Juliet  = 20
 ])
 ;

int: numFlights = 10;                           % number of flights
array[1..numFlights,1..3] of int: requiredCrew; % required crew per flight 
array[1..numFlights,1..3] of float: FDP; %flight characteristics
array[1..numFlights, 1..numPersons] of var 0..1: crew; 

% objective to minimize: standard deviation of flown hours between pilots
var 1..numPersons: z = sum(p in 1..numPersons) (bool2int(sum(f in 1..numFlights) (crew[f,p]) > 0));

% solve satisfy;
solve minimize z;

constraint
%  z = 19 ;  % for solve satisfy
% % %  /\
  forall(f in 1..numFlights) (
     % size of crew
     sum(i in 1..numPersons) (crew[f,i]) = requiredCrew[f, 1] /\ 
     % attribute and requirements
     forall(j in 1..2) (sum(i in 1..numPersons) (attributes[i,j]*crew[f,i]) >=  requiredCrew[f,j+1])) ;


% for each pilot doing a flight, end of flight i must not overlap beginning of flight i+1

 
%data

requiredCrew = 
  array2d(1..numFlights,1..3,   %Number of pilots required, Capt, FO
       [2,1,1, % Flight 1
        2,1,1, % Flight 2
        2,1,1, % ..
        2,1,1,
        3,2,1,
        2,1,1,
        2,1,1,
        3,1,2,
        2,1,1,
        2,1,1  % Flight 10
]);

FDP = 
  array2d(1..numFlights,1..3,  % flight start , flight end, flown hours
  [44531.58333,44531.70833,1.2,
   44533.16667,44533.5,2,
   44534.33333,44534.54167,1.1,
   44258.33333,44533.45833,1.5,
   44536.72917,44536.79167,2.3,
   44534.33333,44534.54167,3.1,
   44258.33333,44533.45833,0.2,
   44538.75,44538.95833,1.5,
   44539.625,44539.79167,2.2,
   44534.33333,44534.54167,1.8
 ]);

output [

       if i = 1 /\ j = 1 then
       "number of person: " ++ show(z) ++ "\n"
       else "" endif ++
       if j mod numPersons = 1 then show(i) ++ ": " else "" endif ++
       show(crew[i,j]) ++ if j mod numPersons = 0 then "\n" else " " endif 
       | i in 1..numFlights, j in 1..numPersons
] ++ ["\n"]
;

Answer 1

据我了解你的问题，要求是一个人（不仅仅是飞行员）不能被分配到任何重叠的航班。

如果这是正确的，那么下面添加的约束应该可以完成工作：

% ....

% for each pilot doing a flight, end of flight i must not overlap beginning of flight i+1
constraint
   forall(f1,f2 in 1..numFlights where f1 < f2  /\
           (
            ( FDP[f1,1] >= FDP[f2,1] /\ FDP[f1,2] <= FDP[f2,2] )
             \/
           ( FDP[f2,1] >= FDP[f1,1] /\ FDP[f2,2] <= FDP[f1,2] )
          ))
(
    not(exists(p in 1..numPersons) (
        crew[f1,p] = 1 /\ crew[f2,p] = 1
    ))
  );
% ...

它指出，如果两个航班的开始时间和结束时间重叠，则不能将一个人分配给两个航班。请注意，该模型不使用 flown hours 值，因为它们对我来说没有意义。

Chuffed 求解器输出此最优解：

% ....

----------
number of person: 6
1: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
2: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
3: 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
4: 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
5: 0 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
6: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
7: 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
8: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0
9: 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
10: 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0

----------
==========

你觉得这有意义吗？

Minizinc 约束公式

Minizinc Constraint Formulation

minizinc