This is kind of a "one in ten thousand users" thing, so I'm not surprised that it is not a built-in feature. (I've not heard of it as a feature in any other MILP solver, for that matter.) Also, for what it's worth, it is known that even when you have an objective function and want only optimal solutions, not every optimal solution can be found by a branch-and-cut MIP solver, because some of the optima may not be extreme points of the integer hull.
Original Message:
Sent: Thu November 19, 2020 03:14 PM
From: Andy Ham
Subject: Cplex returns duplicate solution
Thanks! I wish Cplex automatically does the tasks for user ^^
Original Message:
Sent: Thu November 19, 2020 02:57 PM
From: Paul Rubin
Subject: Cplex returns duplicate solution
An approach I have used (with CPLEX -- should also work with CPO) to generate multiple feasible solutions is the following.
- Maximize a randomly generated linear objective function, capturing intermediate (suboptimal solutions) along the way (via the solution pool in CPLEX; hopefully there is something similar in CPO).
- Minimize the same function, again capturing intermediate solutions.
- Repeat with new random objectives until either a time limit is hit or I go a certain number of iterations without generating a new solution.
This requires an efficient method to detect duplicate solutions, and the method does not necessarily capture all feasible solutions (even without time and failure limits).
------------------------------
Paul Rubin
Professor Emeritus
Michigan State University
Original Message:
Sent: Thu November 19, 2020 02:45 PM
From: Andy Ham
Subject: Cplex returns duplicate solution
Thanks for the info, but that setting makes my model slow. CP was able to generate hundreds of feasible solutions (most are duplicated though) within 60 s with default setting. With the new setting, no solution was found within 60 s.
! --------------------------------------------------- CP Optimizer 20.1.0.0 --
! Satisfiability problem - 1,482 variables, 7,795 constraints, 1 phase
! Presolve : 1,667 extractables eliminated
! TimeLimit = 60
! LogVerbosity = Terse
! Initial process time : 0.12s (0.12s extraction + 0.01s propagation)
! . Log search space : 1,270.5 (before), 1,270.5 (after)
! . Memory usage : 3.6 MB (before), 3.6 MB (after)
! Using parallel search with 8 workers.
! ----------------------------------------------------------------------------
! Branches Non-fixed W Branch decision
* 725 0.19s 8 3 = CPx#0#180
* 1,510 0.21s 3 1 = k#0#15
* 16,885 0.41s 8 1 = k#0#14
* 22,409 0.47s 1 1 = k#0#19
* 25,804 0.58s 1 1 = k#0#19
* 25,805 0.58s 1 1 != k#0#19
* 25,806 0.59s 1 1 != k#0#10
* 25,807 0.59s 1 1 != k#0#9
* 25,808 0.59s 1 1 != k#0#8
* 25,809 0.59s 1 1 != k#0#7
* 25,810 0.60s 1 1 != k#0#4
! --------------------------------------------------- CP Optimizer 20.1.0.0 --
! Satisfiability problem - 1,482 variables, 7,795 constraints, 1 phase
! Presolve : 1,667 extractables eliminated
! TimeLimit = 60
! Workers = 1
! LogVerbosity = Terse
! SearchType = DepthFirst
! Initial process time : 0.13s (0.12s extraction + 0.01s propagation)
! . Log search space : 1,270.5 (before), 1,270.5 (after)
! . Memory usage : 3.6 MB (before), 3.6 MB (after)
! Using sequential search.
! ----------------------------------------------------------------------------
! Branches Non-fixed Branch decision
Original Message:
Sent: Thu November 19, 2020 02:34 PM
From: Olivier Oudot
Subject: Cplex returns duplicate solution
For the particular case of CP, to get list of unique solutions, you just have to set the following solver parameters:
- SearchType=DepthFirst
- Workers=1
Syntax depends on the language you are using. Please refer to the documentation for details.
------------------------------
Olivier Oudot
Original Message:
Sent: Thu November 19, 2020 02:18 PM
From: Andy Ham
Subject: Cplex returns duplicate solution
I do have the exactly same issue with CP. I need to generate as many feasible solutions as possible without objective. In my example, CP generated 1000 solutions, but there were only 165 unique solutions. When I put objectives based on the above discussion, my model could not find multiple feasible solutions, but only one within a given time.
Cplex version: 20.1.0.0 Early Release
cp.startNewSearch();
while(cp.next()) { ...}
Original Message:
Sent: Tue November 10, 2020 05:24 AM
From: Philippe Couronne
Subject: Cplex returns duplicate solution
Yes, I added both the objective and the settings.
The settings are present to find a solution faster, I'm not sure they will work in a similar manner without any objective.
I introduced a dummy objective from my understanding of how populate works: from a solution, it explores neighboring solutions
by relaxing gap. This dummy objective is only present to help populate find neighboring solutions.
Again, the fact that this model has so few solutions might indicate a problem in its formulation, which
go well beyond my support duties.
As for documentation, `Model.populate` returns an instance of class `docplex.mp.SolutionPool`, which is documented.
------------------------------
Philippe Couronne
Original Message:
Sent: Tue November 10, 2020 04:30 AM
From: Sana Nazari
Subject: Cplex returns duplicate solution
Thank you Philippe.
So you added these new setting to a model with an objective. Right?
And in the limit of 2h you did not get any duplicate solutions? The model is okay, the only important thing now is to avoid duplicates and see how many actual solutions we can get. If I add these new settings to my model (no objective) will it avoid duplicates?
And the last question, is there any documentation for the docplex pool?
------------------------------
Sana Nazari
Original Message:
Sent: Mon November 09, 2020 10:02 AM
From: Philippe Couronne
Subject: Cplex returns duplicate solution
I did some experiments on your dataset. with the cplex interactive optimizer.
To summarize, I added a (dummy) objective to ease the behavior of populate, and tried various settings.
More precisely:
- I compute the sum of binary variables, not used in any indicator constraints (I wanted to avoid too many side-effects) and use it
as a minimization objective
_ I set a large mip gap, say 35% to stop populate phase 1 early and switch to phase 2.
- After some experiments, the best emphasis setting I found is `feasibility` (1)
- I set `lpmethod` to 2 and all cuts to 'aggressive' (2)
With a 2-hour time limit, populate finds 3 solutions only. This confirms the problem is very hard. If this is not your expectation, then maybe something is wrong in the model formulation itself.
I am attaching the log from CPLEX inetractive
Lastly, docplex 2.16 is out today, containing native support for solution pools (see method `Model.populate_solution_pool`.
I suggest you update your docplex version to 2.16 (a simple pip install --update should be enough from 2.15)
------------------------------
Philippe Couronne
Original Message:
Sent: Fri November 06, 2020 06:08 AM
From: Sana Nazari
Subject: Cplex returns duplicate solution
Sorry, I missed you last question. I export all the solutions to csv files and compare them. Here is my method of export:
numsol = cpx.solution.pool.get_num()
for i in range(numsol):
sol_pool.append([j for j, a in enumerate(cpx.solution.pool.get_values(i)) if a > 0.5])
ii=0
import pandas as pd
for element in tqdm(sol_pool):
solution=np.zeros((n,n1),dtype=np.int)
for j in element:
v = mdl.get_var_by_index(j)
if v.name.startswith('x'):
i1 = v.name.split('_')[1]
i2 = v.name.split('_')[2]
schedule[int(i1)][int(i2)]=1
pd.DataFrame(solution).to_csv("solution%s.csv" %ii,index=False)
ii+=1
Then I use python to compare these csv files. Also, I checked by hand to make sure everything works fine.
------------------------------
Sana Nazari
Original Message:
Sent: Wed November 04, 2020 06:16 AM
From: Xavier Nodet
Subject: Cplex returns duplicate solution
It seems you posted a slightly more detailed question at https://stackoverflow.com/questions/64608122/cplex-solution-pool-generates-duplicate-solutions. Sorry for the delay here...
It's unexpected that the solution pool is filled with identical solutions.
Could you please specify which version of CPLEX you use?
Is it possible for you to share the model? You can export a SAV file from docplex, and then it's easy for you or us to load this model in the CPLEX Interactive to reproduce the issue with the following command:
cplex -c "read myfile.sav" "set mip pool intensity 4" "set mip pool absgap 1e75" "set mip pool relgap 1.75" "set mip limits populate 20000" "opt"
Also, please define how exactly you compare two solutions to determine whether they are identical.
------------------------------
Xavier