CODEWITHSUNDEEP
roptimizationmathematical-optimizationlinear-programming
Adrian
Adrian

Reputation: 9793

How to optimize over multiple objectives/variables given a set of constraints in R?

Given 2 unknown variables x = (x1, x2), I want to find the minimum values of x1, x2 such that a set of constraints Ax >= c holds. Here is a toy example where I optimized over x1 and x2, separately (I realized afterwards that this was not the correct approach!):

I coded this up in R:

library(lpSolveAPI)
c_vec <- c(0, 0, -0.42, 0.42, -0.81)
A_mat_col1 <- c(16, -15, -2, 3, 0.027)
A_mat_col2 <- c(15, 13, 16, 12, 13)
my.lp <- make.lp(nrow = 5, ncol = 2)
set.constr.type(my.lp, rep(">=", 5))
set.rhs(my.lp, c_vec)
set.column(my.lp, 1, A_mat_col1)
set.column(my.lp, 2, A_mat_col2)
set.bounds(my.lp, lower = rep(-Inf, 2), upper = rep(Inf, 2))
> my.lp
Model name: 
             C1     C2           
Minimize      0      0           
R1           16     15  >=      0
R2          -15     13  >=      0
R3           -2     16  >=  -0.42
R4            3     12  >=   0.42
R5        0.027     13  >=  -0.81
Kind        Std    Std           
Type       Real   Real           
Upper       Inf    Inf           
Lower      -Inf   -Inf

And then looped over minimizing x1 and x2 as follows:

lower <- vector()
for(i in 1:2){
  set.objfn(my.lp, make_basis(i, p = 2))
  lp.control(my.lp, sense = "min")
  # If return value is 0, then problem is solved successfully
  if(solve(my.lp) == 0){
    lower[i] <- get.objective(my.lp)
  # If return value is 3, then it's unbounded and I set lower bound to -Inf
  }else if(solve(my.lp) == 3){
    lower[i] <- -Inf
  }
}
> lower
[1]       -Inf 0.02876712

So the minimum value of x1 is -Inf, and the minimum value of x2 is 0.02876712. However, this does not satisfy the set of constraints. For example, the first constraint is 16x1 + 15x2 >= 0, since x1 is -Inf, then the result will be negative. So the first constraint is not satisfied.

So now I'm thinking that perhaps I should be solving the following problem instead:

Is there a way to optimize over multiple objectives in R?

Upvotes: 0

Views: 288

Answers (1)

G. Grothendieck
G. Grothendieck

Reputation: 269654

With multiple objectives the best one can do, in general, is to find the set of efficient points (also called Pareto optimal or nondominated points). These are points such that there is no other other point which has at least one objective value that is better while all other objectives are at least as good. Unfortunately in the problem at hand there are no efficient points because for any value of x1 we can satisfy all constraints by making x2 sufficiently large therefore given any x1 and x2 we can find x1' > x1 and x2' > x2 that also satisfy the constraints.

(By the way, note that lpSolveAPI assumes the constraint x >= 0.)

Upvotes: 0

Related Questions