July 21, 2023

Flight Optimization with MiniZinc and GPT-4

I tried expressing the following high-level problem in MiniZinc:

Given sets of planes and pilots and flights that happen 3x a day: find an assignment of planes and pilots to flights such that the workload is fair. As in, no pilot should be unduly burdened. No plane should be unduly stressed.

Assuming there are 5 planes and 5 pilots, here is a solution:

plane_assigned = [5, 1, 2, 3, 4, 1, 2, 1, 3, 2, 3, 1, 2, 1, 3, 2, 3, 1, 3, 1, 2]
pilot_assigned = [5, 3, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 3, 1, 2]

So Pilot 5 and Plane 5 will fly in the first slot of day 1. Pilot 3 and Plane 3 will fly in the first slot of day 2. Pilot 3 will fly Plane 1 in the second slot of day 3.

Here’s the code:

% define the number of flights, planes, pilots, and days
set of int: DAYS = 1..7;
set of int: FLIGHTS = 1..21; % 3 flights a day for 7 days
set of int: PLANES = 1..5;
set of int: PILOTS = 1..5;

% Each flight has a start and end time, now unique for each day
array[FLIGHTS] of int: flight_start = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21];
array[FLIGHTS] of int: flight_end = [2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22];

% define decision variables
% which plane is assigned to each flight
array[FLIGHTS] of var PLANES: plane_assigned;
% which pilot is assigned to each flight
array[FLIGHTS] of var PILOTS: pilot_assigned;
% binary variable that will be 1 if a pilot is used, 0 otherwise
array[PILOTS] of var 0..1: pilot_used;
% binary variable that will be 1 if a plane is used, 0 otherwise
array[PLANES] of var 0..1: plane_used;

% Constraint: No plane can be assigned to two flights at the same time
constraint forall(i in FLIGHTS, j in FLIGHTS where i != j) (
    (plane_assigned[i] = plane_assigned[j]) -> (flight_end[i] <= flight_start[j] \/ flight_end[j] <= flight_start[i])
);

% Constraint: No pilot can be assigned to two flights at the same time
constraint forall(i in FLIGHTS, j in FLIGHTS where i != j) (
    (pilot_assigned[i] = pilot_assigned[j]) -> (flight_end[i] <= flight_start[j] \/ flight_end[j] <= flight_start[i])
);

% Constraint: If a pilot is assigned to at least one flight, the corresponding pilot_used is 1
constraint forall(p in PILOTS)(
    pilot_used[p] = max([if pilot_assigned[f] = p then 1 else 0 endif | f in FLIGHTS])
);

% Constraint: If a plane is assigned to at least one flight, the corresponding plane_used is 1
constraint forall(p in PLANES)(
    plane_used[p] = max([if plane_assigned[f] = p then 1 else 0 endif | f in FLIGHTS])
);

% Constraint: Pilot 1 does not fly on Mondays (flights 1-3)
constraint forall(i in 1..3)(
    if ((i) in FLIGHTS /\ pilot_assigned[i] = 1) then false else true endif
);

% Constraint: Plane 2 does not fly on Tuesdays (flights 4-6)
constraint forall(i in 4..6)(
    if ((i) in FLIGHTS /\ plane_assigned[i] = 2) then false else true endif
);

% Constraint: No pilot flies more than one flight per day
constraint forall(d in DAYS, p in PILOTS)(
  sum([if (f >= 3*(d-1)+1 /\ f <= 3*d /\ pilot_assigned[f] = p) then 1 else 0 endif | f in FLIGHTS]) <= 1
);

% Constraint: No plane flies more than one flight per day
constraint forall(d in DAYS, p in PLANES)(
  sum([if (f >= 3*(d-1)+1 /\ f <= 3*d /\ plane_assigned[f] = p) then 1 else 0 endif | f in FLIGHTS]) <= 1
);

% define penalties
int: consecutive_penalty = 5;

% objective function
var int: obj = sum(pilot_used) + sum(plane_used)
               - consecutive_penalty * sum([if (plane_assigned[i] = plane_assigned[i+1]) then 1 else 0 endif | i in 1..20])
               - consecutive_penalty * sum([if (pilot_assigned[i] = pilot_assigned[i+1]) then 1 else 0 endif | i in 1..20]);

% solve the problem, maximizing the objective
solve maximize obj;

% print the results
output ["plane_assigned = ", show(plane_assigned), "\n",
        "pilot_assigned = ", show(pilot_assigned), "\n",
        "pilot_used = ", show(pilot_used), "\n",
        "plane_used = ", show(plane_used), "\n",
        "obj = ", show(obj)];

Like any good programmer in 2023, I had GPT-4 help me write this code. I found going this route saved a significant amount of time. I still needed to be able to understand the code and problem domain when guiding GPT-4:

GPT-4 went along with me when I wanted to do silly things:

var int: obj = sum(pilot_used) + sum(plane_used)
               - consecutive_penalty * sum([if (plane_assigned[i] = plane_assigned[i+1]) then 1 else 0 endif | i in 1..20])
               - consecutive_penalty * sum([if (pilot_assigned[i] = pilot_assigned[i+1]) then 1 else 0 endif | i in 1..20])
               + variance_penalty * sum([abs(plane_flights[p] - sum(plane_flights) div card(PLANES))^2 | p in PLANES])
               + variance_penalty * sum([abs(pilot_flights[p] - sum(pilot_flights) div card(PILOTS))^2 | p in PILOTS]);

I expressed the opposite of what I truly want. But I don’t think inverting it would have helped either because this model took too long to run.

Overall, the progression when guiding GPT-4 was:

• Fix mechanical errors

• Fix GPT-4 not correctly adhering to the semantics of MiniZinc

• Fix my own under-specification of the problem

• Very fast iteration adding constraints to the problem domain

This experience was pleasant. Of course it is scratching the surface of what’s possible in optimization. Under the hood, looks like MiniZinc focuses on linear solvers but has experimental support for non-linear.

Without getting too fancy, I am encouraged to try this MiniZinc + GPT-4 approach on a more real-world problem.