-
Notifications
You must be signed in to change notification settings - Fork 88
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Improve Example Code Readability #340
Comments
Another example, Resource Constrained Project Scheduling. I have to say, I think it is a huge improvement in showing how the solution works. The expressions used to setup the constraints read far more clearly than the code sample on the examples page. Just compare: # Constraint: resource usage
for res in RESOURCES:
for t in range(PLANNING_HORIZON):
total_usage = mip.xsum(
job.data.resource_usage.get(res, 0) * job.starts_at[s]
for job in JOBS.values()
for s in job.possible_start_times(t) if s >= 0
)
mip_model.add_constr( total_usage <= res.capacity )
# Constraint: job dependencies
successors: dict[Job, list[Job]] = {
job : [ suc for suc in JOBS.values() if job.data in suc.data.dependencies ]
for job in JOBS.values()
}
for job, suc_list in successors.items():
for suc in suc_list:
mip_model.add_constr( job.completed_time <= suc.start_time )
# Objective: minimize the time at which all jobs are complete
all_done = Event(mip_model, 'all_done')
for final_job in (JOBS[8], JOBS[9], JOBS[10]):
mip_model.add_constr( final_job.completed_time <= all_done.time )
mip_model.objective = mip.minimize( all_done.time ) with model.objective = xsum(t * x[n + 1][t] for t in T)
for j in J:
model += xsum(x[j][t] for t in T) == 1
for (r, t) in product(R, T):
model += (
xsum(u[j][r] * x[j][t2] for j in J for t2 in range(max(0, t - p[j] + 1), t + 1))
<= c[r])
for (j, s) in S:
model += xsum(t * x[s][t] - t * x[j][t] for t in T) >= p[j] |
I like these modifications to the plant location example, it makes the examples more pythonic.
# possible plants
@dataclass(frozen=True)
class CandidateSite:
location: tuple[float, float]
max_size: float to @dataclass(frozen=True)
class CandidateSite:
"Potential factory locations"
location: tuple[float, float]
max_capacity: float
class LinearApprox:
"Approximate function by piecewise linear function"
def __init__(self, func: Callable[[float], float], pts: int):
self.func = func
self.pts = pts
@staticmethod
def _linspace(minv: float, maxv: float, pts: int) -> list[float]:
return [ minv + (maxv - minv)*(n / (pts-1)) for n in range(pts) ]
@staticmethod
def _range_of_linexpr(expr: mip.LinExpr | mip.Var) -> tuple[float, float]:
if type(expr) == mip.Var:
return (expr.lb, expr.ub)
lb = expr.const + sum(
factor * (variable.lb if factor >= 0 else variable.ub)
for variable, factor in expr.expr.items()
)
ub = expr.const + sum(
factor * (variable.ub if factor >= 0 else variable.lb)
for variable, factor in expr.expr.items()
)
return (lb, ub)
def __call__(self, x: mip.LinExpr | mip.Var) -> mip.LinExpr:
"Approximate function at the given value. Adds required constraints for each call"
model = x.model
x_min, x_max = self._range_of_linexpr(x)
x_pts = self._linspace(x_min, x_max, self.pts)
# non-linear function values for points in v
y_pts = [ self.func(x) for x in x_pts ]
# w variables - interpolation weights that add to 1, at most two can be non-zero
w_vars = [ model.add_var(lb=0, ub=1) for _ in range(len(x_pts)) ]
model.add_constr( mip.xsum(w_vars) == 1 ) # convexification
model.add_sos([ (w, k) for w, k in zip(w_vars, x_pts) ], sos_type=2)
# linear interpolate in each range to create function input and output expressions
model.add_constr(mip.xsum(w * x for w, x in zip(w_vars, x_pts)) == x)
return mip.xsum(w * y for w, y in zip(w_vars, y_pts)) which simplifies class Factory:
def __init__(self, model: mip.Model, site: CandidateSite):
self.site = site
# create a variable to decide how big to build each plant
# zero size means the plant won't be built
self.capacity = model.add_var(lb = 0, ub = site.max_capacity)
self.build_cost = self.cost_approx(self.capacity)
@staticmethod
def _build_cost(capacity: float) -> float:
"Costs to build a factory with capacity `capacity`; nonlinear function"
return 1520 * math.log(capacity) if capacity > 0 else 0
cost_approx = LinearApprox(_build_cost.__func__, pts = 6) |
@mwerezak Feel free to add a PR. I would add this as a separate examples |
Maybe this is because I'm coming from more of a software engineering background than an operations research background, but I find the code examples in the documentation to be very dense and hard to read.
I like the examples, there are some interesting problems there and the code samples do show you how to use the
mip
package to get solutions to them.However, if you put yourself in the shoes of someone who is evaluating
mip
and trying to imagine how it could be integrated into an actual production system, the code examples fall pretty short.I figure this is a pretty low-priority issue, but I thought I should at least bring up the topic and provide an example of how the code samples could be improved.
I've re-written the Plant Location with Non-Linear Costs example as a way of showing what could be possible. If you're interested, please compare my re-written version with the original one. I believe my version is much more readable and would give a reader who is unfamiliar with
mip
a better sense of how it could be integrated into a larger system.The text was updated successfully, but these errors were encountered: