I am using solveLP in the linprog R package to solve a simple linear programming problem:
minimize -x1-x2
subject to 2*x1+x2+x3 =12
x1+2*x2 +x4 = 9
x1,x2,x3,x4 >=0
which has dual equivalent:
maximize 12*y1+9*y2
subject to 2*y1+y2 <= -1
y1+2*y2 <= -1
y1,y2 <=0
If I state the problem in the primal form I get the right results (5,2,0,0). But when stating the problem in the dual form, the first two constraints simply get ignored. I get the result (0,0) which clearly violates (2*y1+y2 <= -1 and y1+2*y2 <= -1), is there an extra setting or parameter I am missing ? Please have a look at the code underneath and let me know what you think:
require(linprog)
objVec <- c(-1,-1,0,0)
rhsConstr <- c(12, 9,0,0,0,0)
Amat <- rbind( c( 2, 1, 1, 0 ),
c( 1, 2, 0, 1 ),
c( 1, 0, 0, 0 ),
c( 0, 1, 0, 0 ),
c( 0, 0, 1, 0 ),
c( 0, 0, 0, 1 ))
res <- solveLP( objVec, rhsConstr, Amat, maximum=FALSE, const.dir = c("==","==",">=",">=",">=",">=") , lpSolve=TRUE)
res$solution
# dual problem - this is where the problem is
objVec <- c(12,9)
rhsConstr <- c(-1.0,-1.0,0,0)
Amat <- rbind( c( 2, 1),
c( 1, 2),
c( 1, 0),
c( 0, 1))
res <- solveLP( objVec, rhsConstr, Amat, maximum=TRUE, const.dir = rep("<=",length(rhsConstr)))
res$solution
In positive space the dual problem does give the right answer (1/3,1/3):
objVec <- c(12,9);
rhsConstr <- c(1,1,0,0);
Amat <- rbind( c( 2, 1), c( 1, 2), c( 1, 0), c( 0, 1));
res <- solveLP( objVec, rhsConstr, Amat, maximum=FALSE, const.dir = rep(">=",length(rhsConstr)) , lpSolve=TRUE);
res$solution;
As with many linear programming libraries, there are implicit non-negative constraints,
y>=0
: there are no feasible solutions (but I would expectres$status
to indicate this).solveLP
does not seem to allow negative solutions: you can either transform the problem to have only non-negative values (replacey1
withu1-v1
,y2
withu2-v2
) or use another package, that allows negative values.