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

回答済み

Victor Jonsson

2023年03月16日 09:35

• 
• 

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)

関連

• Modeling
• MIP
• Performance

0

• 

  Matthias Miltenberger

  • Gurobi Staff

  2023年03月16日 11:17 編集済み

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

  0

サインインしてコメントを残してください。