CODEWITHSUNDEEP
rlinear-programminglpsolveconvex-optimization
Yue Y
Yue Y

Reputation: 593

lpSolve package seems to give strange results

I am using the R "lpSolve" package downloaded from Cran link and it seems to give strange answers. I wanted to make sure that it is not me messing up things (which is likely the case).

For example, the problem I am trying to solve is 

maximize -3x-2y
s.t       5x -y <=  1
         -2x-2y <= -1
         -3x-2y <=  0

The settings I have in R:

> obj
   -3 -2
> cond
    5   -1
   -2   -2
   -3   -2
> dir
   "<=" "<=" "<="
> rhs
   1 -1  0

With these applied to the lp function in lp.solve

> lp(direction="max", objective.in=obj, const.mat=cond, const.dir=dir, const.rhs=rhs)$objval

This returns -1, however, I know the solution is 0 instead of -1.

I also tried set the objective to be "min" instead, and I get:

> lp(direction = "max", objective.in = obj, const.mat = cond, const.dir = dir, const.rhs = rhs)$objval
[1] -1
> lp(direction = "min", objective.in = obj, const.mat = cond, const.dir = dir, const.rhs = rhs)$objval
[1] 0

How is it possible that I get a bigger value when I try to minimize the objective? Does it have something to do with negative coefficient with x? I looked through the package manual and I didn't see any related requirements for the objective function.

Upvotes: 2

Views: 2755

Answers (1)

josliber
josliber

Reputation: 44340

You are right that (x, y) = (-1, 1.5) yields an objective value of 0, which from the constraints is clearly the maximum possible.

The thing that is holding you back from obtaining this is the following line in ?lp:

Note that every variable is assumed to be >= 0!

Under the assumption that every variable is non-negative, indeed -1 is the best you can do.

To solve your original problem, you could define non-negative decision variables x+ and x- to represent the positive and negative parts of x, and do the same for y. Here is the resulting optimization model:

mod <- lp(direction = "max",
          objective.in = c(obj, -obj),
          const.mat = cbind(cond, -cond),
          const.dir = dir,
          const.rhs = rhs)
mod$objval
# [1] 0
mod$solution[1:2] - mod$solution[3:4]
# [1] -1.0  1.5

In all cases, the effect of the transformation used here is removing the non-negativity requirement of the variables and keeping everything else the same.

Lastly, the reason your minimization looked like it was giving you an objective value of 0 is that it's actually unbounded and didn't set the objval value in its response:

lp(direction = "min", objective.in = obj, const.mat = cond, const.dir = dir, const.rhs = rhs)
# Error: status 3

Upvotes: 4

Related Questions