Integer division in integer programming

回答済み

Nick Fryganiotis

2024年02月27日 20:06

• 
• 
• 

In case of an integer programming problem, i would like to add in the objective function an integer division of a decision variable with a constant number. Is there any efficient way to implent this on gurobi (i use gurobipy)?

関連

• General Constraints

0

• 

  Gurobot (AI-generated response)

  • Gurobi Staff

  2024年02月28日 00:26

  Adding an integer division directly into an objective function can be tricky because most optimization solvers, including Gurobi, are designed to work with linear or quadratic expressions. Integer division introduces non-linearity and discontinuities, which are challenging for these solvers.

  However, there are ways to model this effectively. Here's a strategy you might consider:

  1. Auxiliary Variables and Constraints: Introduce an auxiliary integer variable (say, z) to represent the result of the integer division of your decision variable (say, x) by a constant (say, c). You'll need to add constraints to ensure that z behaves as the integer division of x by c.

  2. Modeling the Division: The integer division x // c can be expressed by ensuring c * z <= x < c * (z + 1). This ensures that z is the greatest integer not greater than x/c.

  3. Integrating into the Objective Function: Once you have z correctly representing the integer division, you can include it in your objective function as required.

  In GurobiPy, this might look something like:

  from gurobipy import Model, GRB
  
  # Assuming you already have your model setup
  model = Model("my_model")
  
  # Decision variables
  x = model.addVar(vtype=GRB.INTEGER, name="x")
  z = model.addVar(vtype=GRB.INTEGER, name="z")
  
  # Constant for division
  c = 10  # Example value
  
  # Constraints for integer division
  model.addConstr(c * z <= x, "div_lower_bound")
  model.addConstr(x < c * (z + 1), "div_upper_bound")
  
  # Objective function
  # Assuming you want to maximize/minimize z or a function involving z
  model.setObjective(z, GRB.MAXIMIZE)  # Or GRB.MINIMIZE as needed
  
  # ... rest of your model setup and optimization call

  Remember, the efficiency of this approach can depend on the size of your problem and the specific context in which it's being used. It's always a good idea to test and tweak the model for performance, especially with non-standard constraints like these.

  0
• 

  Riley Clement

  • Gurobi Staff

  2024年02月28日 01:00

  Hi Nick,

  I'm not 100% the bot response has answered your question.  Please let us know if anything is unclear.

  - Riley

  0

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