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.
-
-
Gurobi Staff
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 -
-
Dear Riley,
I have progressed a lot with my code, and now reached a new challenge that, despite my weeks long testing effort, the solution still remains stubbornly hidden. Below you can find my latest version of the corresponding C code, which (after applying the second objective of maximizing weights), results in the solution containing columns 4 and 7.
This code is used in a Boolean minimization algorithm applied to multiple outputs, and the most valuable solutions are those containing prime implicants (here, on the columns) that are shared by more than one output.In the data below, both combinations {4,7} and {4,8} have exactly the same value, but I have no idea which of those PIs (from column 7 or column 8) are shared between outputs until I solve each such matrix for each of the outputs individually. So it may be that column 8 is actually more valuable after comparing the solutions from all outputs, but I am unable to convince Gurobi to output more than one (equally optimal) solution.
I used:GRBsetintparam(env, "PoolSearchMode", 2)as well as:
GRBsetintparam(env, "PoolSolutions", 100)to no avail. Could you please indicate which further settings should I use to make Gurobi output multiple solutions?
Thank you in advance,
Adrian#include <stdio.h> #include <stdlib.h> #include <fcntl.h> #include "gurobi_c.h" int main(void) { int error = 0; GRBenv *env = NULL; error = GRBloadenv(&env, "multiobj_c.log"); if (error) goto QUIT; GRBmodel *model = NULL; int *ind = NULL; double *value = NULL; double *coeffs = NULL; double *solution = NULL; const int PIs = 19; // number of columns const int ON_minterms = 4; // number of rows /* --- vectorized constraint matrix (row-major) --- */ int xvec[ON_minterms * PIs] = { 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, 0, 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, 0 }; ind = malloc(PIs * sizeof(int)); value = malloc(PIs * sizeof(double)); coeffs = malloc(PIs * sizeof(double)); solution = malloc(PIs * sizeof(double)); if (!ind || !value || !coeffs || !solution) { error = 1; goto QUIT; } /* new model with PIs variables */ error = GRBnewmodel(env, &model, "setcover", PIs, NULL, NULL, NULL, NULL, NULL); if (error) goto QUIT; /* binary vars */ for (int j = 0; j < PIs; j++) { error = GRBsetcharattrelement(model, GRB_CHAR_ATTR_VTYPE, j, GRB_BINARY); if (error) goto QUIT; } /* covering constraints */ for (int i = 0; i < ON_minterms; i++) { int nz = 0; for (int j = 0; j < PIs; j++) { if (xvec[i * PIs + j] == 1) { // row i, col j ind[nz] = j; value[nz] = 1.0; nz++; } } error = GRBaddconstr(model, nz, ind, value, GRB_GREATER_EQUAL, 1.0, NULL); if (error) goto QUIT; } /* indices (all variables) */ for (int j = 0; j < PIs; j++) ind[j] = j; /* first objective: minimize sum x_j */ { for (int j = 0; j < PIs; j++) coeffs[j] = 1.0; error = GRBsetobjectiven( model, 0, 1, 1.0, 0.0, 0.0, "mincols", 0.0, PIs, ind, coeffs ); if (error) goto QUIT; } /* second objective: maximize weighted value */ { for (int j = 0; j < PIs; j++) coeffs[j] = (j < 9 ? -2.0 : -1.0); error = GRBsetobjectiven( model, 1, 0, 1.0, 0.0, 0.0, "maxvalue", 0.0, PIs, ind, coeffs ); if (error) goto QUIT; } /* optimize */ error = GRBoptimize(model); if (error) goto QUIT; /* extract solution */ error = GRBgetdblattrarray(model, GRB_DBL_ATTR_X, 0, PIs, solution); if (error) goto QUIT; printf("Optimal solution:\n"); for (int j = 0; j < PIs; j++) { if (solution[j] > 0.5) printf("x[%d] = 1\n", j+1); } QUIT: if (ind) free(ind); if (value) free(value); if (coeffs) free(coeffs); if (solution) free(solution); if (error) { printf("ERROR: %s\n", GRBgeterrormsg(env)); } if (model) GRBfreemodel(model); if (env) GRBfreeenv(env); return 0; }0 -
-
-
Hi Adrian,
You are setting the necessary parameters correctly, but there is one problem - PoolSearchMode values > 0 are unfortunately not compatible with multi-objective solves.
You could however implement the multi-objective solve yourself as a workaround:
i) solve the model to minimize first objective function f1(x), to obtain objective value objval1.
ii) add a constraint f1(x) ≤ objval1
iii) set objective to maximize second objective function f2(x), set PoolSearchMode=2, PoolSolutions=100, and solve
- Riley
0 -
-
Hi Riley,
This amounts to solving the problem twice, which is bad news for time consuming problems, but I guess there is nothing to do about it.
Alright, I tried to implement your procedure, but for some reason I get back the same solution twice:
Found 2 solutions in pool: Solution 1: 4 7 Solution 2: 4 7I would have expected {4,7} and {4,8} as perfectly equivalent solutions. Could it be that I am not retrieving them right, or is the very same solution stored twice in the pool?
error = GRBoptimize(model); if (error) goto QUIT; double objval; error = GRBgetdblattr(model, GRB_DBL_ATTR_OBJVAL, &objval); if (error) goto QUIT; printf("First objective value = %.0f\n", objval); /* Step 2: add constraint sum x_j <= objval */ { error = GRBaddconstr(model, PIs, ind, coeffs, GRB_LESS_EQUAL, objval, NULL); if (error) goto QUIT; } /* Step 3: maximize weighted value */ for (int j = 0; j < PIs; j++) coeffs[j] = (j < 9 ? -2.0 : -1.0); error = GRBsetobjectiven( model, 0, 1, 1.0, 0.0, 0.0, "maxvalue", 0.0, PIs, ind, coeffs ); if (error) goto QUIT; // enable solution pool error = GRBsetintparam(env, "PoolSearchMode", 2); if (error) goto QUIT; error = GRBsetintparam(env, "PoolSolutions", 100); if (error) goto QUIT; error = GRBoptimize(model); if (error) goto QUIT; int solcount; error = GRBgetintattr(model, GRB_INT_ATTR_SOLCOUNT, &solcount); if (error) goto QUIT; for (int k = 0; k < solcount; k++) { error = GRBsetintparam(env, "SolutionNumber", k); if (error) goto QUIT; error = GRBgetdblattrarray(model, GRB_DBL_ATTR_Xn, 0, PIs, solution); if (error) goto QUIT; printf("Solution %d:", k+1); for (int j = 0; j < PIs; j++) { if (solution[j] > 0.5) printf(" %d", j+1); } printf("\n"); }0 -
-
-
Hi Adrian,
This amounts to solving the problem twice
Sure, but so does using the existing approach. What Gurobi is doing when you solve a multi-objective model is essentially the approach I described. There may be some benefit provided by the initial presolve that is common to all objective solves, but this functionality is mostly for convenience.
The approach will work, here is the equivalent code in Python as a proof of concept:
import gurobipy as gp import numpy as np coeff = np.array([ [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, 0, 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, 0], ]) m = gp.Model() x = m.addMVar(19, obj=1, vtype="B") m.addConstr(coeff@x >= 1) m.optimize() m.addConstr(x.sum() <= 2) m.setObjective(np.array([2]*9+[1]*10)@x, gp.GRB.MAXIMIZE) m.params.PoolSearchMode=2 m.params.PoolSolutions=100 m.optimize() for i in range(m.SolCount): m.params.SolutionNumber = i print([e for e,v in enumerate(m.Xn) if v > 0.5])which gives the following solutions:
[3, 8] [4, 8] [5, 6] [3, 5] [3, 7] [4, 6] [4, 7] [5, 7] [4, 5] [3, 6] [6, 15] [4, 15] [4, 18] [0, 15] [1, 15] [2, 15] [6, 10] [8, 16] [2, 16] [3, 17] [5, 12] [3, 18] [4, 17] [5, 13] [5, 16] [3, 14] [4, 14] [0, 16] [1, 16] [5, 15] [6, 11] [3, 16] [3, 15] [7, 10] [7, 16] [7, 14] [4, 16] [7, 11] [7, 9] [6, 9] [6, 14] [6, 16] [7, 15] [8, 15] [9, 16] [9, 15]
It's not obvious to me where the issue lies, but poolsearch_c.c should help. I would double check you are using a line equivalent to
menv = GRBgetenv(model);from that example.- Riley
0 -
-
-
Hi Adrian,
You may not get all solutions because you use
GRBsetobjectiveninstead ofGRBsetobjectiveto set your objective function(s). The former automatically switches Gurobi to the multi-objective mode (even if you never define more than one objective function that holds at once).If you check your log file, you will also find the following warning after you try to change
PoolSearchModeto 2:Warning: PoolSearchMode != 0 is not supported for multi-objective optimization. Reset PoolSearchMode to zero.As the warning says, Gurobi does not support a
PoolSearchMode != 0if it is in multi-objective mode, so your change in the parameterPoolSearchModewas ignored.Just use the following code snippet for your first objective function
error = GRBsetobjective( model, GRB_MINIMIZE, 0.0, PIs, ind, coeffs, 0, NULL, NULL, NULL );and the next one for your second objective function
error = GRBsetobjective( model, GRB_MAXIMIZE, 0.0, PIs, ind, coeffs, 0, NULL, NULL, NULL );That changes your objective functions without entering multi-objective mode, and Gurobi will now search for all possible solutions.
Best regards,
Martin
----
Dr. Martin Bromberger - MIP Development Scholar
Gurobi GmbH
Sandstraße 104
40789 Monheim am Rhein
Email: martin.bromberger@gurobi.com (he, him, his)
-------------------------------------------------------------------------------
Sitz der Gesellschaft: Düsseldorf
Registergericht: Düsseldorf, HRB 99473
Geschäftsführer: Craig Albrecht und Duke Perrucci0 -
-
Thank you Riley, problem solved.
Apart from failing to usemenv = GRBgetenv(model), I was indeed still using the multi-objective API (GRBsetobjectiven) and that, as you pointed out, makes PoolSearchMode > 0 ineffective.Your Python code made that more obvious.
With my very best,
Adrian0 -
-
Hi Martin, hi Riley,
Just a quick follow-up feedback, having now a working code. The timing of a multi-objective function appears to be about half of the above two-step optimizations.
By setting an equal priority for the two objectives, as far as I understand, the overall model is a blended multi-objective where both are achieved at about the same time (still more time than a single first objective).But obtaining a solution pool through two separate optimizations effectively doubles the timing, compared to the blended multi-objective function. I was wondering how does the multi-objective function selects the best solution, if not out of a pool. Or perhaps there would (should?) be possible to tell the multi-objective function to store the candidate solutions it chooses from and return them along with the solution.
Best,
Adrian0 -
-
-
Hi Adrian,
In the blended case, the objectives are combined into a single linear objective, and Gurobi only has to optimize towards this one objective. Therefore, blended multi-objectives are typically much faster than hierarchical/priority-based multi-objectives, where Gurobi has to optimize towards one objective for every priority level.
Please be aware that blended and priority-based multi-objectives do not generally lead to the same optimal solutions, even if they do in your particular example. For instance, let's look at the following MIP:
Minimize multi-objectives OBJ0: x OBJ1: y Subject To y >= 2 - 2 x Bounds 0 <= x <= 2 0 <= y <= 2 Generals x y EndBlending the two objective functions (with equal weights) would produce the combined objective function: Minimize x + y. As a result, Gurobi would solve the single MIP:
Minimize x + y Subject To y >= 2 - 2 x Bounds 0 <= x <= 2 0 <= y <= 2 Generals x y EndAnd the only optimal solution would be x = 1, y = 0 with objective 1.
If we were to prioritize Minimize x before Minimize y, then Gurobi would first solve the MIP:
Minimize x Subject To y >= 2 - 2 x Bounds 0 <= x <= 2 0 <= y <= 2 Generals x y Endand determine that this MIP has optimal solution x = 0, y = 2 with objective 0. Then, Gurobi would add the constraint x <= 0 to preserve the optimality of the first objective and solve the MIP:
Minimize y Subject To y >= 2 - 2 x x <= 0 Bounds 0 <= x <= 2 0 <= y <= 2 Generals x y EndThe optimal solution of this MIP and therefore the overall multi-objective would be x = 0, y = 2 with objective 2.
As you can see, the two versions of handling multi-objectives can have vastly different results. The same could happen to your example if you changed the values in your second objective or the constraint matrix.
Under the right conditions, there are tricks to use a blended multi-objective to exhibit the same behavior as the priority-based multi-objective. For instance, if you know that
- the difference in objective values between two solutions is always >= D for the first objective and
- the objective values for the second objective lie in the interval [l,u]
then you can set the weight of the first objective to a value strictly larger than (u-l)/D and the weight of the second objective to 1.0. As a result, the first objective is guaranteed to dominate the second one. (Note that in your example, D = 1.0 and [l,u] = [-sum(values),0] would guarantee this behavior!) However, this might easily lead to numerical issues if the chosen weight leads to a too large objective range.
As you might also see from this example, Gurobi does not need solution pools to find the objective for either version.
I hope that helps answer your questions.
Best,
Martin
----
Dr. Martin Bromberger - MIP Development Scholar
Gurobi GmbH
Sandstraße 104
40789 Monheim am Rhein
Email: martin.bromberger@gurobi.com (he, him, his)
-------------------------------------------------------------------------------
Sitz der Gesellschaft: Düsseldorf
Registergericht: Düsseldorf, HRB 99473
Geschäftsführer: Craig Albrecht und Duke Perrucci0 -
-
Thank you Martin, this is very comprehensive.
While the separate two optimizations are clear, I am now struggling with the model specification of a pure blended multi-objective, now on a much larger matrix of about 50k columns and 50 rows.
The R implementation, using 99% the same codebase, takes 6-7x less time than the C implementation, which seems rather weird.
EDIT: this is the timing for the entire code with dozens of optimizations not just one./* new model with PIs variables */ error = GRBnewmodel(env, &model, "setcover", PIs, NULL, NULL, NULL, NULL, NULL); if (error) goto QUIT; /* binary vars */ for (int j = 0; j < PIs; j++) { error = GRBsetcharattrelement(model, GRB_CHAR_ATTR_VTYPE, j, GRB_BINARY); if (error) goto QUIT; } /* covering constraints */ for (int i = 0; i < ON_minterms; i++) { int nz = 0; for (int j = 0; j < PIs; j++) { // xvec was filled column-major as idx = i + ON_minterms * j if (xvec[i + ON_minterms * j] == 1) { // row i, col j ind[nz] = j; coeffs[nz] = 1.0; nz++; } } error = GRBaddconstr(model, nz, ind, coeffs, GRB_GREATER_EQUAL, 1.0, NULL); if (error) goto QUIT; } /* indices (all variables) */ for (int j = 0; j < PIs; j++) ind[j] = j; /* first objective: minimize sum x_j */ { for (int j = 0; j < PIs; j++) coeffs[j] = 1.0; error = GRBsetobjectiven( model, 0, // objective index 1, // priority 1.0, // scaling factor (weight) 0.0, // abstol (absolute tolerance) 0.0, // reltol (relative tolerance) "mincols", // name (optional, can be NULL) 0.0, // constant term, usually 0.0 PIs, // number of nonzero coefficients ind, // variable indices coeffs // coefficient values ); if (error) goto QUIT; } /* second objective: maximize weighted value */ // weights is a vector of length PIs { for (int j = 0; j < PIs; j++) coeffs[j] = -1 * weights[j]; error = GRBsetobjectiven( model, 1, 0, 1.0, 0.0, 0.0, "maxvalue", 0.0, PIs, ind, coeffs ); if (error) goto QUIT; } /* optimize */ error = GRBoptimize(model); if (error) goto QUIT; double objval; error = GRBgetdblattr(model, GRB_DBL_ATTR_OBJVAL, &objval); if (error) goto QUIT;There seems to be some difference from the R implementation:
model <- list( A = x, modelsense = "min", rhs = rep(1, ON_minterms), sense = rep(">=", ON_minterms), vtype = rep("B", PIs) ) model$multiobj <- list( list( objn = rep(1, PIs), priority = 1, weight = 1 ), list( objn = -1 * weights, priority = 0, weight = 1 ) )0 -
-
To answer my own question, it was a confusion: R was solving without the second objective, because of a forgotten variable. And that of course explains the time difference.
Apologies for the false alarm, all clear now,
Adrian0 -
Please sign in to leave a comment.
Comments
23 comments