Open mwerezak opened 1 year ago
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. Recommended changes (would have prefered to comment inline, but don't know how):
Change size to capacity as it better describes the purpose
Some of your comments would perfectly serve as class or method descriptions, so they would be available as tooltips during coding Change
# 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
Moving a linear approximation into an own class increases reusability, but would recommend to make the behaviour more natural by making it callable (IMO this should be a class provided by python-mip):
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 Factory
to
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.