Derivative-free optimziation with integer solutions

Question

Here is an example where the Nelder-Mead derivative-free optimziation algorithm is used. The problem is that I want a solution for integer-valued parameters. Does anybody know a way to do that in R?

library(dfoptim)

fn <- function(x) {
f1 <- x[1] + 6*x[2]
f2 <- 3*(10-x[1]) + 5*(10-x[2])
max(f1, f2)
}

par0 <- c(1, 1) 
nmkb(par0, fn, lower = 0, upper = 10)

possible duplicate of [Non Linear Integer Programming](http://stackoverflow.com/questions/3234935/non-linear-integer-programming) — Thilo, Dec 10 '14 at 19:53
You have a piecewise linear objective. With little work, it can be formulated as a MILP (Mixed-Integer Linear Programming) and solved with a branch-and-bound solver. — flodel, Dec 10 '14 at 19:59

score 1 · Accepted Answer · answered Dec 11 '14 at 00:52

Following up on my comment, your problem can be rewritten as as Mixed-Integer Linear Programming:

Minimize z               (A)
Subject to
  z >= x + 6y            (B)
  z >= 80 - 3x - 5y      (C)
  x >= 0                 (D)
  x <= 10                (E)
  y >= 0                 (F)
  y <= 10                (G)
  x, y are integer       (H)

MILP are solved using a branch-and-bound algorithm that should be faster than a non-linear solver. One such free solver is lpSolve:

library(lpSolve)
res <- lp(direction = "min",
          objective.in = c(1, 0, 0),       # (A) (weights for {z, x, y})
          const.mat = rbind(c(1, -1, -6),  # (B)
                            c(1, +3, +5),  # (C)
                            c(0,  1,  0),  # (D)
                            c(0,  1,  0),  # (E)
                            c(0,  0,  1),  # (F)
                            c(0,  0,  1)), # (G)
          const.dir = c(">=", ">=", ">=", "<=", ">=", "<="),  # (B through G)
          const.rhs = c(  0,   80,    0,   10,    0,   10),   # (B through G)
          int.vec   = c(2, 3))             # (H)

res$solution    # optimal values for z, x, y respectively
# [1] 33  9  4

I hope this helps. If not, maybe some will find it interesting nonetheless.

Derivative-free optimziation with integer solutions

1 Answers1