Cost functions

[tpaviot]

For a Task, the current definition of the cost_per_period is very poor and does not cover all situations of industrial cases. Indeed, cost functions may depend on time (for example, a cost quadratic function of time). It should be possible to define such functions and run the scheduler/optimizer on top of it.

The z3 solver is able to deal with Real numbers and nonlinear expressions. But none of the exp/sin/cos etc. functions, only polynomials. The best way to go is to define a cost function using only integer numbers. I suggest interpolating any function of one real variable using linear segments defined only with integer numbers. I contributed related code to https://github.com/tpaviot/LinearIntegerInterpolation. It is a very first draft.

ping @dreinon

[dreinon]

What about taylor series?

[tpaviot]

Taylor series gives you a polynomial approximation around a single point. Here, I rather need an interpolation over a wide range.

[dreinon]

True

[dreinon]

Do you know spline or kringing iterpolation? Those may give a better function approximation. Although, we may not want a better whole function approximation but rather an easier-to-compute approximation which gives the right results for costs of integers, and that's the point of the linear interpolation, am I right?

[tpaviot]

Right, I don't care about the interpolation quality. Although I should, however, compute the error of the interpolation (I guess least square error is a good indicator). I want my interpolation function:

• to work only with integers (to be able to use integer linear constraintsin z3)
• ideally with the smallest number of interpolation segmets (because, in z3, the function will be approximated by a set of If x in interval then the value is constraints). So ideally no more than 3 or 4 intervals for the interpolate a function; It might not be reachable for periodic functions

[tpaviot]

I don't know the kringing interpolation

[tpaviot]

Maybe we can start with implementing a cost function as a linear function on the interval [0, horizon], and see later for interpolating more complex functions, for example:

ress1=Worker('Worker1', cost=CostFunction(cost_ress_1 = lambda t : 2*t + 10))
ress2=Worker('Worker2', cost=CostPerPeriod(5))

The CostFunction and CostPerPeriod would inherit from a _Cost base class.

What do you think?

[tpaviot]

Note:

ress2=Worker('Worker2', cost=CostFunction(cost_ress_2 = lambda t : 5))

This would be equivalent, but less readable

[tpaviot]

The advantage with constant or linear cost functions is that the total cost over a given period can be computed from a very simple area computation (rectangle if constant function, trapeze if linear)

[dreinon]

cost_ress_1 

I don't understand why naming the lambda function, doesn't it work like this: ress1=Worker('Worker1', cost=CostFunction(lambda t : 2*t + 10)) ??

[dreinon]

Also, what about accepting cost as Union[int, CostFunction]? Then, if cost is int, instancing CostPerPeriod(5) inside the function.

This would give a more readable approach, right?

[tpaviot]

Don't what is more readable. If the user is forced to use a Cost instance whenever he wants to assign cost to a resource, it might be better. Indeed I believe that an explicit class name is better than implicit typing. IMO

ress2=Worker('Worker2', cost=ConstantCostPerPeriod(5))

is more readable, at some point, than

ress2=Worker('Worker2', cost=5)

because, in the latter, we don't really know what this 5 refers to.

[tpaviot]

yes, you're right, no need to name the lambda function

[dreinon]

Right. I agree now with that approach.

[tpaviot]

Ok, I decided to start simple. I implemented ConstantCostPerPeriod and what I called PolynomialCostFunction. There are a some related tests

[tpaviot]

The first draft is in the master branch. Issue closed, further issues will need another entry.