Mixed Integer Programming in R - Indicator functions

Question

I hope this message finds you well.

I am trying to solve an optimization problem formulated as a Mixed Integer Program with the lpSolveAPI R-package. However, there are indicator functions in the objective function and in some constraints. To be more specific, consider the following optimization problem:

min{        2.8 * x1 +        3.2 * x2 +        3.5 * x3 + 
     17.5 * delta(x1) + 2.3 * delta(x2) + 5.5 * delta(x3)  }

subject to:

  0.4 * x1 + 8.7 * x2 + 4.5 * x3 <=
          387 - 3 * delta(x1) - 1 * delta(x2) - 3 * delta(x3)

  x1 <= 93 * delta(x1)

  x2 <= 94 * delta(x2), 

  x3 <= 100 * delta(x3), and 

  x1, x2, and x3 are non-negative integers.

In this problem, for all i in {1, 2, 3}, delta(xi) = 1 if xi > 0, whereas delta(xi) = 0 otherwise.

The R-code I have so far is:

install.packages("lpSolveAPI")
library(lpSolveAPI)
a <- c(3, 1, 3)
b <- c(0.4, 8.7, 4.5)
q <- 387
M <- c(93, 94, 100)
A <- c(17.5, 2.3, 5.5)
h <- c(2.8, 3.2, 3.5)

Fn <- function(u1, u2, u3, u4){
lprec <- make.lp(0, 3)
lp.control(lprec, "min")
set.objfn(lprec, u1)
add.constraint(lprec, u2, "<=", u3)
set.bounds(lprec, lower = rep(0, 3), upper = u4)
set.type(lprec, columns = 1:3, type = "integer")
solve(lprec)
return(list(Soln = get.variables(lprec), MinObj = get.objective(lprec)))
}

TheTest <- Fn(u1 = h, u2 = b, u3 = q, u4 = M)

Please, I was wondering if someone could tell me how to put delta functions into this R-code to solve the aforementioned optimization problem.

Rodrigo.

It is an indicator function I(.) defined as: I(x) = 1 if x in A, whereas I(x) = 0 otherwise, where A = (0, +infinity). — Student1981
– Student1981, Commented Nov 3, 2016 at 15:23
The Dirac delta function (a.k.a. the Heaviside function) has support on (-Inf, Inf) but otherwise has the same definition. It's generally pretty easy in R to code such a construct. That doesn't look like R-code. It's missing assignments. Looks more like a pseudo-code specification. — IRTFM
– IRTFM, Commented Nov 3, 2016 at 16:26
After looking at the question ( for purposes of reformatting to SO standards) I'm puzzled by the joint requirement that x1, x2, x3 be non-negative integers and your use of an indication function that has a value of 1 at 0. — IRTFM
– IRTFM, Commented Nov 3, 2016 at 16:37

Erwin Kalvelagen · Accepted Answer · 2016-11-03 07:13:12Z

1

A constraint like x1 <= 93 * delta(x1) looks very strange to me. I think this is just x1 <= 93. For a MIP solver replace the function delta(x) by a binary variable d. Then add the constraint d <= x <= M*d where M is an upper bound on x. To be explicit, for your model we have:

min 2.8*x1 + 3.2*x2 + 3.5*x3 + 17.5*d1 + 2.3*d2 + 5.5*d3
0.4*x1 + 8.7*x2 + 4.5*x3 <= 387 - 3*d1 - d2 - 3*d3
d1 <= x1 <= 93*d1
d2 <= x2 <= 94*d2
d3 <= x3 <= 100*d3
x1 integer in [0,93]
x2 integer in [0,94]
x3 integer in [0,100]
d1,d2,d3 binary

This is now trivial to solve with any MIP solver. Note that a double inequality like d1 <= x1 <= 93*d1 can be written as two inequalities: d1<=x1 and x1<=93*d1.

edited Nov 3, 2016 at 7:13

answered Nov 3, 2016 at 6:57

Erwin Kalvelagen

16.9k3 gold badges17 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

Student1981 Over a year ago

Thanks for the suggestion, Mr. Kalvelagen. However, I realized that your suggestion includes the case in which di = 0 and xi > 0, with i in {1, 2, 3}.

Erwin Kalvelagen Over a year ago

No: you are mistaken

Student1981 Over a year ago

For example, the constraint d1 <= x1 takes place when d1 = 0 and x1 = 30 > 0.

Erwin Kalvelagen Over a year ago

We also have x1 <= 93 d1 which implies that if d1=0, x1 will be forced to be zero. Please read my answer more carefully.

Student1981 Over a year ago

Got it. Thanks a lot, Mr. Kalvelagen.

Collectives™ on Stack Overflow

Mixed Integer Programming in R - Indicator functions

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related