Simple MIP-problem seems really difficult for Gurobi to solve, can model be improved or optimized?
AnsweredHello,
I am trying to solve the optimization model below, which I feel shouldn't be too difficult. But even for small instances of the problem, gurobi is having a really hard time closing the MIP gap. And even for small instances, doesn't seem to reach an optimal solution (atleast in the time I've run it thus far). I am pretty new to Gurobi, is there a problem with the model, or is there some parameter setting I'm missing that could make it faster? One thing I've thought about is that the model can't prioritize which y should be 0 or 1, as they all have the same cost.

Would really appreciate any tips! I've implemented this using the python API, like so:
# Create variables. Binary y[i,j] = [0,1], continuous x[i,j] = [0,inf].
y = m.addVars(len(buy_orders), len(sell_orders), vtype=GRB.BINARY, name="y")
x = m.addVars(len(buy_orders), len(sell_orders), vtype=GRB.CONTINUOUS, name="x")
# Set constraints. Sum of x[i,j] = buy_orders[i], sum of x[i,j] = sell_orders[j]
m.addConstrs((x.sum(i, '*') == buy_orders[i]['Volume'] for i in range(len(buy_orders))), name="c1")
m.addConstrs((x.sum('*', j) == sell_orders[j]['Volume'] for j in range(len(sell_orders))), name="c2")
# Set constraint, if x>0 then y=1
m.addConstrs((x[i,j] <= min(buy_orders['Volume'][i], sell_orders['Volume'][j]) * y[i,j] for i in range(len(buy_orders)) for j in range(len(sell_orders))), name="c3")
# Set objective: Minimize the total cost of the trades. t*y[i,j], (t=1)
t=1
m.setObjective(t*y.sum(), GRB.MINIMIZE)
0
-
Official comment
This post is more than two years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum, or try Gurobot, our chatbot interface offering instant, expert-level support. -
Hi Victor!
It's hard to tell whether there is something wrong with that model without more information on the actual data or a Gurobi log file.
You can check our guide on MIP Logging - Gurobi Optimization to better understand the output of Gurobi. One of the first parameters to play around with is MIPFocus and you can read more about the different parameters types here: MIP Models - Gurobi Optimization.
Our TechTalks on how to improve weak formulations are also a great way to get started with this topic:
- Tech Talk & Chat– Converting Weak to Strong MIP Formulations - Gurobi Optimization
- Tech Talk & Chat– Converting Weak to Strong MIP Formulations, Part II - Gurobi Optimization
You should always keep in mind that MIP solving is NP-hard, and sometimes, even small or seemingly easy instances can take a long time to solve or even just to find a feasible solution.
Cheers,
Matthias0
Post is closed for comments.
Comments
2 comments