Resource Allocation Problem using ILP (GLOP)

• Download source code - 5.1 MB

Introduction

During development, there are many sub problems which are extreme, how do we solve those problems?

Solve them natively which is T&M exhaustive or try some alternative approach.

This article will touch upon ILP (Mathematical Modeling) with existing solver. It's useful in the sense that you can solve various NP-HARD problem in the following areas using solvers.

• Approximate Computing
• Configuration
• Cryptography
• Data mining
• Decision support
• Phylogenetics
• Planning
• Process monitoring and control
• Rosters or schedules
• Routing/vehicle routing
• Scheduling
• Selection
• Tutoring systems

Motivation

This problem is similar to the problem I have encountered in a coding competition. For some reasons unknown to me, the solution is not accepted. I want to pen down my solution and find a better solution.

Problem Statement

A travel agency serves X customers and has Y possible airline routes for destination, each customer requests multiple bookings for multiple destinations.

Following are fields of a Flight.

• FlightId: 1,2,3,4
• FlightOrigin : Pune
• FlightDestination: Sweden
• FlightClass: Either A or A+ ( Planes are rated based on luxury, build type etc)
• Recommended: Either yes or no (This is based on annual feedback from customers)
• FlightDuration: 1,2,3,4,5,6,7 hrs
• FlightDepartureDate: 1 Jan 2017
• FlightDirect: Y or N

Following are fields of request from customers.

• RequestId: Request id e.g "ACQ110"
• CustomerKey: Unique Identifer of customer. e.g "100080I"
• CustomerName: Name of customer e.g "Facebook"
• IsKeyCustomer: "Y" or "N"
• IsKeyRequest: How much important, request is for customer,"Y" mean this request has higher preference and vice versa
• RequestOrigin: Pune
• RequestDestination: Germany
• FlyDate: 2 Jan 2017
• FlightTime: 4 hrs

Expectation

The quality of the solution is a measure of the following:

1. Successful match of request
2. Quality of match
3. Constraint meet

The following describes the exact calculation for the quality score of the solution:

1. For each qualified match proposed in the system, 1 point will be awarded as a starting value. The qualifying criteria for a match is matching of the Request origin and destination to Flight origin destination on the requested date.
2. The actual quality of the match will be reflected in the following additions and subtractions from the value assigned to the match:
   • Add 0.3 points if flight is recommended.
   • Add 0.2 points if FlightClass is A+ or 0.1 if FlightClass is A.
   • Add 0.2 if FlightDirect is 'Y'
   • For every additional hour that the matched flight has over FlightTime of request subtract 0.05 points.
3. The maximum allowable points awarded to a match will depend on the CUSTOMER TYPE and CUSTOMER REQUEST type as follows:

   	IsKeyRequest(Y)	IsKeyRequest(N)
   IsKeyCustomer (Y)	1.7	1.3
   IsKeyCustomer(N)	1.5	1.0

4. In order to make sure that no one Customer gets all best Flights, the overall average matching score for each Customer cannot exceed 1.5 points. For example, for a Customer with 6 requests, the highest possible score will be 1.7*6 =10.2 points. However, the maximum allowable average score of a single Customer is 1.5 points. Therefore, the total allowable score for the 6 requests in this case would be 9 points.
5. The score for the solution is the summation of the scores for all matches for all customers, calculated as defined above.

Find a solution which maximizes the cost (summation of scores) and gives results within a time span of 30 secs for a result set of 2000(Flights)*2000(Request).

Solution

For every request, find all matching flights and calculate score, e.g.

The example below is a request from a customer.

<RequestId>XD1</RequestId>
<CustomerKey>10333I</CustomerKey>
 <CustomerName>Yahoo</CustomerName>
 <IsKeyCustomer>Y</IsKeyCustomer>
 <IsKeyRequest>N</IsKeyRequest>
 <RequestDestination>Germany</RequestDestination>
 <RequestOrigin>New Delhi</RequestOrigin>
 <FlyDate>2/10/2017<FlyDate>
 <FlightTime>4</FlightTime>

The examples below are two samples of Flight.

 <FlightId>A21</FlightId>
 <FlightDestination>Germany</FlightDestination>
  <FlightOrigin>New Delhi</FlightOrigin> 
 <FlightClass>A</FlightClass>
 <Recommended>N</Recommended>
 <FlightDuration>4</FlightDuration>
 <FlightDepartureDate >2/10/2017</FlightDepartureDate >
 <FlightDirect>Y<FlightDirect>
***********************************
 <FlightId>B21</FlightId>
 <FlightDestination>Germany</FlightDestination>
  <FlightOrigin>New Delhi</FlightOrigin> 
 <FlightClass>A+</FlightClass>
 <Recommended>Y</Recommended>
 <FlightDuration>5</FlightDuration>
 <FlightDepartureDate >2/10/2017</FlightDepartureDate >
 <FlightDirect>N<FlightDirect>

A21Score(1.3) = Origin-Destination match and on same date(1) + flight class is A(.1) + Recommended(0) + Directflight(.2) - (FlightDuration(4) - FlightTime(4))*0.05

B21Score(1.45) =Origin-Destination match and on same date(1) + flight class is A+(.2) + Recommended(.3) + Directflight(0) - (FlightDuration(5) - FlightTime(4))*0.05

Request XD1 is from a key Customer but request is not key, the maximum score that can be considered for request is 1.3, flight B21 can't be considered for this request. Since 1.3 < 1.45.

