binary programming for 0/m instead of 0/1 variables
Answered
Hi, I'm using Gurobi to solve an optimization problem min(x'Qx-c'x), where x is a vector that I need to figure out. Each element in x should be either 0, or some real number m, for example x = [0,m,0,0,m,m]. This looks like a binary programming but I think Gurobi only accepts binary variable as either 0 or 1. Any idea how I can formulate my problem so as to make it solvable for Gurobi? Thanks!
-
You could introduce auxiliary binary variables \( z \in \{0,1\}^n \), then add the constraint \( x_i = m z_i\) for \( i = 1, \ldots, n \). This way, each \( x_i \) will be equal to \( 0 \) or \( m \).
0 -
Thanks for the comment! What if the value of m is also unknown? i.e., m is also an unknown variable that I need to find out with optimization?
0 -
You could define \( m \) to be a nonnegative variable. Then, those same constraints include the product of a binary variable and a continuous variable. Fortunately, there is an equivalent linear formulation of this product that Gurobi will automatically apply during presolve. To help Gurobi out, be sure to define a strong upper bound on the new \( m \) variable.
0 -
I think I conceptually got it but find it hard to write codes for introducing new auxiliary variables. So now the problem becomes min(x'Qx-c'x), s.t. x=mz, z = 0 or 1, 0=<m<=2 (2 for instance), right? Does it mean that x, z, m are all variables to solve now? If so, should the Q and c in my objective also be changed?
Could you please show an example code of how to introduce such "auxiliary variables" in R?
0 -
So now the problem becomes min(x'Qx-c'x), s.t. x=mz, z = 0 or 1, 0=<m<=2 (2 for instance), right? Does it mean that x, z, m are all variables to solve now? If so, should the Q and c in my objective also be changed?
Yes, that problem statement is correct, and we are indeed optimizing over \(x\), \(z\), and \(u\) now. Though to be a bit more explicit with the dimensions of the variables, I would write the problem as follows (renaming \( m \) to \( u \), since using \( m \) as a variable can be confusing):
$$\begin{alignat*}{2} \min_{x,z,u}\ && x^\top &Q x - c^\top x && \\ \textrm{s.t.}\ && x_i &= u z_i && i = 1, \ldots, n \\ && z &\in \{0, 1\}^n \quad && \\ && u &\in [0,2]. &&\end{alignat*}$$
Your objective can stay exactly the same; the purpose of the additional variables and constraints is to ensure each \( x_i \) is equal to either \( 0 \) or \( u \).
Could you please show an example code of how to introduce such "auxiliary variables" in R?
Below is an example that minimizes \( \sum_{i = 1}^n (n-i+1) x_i^2 - \sum_{i = 1}^n i x_i \). Introducing additional variables in R requires increasing the dimension of your matrices/vectors to account for the increased number of model variables/columns. You can read more about the different named components featured below in Gurobi's R documentation. The qp.R and qcp.R examples are also useful references for quadratic problems like this.
library(gurobi)
# total number of variables is 2n+1
n <- 10
model <- list()
model$A <- matrix(c(rep(0,2*n), 1), nrow=1, byrow=T)
model$rhs <- c(2.0) # upper bound on u
model$sense <- c('<')
model$obj <- c(-(1:n), rep(0, n+1))
model$Q <- spMatrix(2*n+1, 2*n+1, 1:n, 1:n, n:1)
model$vtype <- c(rep('C', n), rep('B', n), 'C')
model$varnames <- c(sprintf('x[%s]', 1:n), sprintf('z[%s]', 1:n), 'u')
qcs = list()
for (i in 1:n) {
qcs[[i]] <- list()
qcs[[i]]$Qc <- spMatrix(2*n+1, 2*n+1, c(n+i), c(2*n+1), c(-1.0))
qcs[[i]]$rhs <- 0
qcs[[i]]$q <- c(rep(0, i-1), 1, rep(0, 2*n+1-i))
qcs[[i]]$sense <- '='
qcs[[i]]$name <- sprintf('set_x[%s]',i)
}
model$quadcon <- qcs
result <- gurobi(model)
print(result$objval)
print(result$x)
# Write an LP file for visual inspection
gurobi_write(model, 'model.lp')0 -
This is very helpful. Thanks!!
0
Please sign in to leave a comment.
Comments
6 comments