Local optima
Answered
I am running a MIP problem. I am using a set of inputs and the code converges and I get 27 feasible solutions (which are optimal matches) that would reduce the objective function, although I was expecting more, based on heuristics approaches. I test the other solutions by inputting smaller subset, one by one referring to these unidentified solutions (matches), and the code is able to identify those solutions (matches) when I do so. I am confused, why is the code not identifying these matches that reduce the total cost without affecting the other identified matches. It seems that the code is getting stuck at a local optima. I am setting presolve =0 because it was causing errors before. How do I debug the code? and solve this issue with the model?
-
Hi,
I am unsure if I understand your case, but let me try to rephrase it: The solutions returned by the solver are not optimal. You can generate solutions that further improve the objective value. Is this correct?
There are several reasons why the solver returns with suboptimal results:
- Some termination criterium forces the solver to stop earlier. For example, by default, the target MIP gap is 1e-4. Maybe this is not enough for your model, you could set the parameter MIPGap=0.
- In many cases, some constraints in the model are too restrictive. Probably, there is some typo in your code that generates the model. You could write the model in a readable format with Model.write("model.lp") (in Python). For small instances, you should be able to see if all constraints are correctly formulated.
- The solver runs into numerical issues. In many cases, there are warnings in the Gurobi log output. See also our numerical guidelines.
- The solver only guarantees to find at least one optimal solution for the model at hand. If you want to retrieve more solutions, e.g., the N best solutions, then you could experiment with parameter PoolSearchMode.
1 -
Great advice, I will try them all. Thank you so much.
0 -
There are no warnings. The model is written fine. I tested with MIPGap, but since the model is large it consumes too much time to get to MIPGap=0.
When I test a bigger number of elements that I wish to match in groups, the solution I am getting is no matches at all. Although when I test a few elements, I do get matches.
My assumption is that I am setting placeholder variables for the assignments of a number of elements in one matching group. I am setting 100 variables, as I know there won't be more successful matches, however, the possible combinations are in the magnitude of millions. Could it be that the model is not successfully switching and testing different matching of elements and assigning them in those variable placeholders of matched groups? So it is getting stuck by comparing some random 100 groups to no matches at all, and in many instances the solution given is no matches at all?
0 -
Since I do not know the exact definition of your optimization problem and the corresponding model formulation, it is hard to say where there is an issue. If you could give a textual and mathematical description of your problem, including the mathematical formulation, I might be able to detect some issue.
Since the most challenging part is usually to design and implement the model for an optimization problem, I suspect your current mathematical formulation does not correctly model the problem you want to solve.
The algorithm used in the solver is exact, i.e., it does not miss or ignore any assignments, except for suboptimal or infeasible ones. It guarantees that you will obtain at least one optimal solution for your model (if your time limit allows it). If you want to obtain more than one optimal solution, then you might need to play with parameter PoolSearchMode and PoolSolutions.
0
Please sign in to leave a comment.
Comments
4 comments