Simple MIP-problem seems really difficult for Gurobi to solve, can model be improved or optimized?

Hello,

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)

Matthias Miltenberger

Gurobi Staff

March 16, 2023 11:17 Edited

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:

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,
Matthias

Simple MIP-problem seems really difficult for Gurobi to solve, can model be improved or optimized?

Comments

Didn't find what you were looking for?