CODEWITHSUNDEEP
rconstraintsmaximize
Andy
Andy

Reputation: 11

Maximization problem with constraints in R

I have a maximization problem under certain constraints. I have 3 different players on a string. They each have to ‘announce’ an amount (x) of (e) to consume. They all have the same utility function being u(x)=srqt(x) Now I want to maximize the sum of all u(x)=srqt(x) (player 1, player 2 and player 3). However, the choice of x for player 2 depends on the choice of player 1, and the choice of player 3 depends on the choice of player 2 (and thereby indirectly the choice of player 1). (As an example: player 1 has e=3 but chooses x=2, now player 2 has x=2 + the difference between x1 and e1, in this case 1)

Therefore the following constraints:

x1<=e1

x1+x2<=e1+e2

x1+x2+x3<=e1+e2+e3-x1-x2

and

x1+x2+x3=sum(e)

with all e: 0<=e<=10 (e being a randomly generated number between 0 and 10)

As an example:

e1=4, e2=1, e3=2, e4=1

In this case, to maximize sum(u(x)=sqrt(x)) player 1 will announce x1=2 giving sqrt(2)= 1.41 and therefore sends 2 units down the line.

Player 2 now faces: x2<=e1+e2-x1 => x2<=4+1-2 and will choose x2=2 to maximize sum(u(x)=sqrt(x)) and thus send 1 unit down the line

Player 3 will then face x3=e1+e2+e3-x1-x2 => x3<=4+1+2-2-2 and will choose x3=2 and send 1 unit down the line.

At this point player 4 does not have any chose but for the understanding: player 4 faces x4<=e1+e2+e3+e4-x1-x2-x3 => x4<=4+1+2+1-2-2-2 and will choose x4=2

The tricky part for me is that the following players choice depends on the former’s choice and I really seem to struggle with the coding for this. Any idea how to maximize u(x) giving this problem?

Upvotes: 1

Views: 236

Answers (1)

det
det

Reputation: 5232

You can try using DEoptim package for differential evolution.

Fitness function:

fn <- function(x){
  
  if(any(cumsum(x) > ps)) return(Inf)
  
  -(sum(sqrt(x)) + sqrt(e_sum - sum(x)))
}

if tests if your vector passes all conditions (except last one which is deterministic). Minus sign is because DEoptim minimizes. ps are partial sums of vector e except the last sum and e_sum is sum of vector e.

e <- c(4, 1, 2, 1)
ps <- cumsum(e[-length(e)])
e_sum <- sum(e)

x <- DEoptim::DEoptim(
  fn = fn,
  lower = rep(0, length(e) - 1),
  upper = ps 
)

res <- c(x$optim$bestmem, e_sum - sum(x$optim$bestmem))

It is not clear if you are searching for integer solution. In this case it ends up as integers.

> res
par1 par2 par3      
   2    2    2    2

EDIT

If you remove trace = FALSE you would see that algorithm didn't manage to find any feasible solution (best fitness value is infinity). You should try to create your own initial population which will contain some feasible solutions. For example you can try something like:

NP <- 200
initial_sol <- e[-length(e)]
initialPop <- rbind(
  initial_sol,
  Reduce(rbind, lapply(seq_len(NP-1), function(x) abs(initial_sol + rnorm(length(initial_sol)))))
)

and add initialpop= initialPop in DEoptim.control.

You can also create function to create all initial solutions feasible:

createFesibleIndividual <- function(ps){
  
  individual <- numeric(length(ps))
  cur_sum <- 0
  for(i in seq_along(individual)){
    
    new_ele <- runif(1, 0, ps[i] - cur_sum)
    cur_sum <- cur_sum + new_ele
    individual[[i]] <- new_ele
  }
  
  individual
}

initialPop <- Reduce(rbind, lapply(seq_len(NP), function(x) createFesibleIndividual(ps)))

Upvotes: 0

Related Questions