メインコンテンツへスキップ

How can I obtain multiple feasible solutions for a non-convex MIQCP?

回答済み
shir cohen
  • Conversationalist
  • First Question

I’m working on a non-convex MIQCP model in Gurobi.
I would like to obtain multiple feasible solutions, similarly to how the Solution Pool works for MIP or convex MIQCP problems.

I tried setting the following parameters:

model.Params.NonConvex = 2
model.Params.PoolSearchMode = 2
model.Params.PoolSolutions = 10

However, after optimization, I always get only a single solution (model.SolCount == 1).

Is there any supported or recommended way to:

  1. Generate multiple feasible solutions for a non-convex MIQCP (for example, multiple local optima or diverse integer-feasible points)?
  2. Encourage Gurobi to explore different feasible basins (e.g., using Seed, multi-start, or any parameter combination)?
  3. Or alternatively, do I need to run the solver multiple times with different settings to collect such solutions manually?

Any clarification on what’s currently supported (or best practices to approximate a solution pool behavior in non-convex MIQCPs) would be greatly appreciated.

Thank you,

 

関連

0

コメント

10件のコメント

日付 投票
  • Jaromił Najman
    • Gurobi Staff

    Your settings should be the correct ones. Could you please share the log output and a minimal working example of how you call your model?

    0
  • shir cohen
    • Conversationalist
    • First Question

    Hi, 

    Thank you for your quick reply.

    Here is the corresponding solver log summary:

    Non-default parameters:
  TimeLimit = 14400
  Seed = 42
  PoolSolutions = 2
  PoolSearchMode = 2
  PoolGap = 0.05

....

....

....
Solving non-convex MIQCP

....
....
....
Explored 275,929 nodes (75,608,727 simplex iterations) in 14,400.13 seconds (11,714.36 work units)
Thread count was 8 (of 128 available processors)

