lp: Linear and Integer Programming

Description

Interface to lp\_solve linear/integer programming system

Usage

lp (direction = "min", objective.in, const.mat, const.dir, const.rhs,
	transpose.constraints = TRUE, int.vec, presolve=0, compute.sens=0,
        binary.vec, all.int=FALSE, all.bin=FALSE, scale = 196, dense.const, 
        num.bin.solns=1, use.rw=FALSE)

Arguments

direction

Character string giving direction of optimization: "min" (default) or "max."

objective.in

Numeric vector of coefficients of objective function

const.mat

Matrix of numeric constraint coefficients, one row per constraint, one column per variable (unless transpose.constraints = FALSE; see below).

const.dir

Vector of character strings giving the direction of the constraint: each value should be one of "<," "<=," "=," "==," ">," or ">=". (In each pair the two values are identical.)

const.rhs

Vector of numeric values for the right-hand sides of the constraints.

transpose.constraints

By default each constraint occupies a row of const.mat, and that matrix needs to be transposed before being passed to the optimizing code. For very large constraint matrices it may be wiser to construct the constraints in a matrix column-by-column. In that case set transpose.constraints to FALSE.

int.vec

Numeric vector giving the indices of variables that are required to be integer. The length of this vector will therefore be the number of integer variables.

presolve

Numeric: presolve? Default 0 (no); any non-zero value means "yes." Currently ignored.

compute.sens

Numeric: compute sensitivity? Default 0 (no); any non-zero value means "yes."

binary.vec

Numeric vector like int.vec giving the indices of variables that are required to be binary.

all.int

Logical: should all variables be integer? Default: FALSE.

all.bin

Logical: should all variables be binary? Default: FALSE.

scale

Integer: value for lpSolve scaling. Details can be found in the lpSolve documentation. Set to 0 for no scaling. Default: 196

dense.const

Three column dense constraint array. This is ignored if const.mat is supplied. Otherwise the columns are constraint number, column number, and value; there should be one row for each non-zero entry in the constraint matrix.

num.bin.solns

Integer: if all.bin=TRUE, the user can request up to num.bin.solns optimal solutions to be returned.

use.rw

Logical: if TRUE and num.bin.solns > 1, write the lp out to a file and read it back in for each solution after the first. This is just to defeat a bug somewhere. Although the default is FALSE, we recommend you set this to TRUE if you need num.bin.solns > 1, until the bug is found.

Value

An lp object. See lp.object for details.

Details

This function calls the lp\_solve 5.5 solver. That system has many options not supported here. The current version is maintained at http://lpsolve.sourceforge.net/5.5

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

Examples

Run this code

# NOT RUN {
#
# Set up problem: maximize
#   x1 + 9 x2 +   x3 subject to
#   x1 + 2 x2 + 3 x3  <= 9
# 3 x1 + 2 x2 + 2 x3 <= 15
#
f.obj <- c(1, 9, 1)
f.con <- matrix (c(1, 2, 3, 3, 2, 2), nrow=2, byrow=TRUE)
f.dir <- c("<=", "<=")
f.rhs <- c(9, 15)
#
# Now run.
#
lp ("max", f.obj, f.con, f.dir, f.rhs)
# }
# NOT RUN {
Success: the objective function is 40.5
# }
# NOT RUN {
lp ("max", f.obj, f.con, f.dir, f.rhs)$solution
# }
# NOT RUN {
[1] 0.0 4.5 0.0
# }
# NOT RUN {
#
# The same problem using the dense constraint approach:
#
f.con.d <- matrix (c(rep (1:2,each=3), rep (1:3, 2), t(f.con)), ncol=3)
lp ("max", f.obj, , f.dir, f.rhs, dense.const=f.con.d)
# }
# NOT RUN {
Success: the objective function is 40.5
# }
# NOT RUN {
#
# Get sensitivities
#
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.from
# }
# NOT RUN {
[1] -1e+30  2e+00 -1e+30
# }
# NOT RUN {
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$sens.coef.to  
# }
# NOT RUN {
[1] 4.50e+00 1.00e+30 1.35e+01
# }
# NOT RUN {
#
# Right now the dual values for the constraints and the variables are
# combined, constraints coming first. So in this example...
#
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals     
# }
# NOT RUN {
[1]   4.5   0.0  -3.5   0.0 -10.5
# }
# NOT RUN {
#
# ...the duals of the constraints are 4.5 and 0, and of the variables,
# -3.5, 0.0, -10.5. Here are the lower and upper limits on these:
#
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.from
# }
# NOT RUN {
[1]  0e+00 -1e+30 -1e+30 -1e+30 -6e+00
# }
# NOT RUN {
lp ("max", f.obj, f.con, f.dir, f.rhs, compute.sens=TRUE)$duals.to  
# }
# NOT RUN {
[1] 1.5e+01 1.0e+30 3.0e+00 1.0e+30 3.0e+00
# }
# NOT RUN {
#
# Run again, this time requiring that all three variables be integer
#
lp ("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3)
# }
# NOT RUN {
Success: the objective function is 37
# }
# NOT RUN {
lp ("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3)$solution
# }
# NOT RUN {
[1] 1 4 0
# }
# NOT RUN {
#
# You can get sensitivities in the integer case, but they're harder to
# interpret.
#
lp ("max", f.obj, f.con, f.dir, f.rhs, int.vec=1:3, compute.sens=TRUE)$duals
# }
# NOT RUN {
[1] 1 0 0 7 0
# }
# NOT RUN {
#
# Here's an example in which we want more than one solution to a problem
# in which all variables are binary: the 8-queens problem, 
# with dense constraints.
#
chess.obj <- rep (1, 64)
q8 <- make.q8 ()
chess.dir <- rep (c("=", "<"), c(16, 26))
chess.rhs <- rep (1, 42)
lp ('max', chess.obj, , chess.dir, chess.rhs, dense.const = q8, 
    all.bin=TRUE, num.bin.solns=3)
# }