Range constraint with an or condition

回答済み

Pranay Raj

• 2021年07月21日 07:32

Hi, I wanted to model a range constraint with or clause

python code might look something like this:

intervals = []#(list of tuples which has intervals) # input information
access = []#(list of tuples which is our gurobi variable) # gurobi variable
for i in range(len(access)):
    or( m.addConstr((access[i][0] >= intervals[t][0]) and (access[i][1]<=intervals[t][1]) for t in range(len(intervals)) ) )
    

for example intervals = [(1,5), (8,15), (18,24)], I want the access to lie in one of these intervals only

1

• 正式なコメント

  

  Simranjit Kaur

  Gurobi Staff

  • 2024年12月06日 00:29

  This post is more than three 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 why not try our AI Gurobot?.
• 

  Matthias Miltenberger

  Gurobi Staff

  • 2021年07月21日 12:03
  • 編集済み

  Hi Pranay!

  This is one way to model this using manual range constraints (adding an additional explicit slack variable to express each range) and indicator constraints:

  import gurobipy as gp
  
  m = gp.Model()
  intervals = [[1, 5], [8, 15], [18, 24]]
  x = m.addVar(name="x")
  y = m.addVar(name="y")
  z = m.addVars(len(intervals), vtype="B", name="ind")
  c = {}
  slack = {}
  
  for i, interval in enumerate(intervals):
      slack[i] = m.addVar(lb=interval[0], ub=interval[1], name=f"s{i}")
      c[i] = m.addConstr((z[i] == 1) >> (x + y - slack[i] == 0), name=f"range{i}")
  
  m.addConstr(gp.quicksum(z) <= 1, name="select")

  The "select" constraint enforces the "or" condition, only allowing one of those range constraints to be active.

  The resulting model in LP format looks like this:

  Minimize
  Subject To
   select: ind[0] + ind[1] + ind[2] <= 1
   range0: ind[0] = 1 -> x + y - s0 = 0
   range1: ind[1] = 1 -> x + y - s1 = 0
   range2: ind[2] = 1 -> x + y - s2 = 0
  Bounds
   1 <= s0 <= 5
   8 <= s1 <= 15
   18 <= s2 <= 24
  Binaries
   ind[0] ind[1] ind[2]
  End

  Cheers,
  Matthias

  1
• 

  Pranay Raj

  • 2021年07月21日 14:04

  

  

  

  Hi Matthias,

  Thanks for the quick reply, so in my case the code should be something like this right:

  import gurobipy as gp
  
  m = gp.Model()
  intervals = [[1, 5], [8, 15], [18, 24]]
  k = 10
  access = [(x,y) for x in range(k) for y in range(len(2))]
  
  z = {}
  
  for i in range(k):
      c = {}
      slack = {}
      z[i] = m.addVars(len(intervals), vtype="B", name=f"ind_{i}")
  
      for j, interval in enumerate(intervals):
          slack[j] = m.addVar(lb=interval[0], ub=interval[1], name=f"s{i}_{j}")
          c[j] = m.addConstr((z[i][j] == 1) >> (access[i, 0] + access[i, 1] - slack[j] == 0), name=f"range{i}_{j}")
      m.addConstr(access[i,0]<=access[i,1])
      m.addConstr(gp.quicksum(z[i]) == 1, name=f"select_{i}")

  I made changes to the select constraint to == instead of <= as I need at least one of them to be true and added another constraint to get the tuple in correct order, is this the correct way of doing it

  0
• 

  Matthias Miltenberger

  Gurobi Staff

  • 2021年07月21日 14:10

  Hi Pranay,

  You should just write out the model file to verify whether this corresponds to your mathematical model:

  m.write("model.lp")

  It's also always a good idea to have a small test case where you can easily verify the correctness of the solution.

  Cheers,
  Matthias

  0

投稿コメントは受け付けていません。