Solution count 2: 108.457 108.457
SolCount: 2
Unique SolCount: 1

    To check the uniqueness of the solutions, I used the following function:

    def check_unique_sol(config, nsol):
    tol = 1e-6
    unique_sols, sols = [], []
    for k in range(nsol):
        config.model.Params.SolutionNumber = k
        vals = {v.VarName: v.X for v in config.model.getVars()}
        sols.append(vals)
    for idx, sol in enumerate(sols):
        is_new = True
        for _, usol in unique_sols:
            if all(abs(sol[v] - usol[v]) <= tol for v in sol):
                is_new = False
                break
        if is_new:
            unique_sols.append((idx, sol))
    print("Unique SolCount:", len(unique_sols))
    return unique_sols

    The check confirms that both solutions are numerically identical (within tolerance), even though model.SolCount == 2.

    Would it be expected behavior for non-convex MIQCPs that multiple solution entries in the pool can correspond to the same solution numerically?
    Or could this indicate that Gurobi did not find multiple distinct local optima under these settings?

    Additionally, could you please clarify how Gurobi identifies and stores pool solutions internally in this context? If possible, could you also share any materials or documentation that explain how the solution pool mechanism works for (non-convex) MIQCP models?

    Thank you again for your help.

    0
  • Jaromił Najman
    • Gurobi Staff

    Hi Shir,

    Thank you for sharing the log output.

    You are asking for 2 best solutions by setting PoolSolutions=2. During the normal optimization process Gurobi finds 2 solutions with the same objective value which happens to be the globally optimal objective value.

    Would it be expected behavior for non-convex MIQCPs that multiple solution entries in the pool can correspond to the same solution numerically?

    It is possible that two solutions are the same within some tolerances. For the two solutions, could you please print the values of \(\texttt{abs(sol[v] - usol[v]}\) for each variable. It may be that the difference in solution point values is below the tolerance of 1e-6 that you chose, but still > 0.

    Or could this indicate that Gurobi did not find multiple distinct local optima under these settings?

    For numerically difficult models, it could happen that there is one duplicate of the optimal solution point in the solution pool, which might arise from missing numerical precision. If the test \(\texttt{abs(sol[v] - usol[v]}\) indicates that the solution point are equal for a tolerance less than 1e-6, then I would recommend increasing the PoolSolutions parameter value.

    Additionally, could you please clarify how Gurobi identifies and stores pool solutions internally in this context?

    Gurobi stores up to PoolSolutions=N solutions found during the solution process. For PoolSearchMode=2 we search for the N best solutions. If after solving the model to global optimality, we still have < N best solutions, then Gurobi starts a subsequent solution process. In this process Gurobi continues solving the original model, but it makes sure that the already found solution points are excluded from the feasible set of the problem. Often, finding additional solutions is easier because information found about the original model can be re-used. However, there are cases where the search for additional N best solutions is as hard as solving the original model.

    Best regards,
    Jaromił

    0
  • shir cohen
    • Conversationalist
    • First Question

    Thanks for the details. 

    I’m noticing that even though SolCount = 3, all the objective values are identical (115.572) and the absolute differences between solutions are zero, this means all the solutions are effectively the same. I’m seeing this behavior across multiple problem instances as well.

    Could you clarify what might cause Gurobi to return multiple identical solutions in the solution pool (i.e., UniqueSolCount = 1)? I’ve already verified that the model is non-convex (NonConvex = 2) and that the pool parameters are set correctly (PoolSearchMode = 2, PoolSolutions = 3, PoolGap = 0.05), but it seems Gurobi isn’t finding any diverse feasible points.

    Is this expected for non-convex MIQCPs, or could it indicate that the solver is exploring only one basin of attraction?

     

    Non-default parameters:
TimeLimit  10800
Seed  42
PoolSolutions  3
PoolSearchMode  2
PoolGap  0.05
...
Solving non-convex MIQCP
Variable types: 7964 continuous, 10518 integer (10518 binary)
...
Solution count 3: 115.572 115.572 115.572 
....
Status: 9
SolCount: 3
{'var_1[0]': 0.0, 'var_2[0]': 0.0, 'var_3[0]': 0.0, .....}
Unique SolCount: 1

     

    0
  • Jaromił Najman
    • Gurobi Staff

    This looks wrong.

    Which Gurobi version are you using? I remember that there was some issue of exactly that kind in a previous version.

    If a version upgrade does not resolve the issue, then could you please export the model to an LP or MPS file and share it such that we can have a closer look. Note that uploading files in the Community Forum is not possible but we discuss an alternative in Posting to the Community Forum.

    Best regards, 
    Jaromił

    0
  • shir cohen
    • Conversationalist
    • First Question

    Hey,

    Thanks for the follow-up. I found a bug in my code; I was using .X instead of .Xn when iterating through the solution pool, which caused the weird behavior. After fixing it, everything works correctly now.

    BTW, I’m using Gurobi 12.0.2.

    Best, 

    Shir

     

    0
  • Jaromił Najman
    • Gurobi Staff

    Great to hear that the issue could be resolved!

    0
  • shir cohen
    • Conversationalist
    • First Question

    Thanks!


    Now I can indeed see small differences in the X values between the solutions, but the changes are quite minor.
    Is there any configuration or parameter that could encourage larger variations between solutions?
    For example, something that gives the heuristics more time or increases the diversity of the explored solutions?

    0
  • Jaromił Najman
    • Gurobi Staff

    Is there any configuration or parameter that could encourage larger variations between solutions?

    Currently, there is no such parameter.

    If your timelimit allows, you could try increasing the number of poolsolutions. This would lead to finding a larger pool of n-best solutions, which should hopefully lead to more solution diversity. Please note that for non-convex models it is not that unusual that there exist some similar solutions with an objective value very close to the globally optimal objective value. Especially, if the allowed MIPGap is rather large, i.e., > 1%.

    0
  • shir cohen
    • Conversationalist
    • First Question

    Thank you for your reply and for clarifying how the pool search works in the non‐convex MIQCP case.

    0

サインインしてコメントを残してください。

お探しのものを見つけられませんでしたか？

新規投稿