Integer division in integer programming
Answered
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)?
-
-
Gurobi Staff
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:
-
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 thatzbehaves as the integer division ofxbyc. -
Modeling the Division: The integer division
x // ccan be expressed by ensuringc * z <= x < c * (z + 1). This ensures thatzis the greatest integer not greater thanx/c. -
Integrating into the Objective Function: Once you have
zcorrectly 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 callRemember, 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 -
-
-
Hi Nick,
I'm not 100% the bot response has answered your question. Please let us know if anything is unclear.
- Riley
0 -
Please sign in to leave a comment.
Comments
2 comments