CODEWITHSUNDEEP
rdataframelinear-programming
Morts81
Morts81

Reputation: 439

Finding All Possible Solutions with Linear Programming in R (Rglpk?)

I'm comfortable with finding optimal solutions using Rglpk in R, however, what I'm struggling to find a solution for is generating all possible solutions that meet a minimum criteria value.

For example, for the basic dataframe below, I can use Rglpk to find the optimal total result of 1 male and 1 female.

df<-data.frame(c("John","Sandy","James","Sharon"),c("M","F","M","F"),c(84,70,13,62))
colnames(df)<-c("Name","Sex","Result")

df
    Name Sex Result
1   John   M     84
2  Sandy   F     70
3  James   M     13
4 Sharon   F     62

library(Rglpk)
num <- length(df$Name)
obj<-df$Result
var.types<-rep("B",num)
matrix <- rbind(as.numeric(df$Sex == "M"),as.numeric(df$Sex == "F"))
direction <- c("==","==")
rhs<-c(1,1)
sol <- Rglpk_solve_LP(obj = obj, mat = matrix, dir = direction, rhs = rhs,types = var.types, max = TRUE)

df[sol$solution==1,]
   Name Sex Result
1  John   M     84
2 Sandy   F     70

However, if I want to find all possible solutions or 'combinations' of that dataframe where the combined result of 1 male and 1 female score exceeds 140, I can't work out how to generate this solution and subsequently format in the following fashion

     M      F Result
1 John  Sandy    154
2 John Sharon    146

Would appreciate any help that people can offer up.

Upvotes: 4

Views: 744

Answers (1)

Erwin Kalvelagen
Erwin Kalvelagen

Reputation: 16782

You can use the following algorithm for that:

  1. Solve MIP
  2. If infeasible: STOP
  3. Add a constraint to the model that forbids the current optimal solution.
  4. Go to step 1.

The constraint in step 3 can look like:

sum(i, a(i)*x(i)) - sum(i, (1-a(i))*x(i)) <= sum(i, a(i)) - 1

where a(i) is the current optimal solution (found in step 1). I.e. a(i) = x*(i). The a's are constants here. Note that the number of constraints grows by one in each cycle (so the model becomes larger and larger).

Here is the derivation of this cut: link.

It looks like you still need to add a constraint that makes sure the score exceeds 140.

Upvotes: 3

Related Questions