MIQCO in R Gurobi

[Patrik Waldmann]

Dear Gurobi users,

I want to perform Mixed Integer Quadratic Constrained Optimization (maximization) of a relatively large problem in R Gurobi. My problem is as follows:

Max: x^t*c

with constraints:

x^t*Q*x <= k

x_i = {0,1}

where c is a vector of length N, k is a constant, Q a quadratic dense matrix of size N x N, and x is the vector of intergers to be optimized. Note that N is on the order of 3000 to 4000. Is this model possible to fit in R Gurobi? Could someone help with coding since I'm very new to Gurobi.

Best,

Patrik Waldmann

Swedish University of Agricultural Sciences

[Sonja Mars]

Hi Patrik,

You might want to take a look at our R examples. You can find them in the Gurobi installation directory in the examples folder. Additionally, we have them on our website:
https://www.gurobi.com/documentation/6.5/examples/r_examples.html

For example, here you can find a simple MIP model:
https://www.gurobi.com/documentation/6.5/examples/mip_r.html
and here is a model with quadratic constraints:
https://www.gurobi.com/documentation/6.5/examples/qcp_r.html

Best regards,
Sonja


----
Dr. Sonja Mars
Gurobi Optimization - Technical Support

[Patrik Waldmann]

Hi,

I do understand that integer constraint is obtained with: model$vtype      <- 'B'

but the quadratic constraint example doesn't help very much.

Patrik

[Patrik Waldmann]

Here is a toy example that doesn't work:

> library(gurobi)
Loading required package: slam
> model<-list()
> model$modelsense <- "max"
> model$obj <- c(1,1,2)
> model$quadcon[[1]]$Qc <- matrix(c(1,2,3,2,1,0,1,0,1),nrow=3,ncol=3,byrow=T)
> model$quadcon[[1]]$rhs <- 1
> model$vtype  <- 'B'
> params  <- list(OutputFlag=0)
> result  <-gurobi(model,params)
Error: is(model$A, "matrix") || is(model$A, "sparseMatrix") || is(model$A,  .... is not TRUE

[Renan Garcia]

As indicated in https://www.gurobi.com/documentation/6.5/refman/solving_models_with_the_gu.html, the named components corresponding to the linear constraints (i.e., A, sense and rhs) are not optional. However, a workaround for your model, which has no linear constraints, is to add a single redundant constraint 0x = 0. In your case, you would add the following lines:

  model$A     <- matrix(c(0,0,0), nrow=1, byrow=T)

  model$rhs   <- c(0)

  model$sense <- c('=')

--

---
You received this message because you are subscribed to the Google Groups "Gurobi Optimization" group.
To unsubscribe from this group and stop receiving emails from it, send an email to gurobi+un...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Patrik Waldmann]

OK, thanks. Th following now works:

> library(gurobi)

> model<-list()
> model$modelsense <- "max"
> model$obj <- c(1,1,2)

> model$A <- matrix(c(0,0,0), nrow=1, byrow=T)
> model$rhs <- c(0)
> model$sense <- c('=')

> model$quadcon[[1]]$Qc <- matrix(c(1,2,3,2,1,0,1,0,1),nrow=3,ncol=3,byrow=T)
> model$quadcon[[1]]$rhs <- 1
> model$vtype  <- 'B'
> params  <- list(OutputFlag=0)
> result  <-gurobi(model,params)

> print('Solution:')
[1] "Solution:"
> print(result$objval)
[1] 2
> print(result$x)
[1] 0 0 1

Will this be equivalent to the following (which is obtained by moving the quadratic constraint to the objective and adding the alpha parameter):

> model2 <- list()
> model2$modelsense <- "max"
> model2$Qcon <- matrix(c(1,2,3,2,1,0,1,0,1),nrow=3,ncol=3,byrow=T)
> model2$obj <- c(1,1,2)
> model2$objcon <- -1
> model2$A <- matrix(c(1,1,1),nrow=1,ncol=3,byrow=T)
> model2$rhs  <- c(1)
> model2$sense  <-  c('<=')
> model2$vtype  <- 'B'
> params2  <- list(OutputFlag=0)
> result2  <-gurobi(model2,params2)
> print('Solution:')
[1] "Solution:"
> print(result2$objval)
[1] 2
> print(result2$x)
[1] 0 0 1

[Renan Garcia]

In general, z1 = max { obj' x : x' Qc x <= 1, x binary } is not equivalent to z2 = max { obj' x + x' Qc x - 1 : 1'x <= 1, x binary }. For example, let

  obj <- c(1,1,1)

and

  Qc <- matrix(c(1,0,0,0,0.5,0,0,0,0.5),nrow=3,byrow=T)

Then, z1 = 2 and z2 = 1.

[Patrik Waldmann]

OK, thanks again. Last question, where can I find details about the algorithms behind z1 = max { obj' x : x' Qc x< = 1, x binary }?

[Renan Garcia]

See https://www.gurobi.com/resources/getting-started/lp-basics and https://www.gurobi.com/resources/getting-started/mip-basics