The above illustration shows all flights (F1-F9) and Request (R2-R8) along with scores, if score is not present then it's assumed not valid. Calculating score and finding match is an easy task and can be calculated in less than 2 secs using multithreading.

The real problem comes while satisfying d constraint, for this, I have used GLOP where the problem has to be modeled using ILP.

Using the Code

Create three dimensional arrays, for every request and flight find suitable match and calculate score considering constraints (a,b,c), the code for calculating score is multithreaded and is plain simple (code attached).

Matrix = new float[2, this.RequestCount, this.FlightCount]; 
int SkillMatch = 0; 
Matrix[SkillMatch, i, j] has value 1 -> Flight at index j can be booked for request at i.
Matrix[SkillMatch, i, j] has value 0 -> Flight at index j can't be booked for request at i.
int sum = 1; Matrix[sum, i, j] has score if flight at index j can be booked for request at i.

In order to meet constraint d, the problem has to be modeled using ILP and solved using Google linear optimization.

The following code creates a solver.

Solver solver = Solver.CreateSolver("IntegerProgramming", "GLOP_LINEAR_PROGRAMMING");

Next, define array x of variables where each variable value is between 0 and 1.

The length of array is count of all possible matches, at this step, we exclude all non matches, thus reducing the number of variables and improve the speed of solver.

int rows = agency.RequestCount;
int cols = agency.FlightCount;

var countVariable =   ( from i in Enumerable.Range(0, agency.Matrix.GetLength(1))
                               from j in Enumerable.Range(0, agency.Matrix.GetLength(2))
                               where agency.Matrix[SkillMatch,i,j] == 1
                               select agency.Matrix[SkillMatch, i, j] ).Count();

Variable[] x = solver.MakeIntVarArray(countVariable, 0, 1, "Matrix");

The following code creates a two dimensional map variableIndex, for every possible match, iterate from left to right through each row, increment and assign value in map where match is found.

Every i,j pair is represented by a number.

int[,]  variableIndex = new int[rows,cols];
int indexCounter = 0;

  for(int i = 0;i < rows; i++)
      {
          for(int j = 0; j< cols ; j++)
          {
              variableIndex[i,j] = -1;

              if(agency.Matrix[SkillMatch,i,j] == 1)
              {
                  variableIndex[i,j] = indexCounter;
                  indexCounter ++;
              }
              else
              {
                  variableIndex[i, j] = -1;
              }
          }
      }

Next, define a constraint on variables "every request must be matched with exactly one flight".

Sum Xij for all i where j-> 1 to FlightCount.

for (int i = 0; i < rows; i++)
       {
           solver.Add((from j in Enumerable.Range(0, cols)
                       where agency.Matrix[SkillMatch, i, j] == 1
                       select x[variableIndex[i,j]]).ToArray().Sum() <= 1);
       }

Next, define a constraint on variables "every flight must be matched with exactly one request".

Sum Xij for all j where i-> 1 to RequestCount.

for (int j = 0; j < cols; j++)
      {
          solver.Add((from i in Enumerable.Range(0, rows)
                      where agency.Matrix[SkillMatch, i, j] == 1
                      select x[variableIndex[i, j]]).ToArray().Sum() <= 1);
      }

Next, define a constraint on variables "for where there is match then Xij <=1".

for (int i = 0; i < rows; i++)
       {
           for (int j = 0; j < cols; j++)
           {
               if (agency.Matrix[SkillMatch, i, j] == 1)
               {
                   solver.Add(x[variableIndex[i, j]] <= agency.Matrix[SkillMatch, i, j]);
               }
           }
       }

Next, define constraint d on variable, customerRequest holds a collection of all requests for every customer, the sum of scores of all requests from a customer will always be <= 1.5* count of request for a customer.

foreach (var customerKey in agency.CustomerRequests.Keys)
       {
           solver.Add((from i in agency.CustomerRequests[customerKey]
                       from j in Enumerable.Range(0, cols)
                       where agency.Matrix[SkillMatch, i, j] == 1
                       select agency.Matrix[sum, i, j] * x[variableIndex[i, j]]
                       ).ToArray().Sum() <= 1.5F * agency.CustomerRequests[customerKey].Count());
       }

The following code defines what to expect from solver, the code tells the solver to find values of variable such that:

(agency.Matrix[sum, i, j] * x[variableIndex[i, j]]) is maximized and constraints (a,b,c,d) are met.

solver.Maximize((
             from i in Enumerable.Range(0, agency.Matrix.GetLength(1))
             from j in Enumerable.Range(0, agency.Matrix.GetLength(2))
             where agency.Matrix[SkillMatch, i, j] == 1
             select (agency.Matrix[sum, i, j] * x[variableIndex[i, j]])).ToArray().Sum());

Let solver solve the problem and find a optimal solution, it will try to assign values either 0 or 1 to variables such that constraints are met and score is maximized.

int solution = solver.Solve();

if (solution == Solver.OPTIMAL)
{
    FoundOptimalSolution(solver, agency, x, variableIndex);
}

All index[(i,j) where value is set as 1 are assignment of request i to flight j.

x[variableIndex[i, j]].SolutionValue() == 1

On a set of 2000*2000, the above code gives results in less than 30 secs.

If you have any suggestions, or want to improve the current solution, or want to suggest a better solution, please write to me at atulloona4@gmail.com.

Thanks!