CPLEX Solver Solution

0
votes

I am currently stuck writing a CPLEX Solver.

The problem is basically a weighted bipartite matching with a twist.

Imagine we have 2 shelters and 2 homeless. Every homeless has a risk associated with a certain shelter. below is a matrix of this problem:

    S1   S2

P1  1    5

P2  10   5

so P1(person1) has risk 1 if it goes to S1(shelter1) and so on. For the above case, the optimal solution is to assign P1 to S1 and P2 to S2 to minimize the risk.

Now here is the twist. We have a [fairness equation (Jain's Fairness)][1]. This fairness equation is a quadratic function that basically calculates the fairness after all the assignment is done. This is the fairness index for the above solution.

Fairness = (1+5^2)/(2*(1^2)+(5^2) = 0.9 OR 90% fairness.

I want to write a solver that maximizes fairness. Gurobi couldn't solve my problem because it is a quadratic function. I moved on to CPLEX but I'm still unable to solve the problem. Here is my code:

int NbPeople = ...;
range People = 1..NbPeople;

int Shelters = ...;
range Shelter=1..Shelters;

int SheltersCapacity[Shelter] = ...;
int PersonReq[People]=...;
int GoodnessOfFit[People][Shelter] = ...;

dvar boolean A[p in People][s in Shelter];
dvar int gof;

//dexpr int Assignment=sum(p in People, s in Shelter) A[p][s] * GoodnessOfFit[p][s] ; 

maximize gof;

subject to {

forall(s in Shelter)
    Capacity:
       sum(p in People)
         A[p][s] * PersonReq[p]  <= SheltersCapacity[s];

forall (p in People)
    sum(s in Shelter) A[p][s] <= 1;

    sum (p in People,s in Shelter) A[p][s] == 3;

forall (p in People, s in Shelter)
   Fairness:
   (A[p][s] * GoodnessOfFit[p][s] ^ 2)
    /
    3 * A[p][s] * GoodnessOfFit[p][s] ^ 2 <= gof;

}```


[1]: https://en.wikipedia.org/wiki/Fairness_measure
1
cplexsolvergurobi
An alternative is to minimize the bandwidth (mentioned in the Wikipedia article: max-min fairness). That measure is easy to implement. - Erwin Kalvelagen

1 Answers

1
votes

You could try to use CP within CPLEX.

For instance:

using CP; // 

dvar int x in 10..100;
dvar int y in 1..10;

minimize x/(y*y+x);

subject to
{
x>=y+2;
}