Changing the order of the constraints affects performance
AnsweredI am solving an MIP. I noticed that if I change the order in which constraints are added slightly, it drastically affects the solution runtime. Currently, I have an MIPGap = 1%. One order gets to the solution with 0% gap, but the other order terminates at 0.9% gap. To get the same solution, I need to set MIPGap = 0.001%, which takes an impractically longer time.
What I want is, I do not care about the solution quality as long as it is within 1% gap, but I want to make sure the solution is agnostic to constraint ordering. Is there any way to achieve that?
-
-
Gurobi Staff
Hi Krypt,
if I change the order in which constraints are added slightly, it drastically affects the solution runtime
It sounds like your model has a large performance variance. Are there signs of numerical issues?
I want to make sure the solution is agnostic to constraint ordering. Is there any way to achieve that?
There is not - this is common to all MIP solvers. The moment anything changes in the model the solver possibly follows a different solution path. Even if you solved to 0% MIP Gap you might get different optimal solutions (there is often more than 1).
Not sure if it fits your use case, but you can reorder variables and constraints by their names to create a new model with the following Python function:
import gurobipy as gp import numpy as np def order_model(m, var_order = None, constr_order=None): vars = m.getVars() init_varname = m.getAttr("VarName", vars) if var_order is None: var_argsort = np.argsort(init_varname) else: var_argsort = np.argsort(init_varname)[np.argsort(np.argsort(var_order))] lb = np.array(m.getAttr("lb", vars))[var_argsort] ub = np.array(m.getAttr("ub", vars))[var_argsort] obj = np.array(m.getAttr("obj", vars))[var_argsort] vtype = np.array(m.getAttr("vtype", vars))[var_argsort] varname = np.array(init_varname)[var_argsort] constrs = m.getConstrs() init_constrname = m.getAttr("ConstrName", constrs) if constr_order is None: constr_argsort = np.argsort(init_constrname) else: constr_argsort = np.argsort(init_constrname)[np.argsort(np.argsort(constr_order))] sense = np.array(m.getAttr("Sense", constrs))[constr_argsort] rhs = np.array(m.getAttr("RHS", constrs))[constr_argsort] constrname = np.array(init_constrname)[constr_argsort] mnew = gp.Model() x = mnew.addMVar(m.NumVars, lb, ub, obj, vtype, varname) A = m.getA()[constr_argsort][:, var_argsort] mnew.addMConstr(A, x, sense, rhs, constrname) mnew.ModelSense = m.ModelSense mnew.update() return mnew- Riley
0 -
-
Riley, this is really helpful. Thank you very much!
One more question, what can I try to minimize this behavior as much as possible? What are the settings that I can potentially play with?0 -
-
-
The reason I asked about numerical issues is that it is often a culprit behind high performance variance. So if it is numerical issues you can refer to Solver Parameters to Manage Numerical Issues.
But models will naturally have a performance variance - when you change parameters (such as Seed), or build the model in a different order, of run on a different machine - and trying to find parameters which help reduce the variance requires parameter tuning. I'd start with parameters like MIPFocus, Method, Presolve. The NoRel heuristic might help consistently find good solutions too. Also see “How can I make accurate comparisons”.
- Riley
0 -
-
I see. I will check the numerical issue.
If I understood you correctly, even if the model does not have a numerical issue, we can never guarantee that we will get the same performance irrespective of constraint/variable ordering?
0 -
-
-
Yes, this is correct. We see actually see this is a good thing, as it allows you to characterize performance variance so that you can understand how similar models may perform.
1 -
-
thanks for all the help!
0 -
Please sign in to leave a comment.
Comments
6 comments