Failed to find feasible solutions on super-undertermined problems
Answered
Hello Gurobi community, I met a problem on finding the feasible solutions to super under-determined problems.
I am trying to find 10 feasible solutions to the problem containing 25 unknowns limited by 3 constraints. Obviously the problem is very under-determined, and I am expecting the solver should return different feasible solutions easily.
However, no matter how I change the random seed, shuffle the input order of constraints and change the variable names, the solver only returns one feasible solution.
I am wondering why this happened? Is this related to the optimization technique in the solver?
-
Hi,
Have you tried to follow How do I find additional solutions to a model? and links within?
Cheers,
David0 -
Hi David,
Thanks for the prompt reply. I already set up PoolSolution to 1000 (this is large enough) and PoolSearchMode to 2, but the solver only returns one feasible solution.
I should explain my problem a little bit:
Our model contains 3 non-conflicting constraints and 25 unknowns. Our objective function is trivial (0). Our goal is asking the solver to return a couple of feasible solutions bounded by the input constraints.
Since there are only three constraints in the model, they cannot confirm the value assignments of 25 unknowns.
I am expecting the model to "loop through" the possible values of unknown variables that are not bounded by the constraints, but the model seems only initializing these variables and not "looping through" them. Do you know why?
Best,
Yifeng0 -
Hi Yifeng,
That is interesting.
The problem is relatively small, is it solved during presolve?
You can see this in the log when presolve removes all rows + columns.
If you can share the log and copy-paste the LP file, it might be easier to help.Cheers,
David0 -
Hi David,
I slightly change the number of variables and the number of constraints in my latest experiments.
Here is the log from Gurobi solver:
Could you take a look?
Thank you very much for your help!
Best,
Yifeng0 -
Hi again Yifeng,
That looks good, near the bottom of the log it says that the solution count is 1000 (all are feasible solutions).
All of them have objective value 0 as you don't have an objective function.You can loop through the solutions and obtain the value of the variables like shown in the poolsearch.py example.
Something like:
for n in range(model.SolCount):
model.params.SolutionNumber = n
print()
print(f"Solution {n = }")
for v in model.getVars():
print(f"{v.Xn = }")I am expecting the model to "loop through" the possible values of unknown variables that are not bounded by the constraints, but the model seems only initializing these variables and not "looping through" them. Do you know why?
I am not sure what you mean here. Does the above example not work for you?
Cheers,
David0 -
Hi David,
First, I want to thank you for the reply! However, the method you mentioned didn't work.
I want to assign value to a tabular consisting of 5 rows and 5 columns (column name A, B, C, D, E), and all columns have the range of {0,1,2}. To solve the value assignment problem, I set up 25 unknown variables, each variable represents one element in the tabular. I give the constraints on variables in column B, C, D and E, but I didn't give any constraint on column A.
The output from the solver is posted above. As you can see, the value of variables in column A is all assigned to 0. I think this is because the solver simply outputs the initialized value 0. So, my first question is: Do you know how to set up random initialization?
Also, no matter how I change the random seed or assign poolSolution parameters, the output values in column A remains to be 0. What I expect is the solver could output other possible values in the column A's domain (looks like the solver is "looping" through the domain of columns A). Thus, my second question is : Why my expectation does not happen?0 -
Hi Yifeng,
If variable A does not appear in any constraints or the objective it can be removed from the problem.
It's value set to 0 as they don't have an effect on the problem. This is expected and not affected by the seed.Try adding it to a constraint e.g. the some over the A column must be at least 1.
Or forcing the variable values by setting the lower and upper bounds to the value that you want.
If you only force the value and it is still not present anywhere else, you should expect the exact same values for the rest of the variables you are observing now.Cheers,
David0 -
Hi David,
Thanks for the previous help. I think I met another problem on the precision of GRB.BINARY variables.
Here the binary variables are showing values like 0.9999999999999999978 and 1.0000000000000004. I am wondering if there exist a method to strictly force the value of binary variable to be either 0 or 1.
Best,
Yifeng
0 -
Hi Yifeng,
You can tighten up IntFeastTol and/or set IntegralityFocus to 1.
Cheers,
David0 -
In addition to David's reply, please refer to Why does Gurobi sometimes return non-integral values for integer variables?
1
Please sign in to leave a comment.
Comments
10 comments