different weights for matrix rows (ILP)
AnsweredHi all,
Not sure if this is the right forum, but I would be interested in how the ILP algorithm works and learn if (perhaps) the parameters could be tweaked to obtain a solution.
I am using Gurobi for an ILP to solve the so-called Set Covering Problem. In my case, to find the minimum number of rows that could cover a certain number of columns.
By using Gurobi for a good number of test problems, I learned that its solution varies from one run to another, even with the same matrix. It gives the same minima, but the rows signaled to construct the minima vary.
If at all possible, it would be really good to know, when different combinations of rows are equally good at covering the columns, if I could give more weight to those combinations containing a certain range of rows.
In my situation, the rows on the top of the matrix are more valuable, and the rows on the bottom of the matrix are less valuable. So there are layers of rows in descending order of their value, and now I wonder if that value could be specified in some sort of a weight to prefer solutions containing more "value" over other (equally good in term of the minima) solutions.
I hope to have explained this right, I am a not a mathematician but a mere sociologist.
-
Hi Adrian,
It sounds like you might be interested in multi-objective optimization, specifically a hierarchical approach, where the first objective is to minimize the number of rows used, then a second objective is to find the solution (amongst those that are optimal with respect to the first) that maximize the value of the rows selected (according to your metric for value).
I would start with our documentation on multiple objectives:
https://docs.gurobi.com/projects/optimizer/en/current/features/multiobjective.htmlthen take a look at our examples, relevant to the API of your choice:
https://docs.gurobi.com/projects/examples/en/current/examples/multiobj.html- Riley
0 -
Hello Riley,
Thank you for the prompt response, it sounds indeed like a multi-objective optimization. Although, if Gurobi returns with multiple solutions, I can select the best one myself.
So I started to experiment with, and read the indicated links. I am an R user, but could not exactly understand the example. It says it: "... want to cover three different sets ..." but in the example there seem to be four sets.
In addition, my own Set Covering Problem involves a modelsense of "min", whereas the example uses a "max".
My input matrix is supplied directly in the model$A part, and in the example it seems to be supplied in the multiobj specification.
I would be really grateful for a more targeted advice on a practical, minimal reproducible example. For instance, this is how I currently have my optimization in R:
model <- list(
A = x,
obj = rep(1, ncol(x)),
modelsense = "min",
rhs = rep(1, nrow(x)),
sense = rep(">=", nrow(x)),
vtype = "B",
lb = 0,
ub = 1
)(where x is a binary matrix with a variable number of rows an columns)I obtain my solution with:solution <- gurobi(
model,
params = list(
OutputFlag = 0,
LogToConsole = 0,
PoolSolutions = 100
)
)Is this likely to return multiple solutions? If yes, then the problem is solved, for I can look at them myself and give them different weights to select the best. If a multiobj part is mandatory to obtain the "best" solution, I could probably need more help.With my very best wishes,Adrian0 -
Hi Adrian,
It says it: "... want to cover three different sets ..." but in the example there seem to be four sets.
I think you've found a typo, thank you!
My input matrix is supplied directly in the model$A part, and in the example it seems to be supplied in the multiobj specification.
The constraint matrix is separate from the multiobj specification:
# Build constraint matrix model$A <- spMatrix(1, groundSetSize,
...The multiobj part only contains things that are relevant to the objective function(s)
Is this likely to return multiple solutions?
Probably, but not the solutions you need. Consider a minimization problem with two objectives f and g, of which there are solutions with the following objective values: (f,g} = {(1,2), (1,3), (2,3), (2,2), (2,1)}. You can say that the solution with objectives (1,2) is strictly better than (1,3), (2,3) and (2,2) because when comparing to another solution it always has one objective that is better, while the other one is no worse. Using the proper lingo we say that "(1,3), (2,3) and (2,2) are dominated by (1,2)". Likewise we can also say that (2,3), (2,2), (2,1) are dominated by (2,1). We don't care about dominated solutions as there is always a better choice. So when you run your optimization you want to get non-dominated solutions. But what if you run your optimization and you only get solutions with objectives corresponding to (1,2), (1,3), (2,3) and (2,2)? This is why you need the multi-objective framework, stumbling across non-dominated solutions otherwise will be pure luck (and possibly not likely). The following video might help color in some details: https://www.youtube.com/watch?v=ELLHqHk32II
I am not an R user, as it is not used very much by our customers, but if you were to ask ChatGPT for help with your R code then I could probably help you debug the output.
- Riley
0 -
Dear Riley,
Thank you for your patience, with a complete beginner like myself.
I tried many variations (after reading the documentation and the videos), but still unable to get how to solve this type of problem. I read, for instance, the example from:
https://docs.gurobi.com/projects/examples/en/current/examples/multiobj.htmlAlthough I am not an expert, I can read the code from C, Python and Javascript. None of them seem have the component model$A as in R, which seems to be some sort of a sparse matrix but different (and most likely with a different purpose) than my matrix that need to be solved.
In that example, the sets have different priorities / weights. In my case, it is the 20 numbers that need to have different weights, so that I could cover the 4 sets with higher priority for the numbers at the beginning of the sets (say, first ten), and lower priority for the numbers at the end of the sets (last ten).
I do understand the concept of a multi-objective function, it is just a matter of telling R how to do it. So far, I get in all sorts of errors such as:
Error: length(model$sense) != nrow(A)
Error: length(model$multiobj[[i]]$objn) != ncol(A)It feels like I am on the right track, it is just a bit frustrating for not getting it done (shouldn't be that difficult). ChatGPT also doesn't know what to do about different priorities for the different numbers in the sets...
0 -
Hi Adrian,
I can read the code from C, Python and Javascript. None of them seem have the component model$A as in R
Correct, they use a more natural modelling style than R (which is horrible in my opinion).
some sort of a sparse matrix but different (and most likely with a different purpose) than my matrix that need to be solved
R requires the coefficient matrix of the problem to be constructed (model$A). You may have another matrix in mind but ultimately it's the coefficient matrix that needs to be constructed. Consider the following constraints:
x + y + z <= 1
x + 2y >= 1
3x + z <= 2The corresponding coefficient matrix is
1 1 1
1 2 0
3 0 1Hopefully the diet example will help as your biggest obstacle does not seem to be related to multiple objectives.
Error: length(model$sense) != nrow(A) Error: length(model$multiobj[[i]]$objn) != ncol(A)
I think these are stemming from the fact you aren't building the coefficient matrix.
Do you have any experience with Julia? I know many users of R jumped ship to Julia and its optimization tooling is lightyears ahead of anything in R. We don't have a Julia API ourselves but maybe it's an option.
- Riley
0 -
Hi Riley,
Yes that is my understanding as well, but the matrix generated by the function spMatrix() is not a coefficient matrix, it is something else. What you describe really is a matrix with rows and columns, whereas the result of spMatrix has only one row and 20 columns, plus some "slots":
> sp
1 x 20 sparse Matrix of class "dgTMatrix"
[1,] 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1Alright, let me rephrase what I really want, starting from an example based on your website, with 4 sets. Suppose I have this coefficient matrix:
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1
0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 1 1 0 0
0 0 0 1 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0which corresponds to the following system of constraints:
a + b + c + d + e + f + g + h + i + j >= 1
f + g + h + i + j + o + p + q + r + s >= 1
d + e + g + h + m + n + p + q >= 1
d + e + f + j + k + l + o + p + q >= 1The objective is to find a "min"imal solution to this system of inequalities. There are about 50 different solutions, among which for instance:
a + p
or
d + f
or
j + q
Now, if I valued letters a through i, double as much the rest, then combination d + f is the most valuable solution, even through all of them are minimal. Solution a + p is less valuable but still more valuable than j + q.
I hope to have nailed the description of my problem, with anticipated thanks, yet again, with your kind assistance. My final product will be written in C, but for the moment I would very much like to create a test suite in R. I know it is not built for speed or performance, but it was not designed for this purpose. It is just super easy to teach students (especially from the social sciences) for whom C would be a big obstacle.
Best,
AdrianPS (edited) Gurobi consistently reports f + p as a minimal solution, but that is less valuable than d + f given the weights I give to letters a to i.
0 -
Hi Adrian,
What you describe really is a matrix with rows and columns, whereas the result of spMatrix has only one row and 20 columns, plus some "slots"
Yes the coefficient matrix in the multiobj example has 1 row and 20 columns. There are 20 variables and 1 constraint. It is not modeled the same as your example, perhaps that's where the confusion is arising.
It seems like your base model has no objective, and so multi-objective is not needed here - it will be enough just to have an objective.
If you create an objective where the more valuable variables have a greater objective coefficient then those solutions which favor those variables will be preferred. Do you think this will be enough or is there something still missing?
I would very much like to create a test suite in R. I know it is not built for speed or performance, but it was not designed for this purpose
The suggestion to use an alternative to R was not motivated by speed or performance but by readability and ease of use (and not as a general comment on the language, but specifically for building optimization models).
- Riley
0 -
If you create an objective where the more valuable variables have a greater objective coefficient then those solutions which favor those variables will be preferred. Do you think this will be enough or is there something still missing?
That would be perfect, if I could model this latest example to obtain the solution with the most valued variables, it would be perfect. This is what I am looking for.
What I would need to understand is how to write the R code for this to happen. Then I will most likely figure out how to do that in C.
With all my best,
Adrian0 -
Hi Adrian,
With reference to the diet model the objective is set here:
cost <- c(2.49, 2.89, 1.50, 1.89, 2.09, 1.99, 2.49, 0.89, 1.59)
...
model$obj <- c(rep(0, nCategories), cost)Once you define your vector of values and pass assign it to model$obj all that is left is to make sure Gurobi knows you're trying to maximize the result:
model$modelsense <- 'max'
- Riley
0 -
Hello Riley,
Let me again bring my deepest gratitude with your patience and your help.
I tried to make sense of both examples in Gurobi, but still to no avail. In the diet example, the cost (which is my value) is specified in the model$obj.
The problem is that Gurobi does not allow both "obj" and "multiobj" components in the model.
So, if my problem is a multi-objective optimization, I am still left puzzled as to how to specify the cost / value in the multiobj component.
I apologize for my lack of optimization knowledge, as previously mentioned I am a total beginner in this world. It would mean the world to me, if I could be provided with an R solution to my problem. I understand the R commands (having written many R packages), I just don't have enough optimization knowledge to understand what component belongs to which place in order to get what I am looking for.
This is what my problem definition looks like, at this point:
chart <- list(
c( 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ),
c( 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1 ),
c( 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0 ),
c( 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0 )
)
nVariables <- 19
nMinterms <- 4
values <- unlist(chart)
cost <- c(rep(2, 9), rep(1, 10))
model <- list()
model$sense <- rep('>=', nVariables)
model$rhs <- rep(1, nVariables)
model$varnames <- letters[1:nVariables]
model$modelsense <- 'min'
model$vtype <- "B"The thing that I still need to figure out is to how to specify:
- the component "A" matrix
- the "obj" or "multiobj" part, taking care of the cost / valuein order to find the most valuable minimal solution (so I assume a modelsense of "min") to this set covering problem.
Thank you again,
Adrian0 -
Hi Adrian,
The problem is that Gurobi does not allow both "obj" and "multiobj" components in the model.
An optimization problem either has 0, 1 or multiple objectives. For multiple objectives the multiobj component is used, for 1 objective the obj component is used. It would not make sense to have both.
See if the following works for you?
library(Matrix)
library(gurobi)
nVariables <- 19
nMinterms <- 4
value <- c(rep(2, 9), rep(1, 10))
chart <- list(
c( 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ),
c( 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1 ),
c( 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0 ),
c( 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0 )
)
model <- list()
model$sense <- rep('>=', nMinterms)
model$rhs <- rep(1, nMinterms)
model$varnames <- letters[1:nVariables]
model$modelsense <- 'min'
model$vtype <- rep("B", nVariables)
model$A <- Matrix(do.call(rbind, chart), sparse = TRUE)
model$multiobj <- list()
model$multiobj[[1]] <- list()
model$multiobj[[1]]$objn <- rep(1, nVariables)
model$multiobj[[1]]$priority <- 1
model$multiobj[[1]]$weight <- 1
model$multiobj[[2]] <- list()
model$multiobj[[2]]$objn <- -value
model$multiobj[[2]]$priority <- 0
model$multiobj[[2]]$weight <- 1
result <- gurobi(model)
for (e in 1:nVariables) {
cat(result$x[e])
}
rm(model, result)The first objective minimizes the number of columns selected. The second objective minimized the negative of the value which is equivalent to maximizing the value - we do this because we all objectives need the same sense, either min or max.
- Riley
0 -
Dear Riley,
You just made a very happy person. This is beautiful, exactly what I was looking for.
It did not occur to me that using the negative of the value was the culprit, I tried something similar using the positive values. But your explanation makes this clear now, thank you so much for your help.
I intend to use this to finish my simulations, then wrap everything into a paper and target a high impact IEEE engineering journal. I will certainly mention this support in the Acknowledgements section.
With all my best,
Adrian0 -
No problem, best of luck with the paper!
0
Please sign in to leave a comment.
Comments
13 comments