Pyrite | Level 9

Solver

Hello guys,

My data looks like this :

I have four flights, and for each flight i have a segment. Segment means where i have a passengers. For example, for flight number 2, i have passengers in two segments, NYC-AMS and NYC-LON, i.e some passengers fly from NYC to AMS and others from NYC to LON.

Capacity means maximum number of seats in aircraft. In other words the number of passengers cannot be more than the number of seats.

For each station, AMS and LON, i have a total number of passengers.

My  goal is to divide the passengers between each segment. I want that the percent of passengers divided by capacity for each segment(NYC-AMS, NYC-LON) will be identical. For example, let's take NYC-AMS.

There are two segments NYC-AMS, 150 passengers, because both segments have the same capacity, each segment will have 75 passengers. 75/166=0.4518 percent. Percent we get is identical for all NYC-AMS. Of course the capacity can be different.

Another problem, that flight number two has another segment NYC-LON, i.e flight NYC-AMS-LON cannot be more than 166 seats. In other words, when you calculate passengers for segment NYC-AMS, you take into account also other segments. You cannot divide the number of passengers for each segment separately.

To summarize, this problem has three conditions :

1. for each flight the number of passengers no more than the capacity

2. the total number of passengers for each segment is equal to total number of passengers in station.

3. as i told early, percent of passengers divided by capacity have to be identical for each segment.

I will be very happy for your help to solve this task.

1 ACCEPTED SOLUTION

Accepted Solutions
SAS Super FREQ

Re: Solver

You cannot get exactly identical, but here is a way to minimize the error:

``````data stationData;
input station \$ demand;
datalines;
AMS 150
LON 220
;

data flightSegmentData;
input flight rotation \$11. segment \$ capacity;
datalines;
1 NYC-AMS     NYC-AMS 166
2 NYC-AMS-LON NYC-AMS 166
2 NYC-AMS-LON NYC-LON 166
3 NYC-LON     NYC-LON 175
4 NYC-LON     NYC-LON 175
;

proc optmodel;
set <str> STATIONS;
num demand {STATIONS};
read data stationData into STATIONS=[station] demand;

set <num,str> FLIGHTS_SEGMENTS;
num capacity {FLIGHTS_SEGMENTS};
read data flightSegmentData into FLIGHTS_SEGMENTS=[flight segment] capacity;

set SEGMENTS = setof {<f,s> in FLIGHTS_SEGMENTS} s;

var NumPassengers {<f,s> in FLIGHTS_SEGMENTS} >= 0 <= capacity[f,s] integer;

var Ratio {SEGMENTS} >= 0;

var Surplus {FLIGHTS_SEGMENTS} >= 0;
var Slack {FLIGHTS_SEGMENTS} >= 0;

min Error = sum {<f,s> in FLIGHTS_SEGMENTS} (Surplus[f,s] + Slack[f,s]);

con SatisfyDemand {station in STATIONS}:
sum {<f,s> in FLIGHTS_SEGMENTS: scan(s,2,'-') = station} NumPassengers[f,s] = demand[station];

con EqualRatio {<f,s> in FLIGHTS_SEGMENTS}:
NumPassengers[f,s] - capacity[f,s] * Ratio[s] = Surplus[f,s] - Slack[f,s];

solve;
print Ratio NumPassengers Surplus Slack;
quit;``````
Solution Summary
Solver MILP
Algorithm Branch and Cut
Objective Function Error
Solution Status Optimal
Objective Value 1

Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 1.421085E-14
Integer Infeasibility 0

Best Bound 1
Nodes 1
Solutions Found 2
Iterations 59
Presolve Time 0.00
Solution Time 0.02

[1] Ratio
NYC-AMS 0.45181
NYC-LON 0.42771

[1] [2] NumPassengers Surplus Slack
1 NYC-AMS 75 0.0000 0.0000
2 NYC-AMS 75 0.0000 0.0000
2 NYC-LON 71 -0.0000 0.0000
3 NYC-LON 75 0.1506 0.0000
4 NYC-LON 74 0.0000 0.8494
SAS Super FREQ

Re: Solver

You cannot get exactly identical, but here is a way to minimize the error:

``````data stationData;
input station \$ demand;
datalines;
AMS 150
LON 220
;

data flightSegmentData;
input flight rotation \$11. segment \$ capacity;
datalines;
1 NYC-AMS     NYC-AMS 166
2 NYC-AMS-LON NYC-AMS 166
2 NYC-AMS-LON NYC-LON 166
3 NYC-LON     NYC-LON 175
4 NYC-LON     NYC-LON 175
;

proc optmodel;
set <str> STATIONS;
num demand {STATIONS};
read data stationData into STATIONS=[station] demand;

set <num,str> FLIGHTS_SEGMENTS;
num capacity {FLIGHTS_SEGMENTS};
read data flightSegmentData into FLIGHTS_SEGMENTS=[flight segment] capacity;

set SEGMENTS = setof {<f,s> in FLIGHTS_SEGMENTS} s;

var NumPassengers {<f,s> in FLIGHTS_SEGMENTS} >= 0 <= capacity[f,s] integer;

var Ratio {SEGMENTS} >= 0;

var Surplus {FLIGHTS_SEGMENTS} >= 0;
var Slack {FLIGHTS_SEGMENTS} >= 0;

min Error = sum {<f,s> in FLIGHTS_SEGMENTS} (Surplus[f,s] + Slack[f,s]);

con SatisfyDemand {station in STATIONS}:
sum {<f,s> in FLIGHTS_SEGMENTS: scan(s,2,'-') = station} NumPassengers[f,s] = demand[station];

con EqualRatio {<f,s> in FLIGHTS_SEGMENTS}:
NumPassengers[f,s] - capacity[f,s] * Ratio[s] = Surplus[f,s] - Slack[f,s];

solve;
print Ratio NumPassengers Surplus Slack;
quit;``````
Solution Summary
Solver MILP
Algorithm Branch and Cut
Objective Function Error
Solution Status Optimal
Objective Value 1

Relative Gap 0
Absolute Gap 0
Primal Infeasibility 0
Bound Infeasibility 1.421085E-14
Integer Infeasibility 0

Best Bound 1
Nodes 1
Solutions Found 2
Iterations 59
Presolve Time 0.00
Solution Time 0.02

[1] Ratio
NYC-AMS 0.45181
NYC-LON 0.42771

[1] [2] NumPassengers Surplus Slack
1 NYC-AMS 75 0.0000 0.0000
2 NYC-AMS 75 0.0000 0.0000
2 NYC-LON 71 -0.0000 0.0000
3 NYC-LON 75 0.1506 0.0000
4 NYC-LON 74 0.0000 0.8494
Discussion stats