Click here to Skip to main content
13,863,239 members
Click here to Skip to main content
Add your own
alternative version

Tagged as

Stats

3.3K views
50 downloads
2 bookmarked
Posted 3 Apr 2017
Licenced CPOL

Resource Allocation Problem using ILP (GLOP)

, 3 Apr 2017
Rate this:
Please Sign up or sign in to vote.
ILP using Google linear optimizations

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.71.3
    IsKeyCustomer(N)1.51.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!

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

ATUL_LOONA
India India
"It's impossible," said pride. "It's risky," said experience . "It's pointless," said reason "Give it a try." whispered the heart


Another piece of work here are links.

1) http://monk.parseapp.com/index.htm

2) http://picassa.parseapp.com/index.htm

3) http://circles.parseapp.com/

4) https://play.google.com/store/apps/details?id=com.complex

5) https://www.facebook.com/pages/MagForce/1406500216306629

You may also be interested in...

Pro
Pro

Comments and Discussions

 
PraiseMy vote of 5! Pin
jediYL4-Apr-17 17:32
professionaljediYL4-Apr-17 17:32 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web06 | 2.8.190214.1 | Last Updated 3 Apr 2017
Article Copyright 2017 by ATUL_LOONA
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid