Comparing suboptimal solutions for different scenarios and defending the use of Gurobi as a solver in an academic setting,
Awaiting user input
Hi, I would like to defend the use of Gurobi in an academic setting and would very much appreciate any advice and help in doing so.
I have formed a MIQP (for a rich variant of the VRP) and two MIQCP problems (for rich variants of the Vehicle Scheduling Problem) and sought to compare the outcomes and associated decision variables adopted for a variety of scenarios analysed. The problems are NP hard and as a result, I get optimality gaps of <10% for the MIQP problem and 20-40% for the MIQCP problems.
I ultimately want to answer the question: Are the solutions for different scenarios comparable (despite the optimality gaps)?
- Specifically, I think this means: How can I demonstrate that the solution techniques used by Gurobi are appropriate and that the uncertainty that remains to optimality is not subject to structural or hidden biases which might favour one or another scenario? (scenarios vary in input values, but not the objective function or constraints)
- As a follow up, is there a way to get Gurobi to implement simple, well known solution approaches without all of the fancy/sophisticated, but less transparent heuristics? Even if it means less-optimal answers?
I believe I have also managed to convert the problems to MILPs, however this doesn’t appear to have improved the solutions or optimality gaps. Is it possible to get more detail on how the quadratic problems are solved and why I don't get better results if I convert to MILPs?
-
Hi Garrett,
Just to understand your situation a bit better, you have 3 VRP models and for each model you have several instances (=scenarios), right?
For each model you want to compare the solutions for the different scenarios. What exactly do you want to compare? The runtime to solve them, the obtained objective values, or the solution structure itself? The latter two aspects are independent of your solution method, this depends only on the model and the input values.
In general, the current state-of-the-art methodology to solve MIQPs, MILPs, etc. based on branch-and-bound is subject to high variability, i.e., the same mathematical model with different input values can potentially lead to significantly different runtimes. Many random decisions are taken throughout the optimization process (in branching, cutting, heuristics, etc.) that finally lead to a provably optimal solution, but potentially over different solution paths. The runtime can therefore be hardly predicted.
I am not sure if I understand your second question. Do you want to switch off some components of Gurobi, e.g., built-in heuristics, cuts, presolving, etc.? Even if you would do that (I do not recommend this), the algorithm stays a black-box, the millions of decisions taken will not be transparent.
Regarding the linearizations to MILP, it depends on the way you did it whether it pays off or not. Gurobi can re-solve quadratic terms in different ways, there are also parameters that control this, e.g., MIQCPMethod, PreMIQCPForm. We have a webinar that describes more details how Gurobi considers quadratic constraints.
0
Please sign in to leave a comment.
Comments
1 comment