binary programming for 0/m instead of 0/1 variables
AnsweredHi, 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!
-
Official comment
-
Gurobi Staff
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
-
-
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 -
Post is closed for comments.
Comments
7 comments