How to represent sums of piecewise quadratic functions for efficient optimisation?
I'm trying to implement a decision procedure for finding solutions to a scheduling problem; this involves computing the point in time which is under the most contention. Each task to be scheduled has a continuous compactly supported piecewise linear distribution of possible time allocations; the total contention at any time is then a certain sum of pairwise products of these individual piecewise linear distributions (this is the JointHeight criticality estimate, see [1]). As a consequence I am interested in the following:
Question: How can one represent sums of continuous compactly supported piecewise quadratic functions, in a way which affords efficient implementations of:
* adding/removing/modifying a summand,
* finding the maximum.
As <PERSON> points out, if a summand that is added/removed/modified spans the whole domain of support of the sum, then it seems inevitable to need to traverse the whole thing. However, when that domain is rather smaller, I'd hope to be able to efficiently update the whole sum without incurring an $\textrm{O}(#\textrm{Tasks})$ cost; I should only need to update the control points that overlap the domain of the modified task.
After making each search decision, constraint solving takes place, resulting in the modification of the availabilities of certain tasks. 143
My goal is to be able to efficiently update the above representation with these modifications, so that one can efficiently recompute the new time which is under maximum contention after these updates.
Now, a sum of continuous compactly supported piecewise quadratic functions is itself continuous, compactly supported and piecewise quadratic. Once one has an explicit piecewise quadratic expression, it is straightforward to compute the maximum. However I haven't figured out an implementation which would allow me to efficiently recompute the control points when adding/removing/modifying a summand.
A point of comparison is the PiecewiseExpand function from Mathematica. PiecewiseExpand can take a sum of piecewise functions and return an explicit piecewise expression, with the minimal number of control points. So I'd be interested in knowing how such a function is implemented.
[1] Beyond Contention: Extending Texture-Based Scheduling Heuristics (1997, AAAI'97/IAAI'97).
<PERSON>, <PERSON>, <PERSON>, <PERSON> 143