Piecewise-linear curves
A fuel cost that rises in steps, an efficiency that changes with load, and a
revenue that saturates are each a curve through a list of points.
piecewise relates an expression y to an expression x through such
points. x is on the curve. sign compares y with the curve: == sets
y to the curve, >= bounds y below by it and <= bounds y above by it.
The points are two parameters, x_points and y_points. Each is over some
or all of the sets of x and over one breakpoint set. The declaration
generates the variables and the constraints of its method. Each generated
name begins with the declaration's name.
A cost curve that is not convex
method="incremental" is exact for breakpoints that are strictly increasing
or strictly decreasing. It adds one continuous variable and one integer
variable per segment.
import numpy as np
from nimopt import Model, Param, Set, Sum
G = Set("G", np.array(["a", "b"]))
B = Set("B", np.array(["b0", "b1", "b2", "b3"]))
power = Param.from_dense("power", (G, B), [[0, 10, 20, 30], [0, 10, 20, 30]])
cost = Param.from_dense("cost", (G, B), [[0, 5, 30, 35], [0, 20, 30, 40]])
m = Model("curve")
p = m.var("p", (G,))
c = m.var("c", (G,))
m.constraint("demand", Sum(G, p[G]) == 25.0)
m.piecewise(
"fuel",
x=p[G],
x_points=power[G, B],
y=c[G],
y_points=cost[G, B],
sign=">=",
method="incremental",
)
m.set_objective(Sum(G, c[G]))
s = m.solve()
print(s.objective)
print(s.primal("p").to_dense())
print(list(m.variables))
print(list(m.constraints))
Output
30.0
[10. 15.]
['p', 'c', 'fuel_fill', 'fuel_order']
['demand', 'fuel_x', 'fuel_y', 'fuel_order_bound', 'fuel_fill_order', 'fuel_order_link']
The generated variables and constraints are declarations of the model.
primal, dual, row and explain read them by their names.
x and y are expressions. p[G] + 5.0 is on the curve five units above
p, and the incremental method reads that constant. The tangent method
multiplies x by the slope of each segment, and a constant in x raises
ValueError. Subtract it from x_points instead.
A convex curve
method="tangent" adds no variable. It adds one row per segment, and two
rows that keep x between the first and the last breakpoint. The rows
describe the curve exactly when the points are convex under >=, or
concave under <=.
import numpy as np
from nimopt import Model, Param, Set, Sum
G = Set("G", np.array(["a"]))
B = Set("B", np.array(["b0", "b1", "b2"]))
power = Param.from_dense("power", (G, B), [[0, 10, 20]])
cost = Param.from_dense("cost", (G, B), [[0, 10, 30]])
m = Model("convex")
p = m.var("p", (G,))
c = m.var("c", (G,))
m.constraint("demand", Sum(G, p[G]) == 15.0)
m.piecewise("fuel", p[G], power[G, B], c[G], cost[G, B], ">=", "tangent")
m.set_objective(Sum(G, c[G]))
s = m.solve()
print(s.objective)
print(m.constraints["fuel_tangent"])
Output
20.0
Constraint('fuel_tangent', ('G', 'fuel_segment'), 2 rows, 4 coefficients)
Points that are not convex under >= raise ValueError and identify the
first entity at fault. The tangent rows of such points describe a different
curve.
import numpy as np
from nimopt import Model, Param, Set
G = Set("G", np.array(["a"]))
B = Set("B", np.array(["b0", "b1", "b2"]))
power = Param.from_dense("power", (G, B), [[0, 10, 20]])
cost = Param.from_dense("cost", (G, B), [[0, 20, 30]])
m = Model("concave")
p = m.var("p", (G,))
c = m.var("c", (G,))
m.piecewise("fuel", p[G], power[G, B], c[G], cost[G, B], ">=", "tangent")
Raises ValueError
ValueError: piecewise 'fuel' has points that are not convex, required by sign '>=' at {'G': 'a'}; use method 'incremental'
The method from the data
method="auto" generates the tangent rows where they describe the curve
exactly: the sign is not ==, no active is given, x has no constant and
the points of every entity are convex under >= or concave under <=.
Otherwise it generates the incremental declarations. formulation reports
the method the model generated.
import numpy as np
from nimopt import Model, Param, Set, Sum
G = Set("G", np.array(["a"]))
B = Set("B", np.array(["b0", "b1", "b2"]))
power = Param.from_dense("power", (G, B), [[0, 10, 20]])
for values in ([0, 10, 30], [0, 20, 30]):
cost = Param.from_dense("cost", (G, B), [values])
m = Model("auto")
p = m.var("p", (G,))
c = m.var("c", (G,))
m.constraint("demand", Sum(G, p[G]) == 15.0)
fuel = m.piecewise("fuel", p[G], power[G, B], c[G], cost[G, B], ">=", "auto")
m.set_objective(Sum(G, c[G]))
print(fuel.formulation, m.solve().objective)
Output
tangent 20.0
incremental 25.0
One curve for every entity
x_points and y_points are over the breakpoint set and over as many of the
sets of x as the curves differ along. Points over the breakpoint set alone
give every entity the same curve.
Entities with fewer breakpoints
A parameter built from a table has entries only where the table lists
them. An entity with fewer breakpoints lists its first ones, and the rest
are absent. An entity with no breakpoint has no generated rows and no
generated columns. Its x and y are not related by the declaration.
import numpy as np
from nimopt import Model, Param, Set, Sum
G = Set("G", np.array(["a", "b", "c"]))
B = Set("B", np.array(["b0", "b1", "b2"]))
labels = {
"G": np.array(["a", "a", "a", "b", "b"]),
"B": np.array(["b0", "b1", "b2", "b0", "b1"]),
}
power = Param.from_long("power", (G, B), labels, [0.0, 10.0, 20.0, 0.0, 15.0])
cost = Param.from_long("cost", (G, B), labels, [0.0, 10.0, 30.0, 0.0, 30.0])
m = Model("short")
p = m.var("p", (G,))
c = m.var("c", (G,))
m.piecewise("fuel", p[G], power[G, B], c[G], cost[G, B], ">=", "incremental")
print(m.variables["fuel_fill"].n_columns)
print(m.constraints["fuel_x"].n_rows)
Output
3
2
A breakpoint absent before a present one raises ValueError. A table
with an entity of one breakpoint raises ValueError.
A curve that a binary variable switches off
active= takes a binary variable over the sets of x, or a sum of them.
Where it is 1, x is on the curve. Where it is 0, x is 0 and y is
compared with 0. The curve then starts at its first breakpoint, and a first
breakpoint above 0 is a minimum output. active= is supported by
method="incremental" only. A variable with bounds outside 0 and 1 and a
scaled variable raise ValueError.
A continuous variable raises ValueError under the default. A value between
0 and 1 scales every breakpoint, so the curve is met at a fraction of its
first breakpoint and at a fraction of its cost. relaxed=True accepts that
variable and declares the scaled curve, which is the linear relaxation of
the switch. relaxed=True with no active= raises ValueError.
import numpy as np
from nimopt import Model, Param, Set, Sum
G = Set("G", np.array(["a"]))
T = Set("T", np.array(["t0", "t1"]))
B = Set("B", np.array(["b0", "b1", "b2"]))
power = Param.from_dense("power", (G, B), [[10, 20, 30]])
cost = Param.from_dense("cost", (G, B), [[10, 15, 30]])
demand = Param.from_dense("demand", (T,), [5.0, 25.0])
m = Model("committed")
p = m.var("p", (G, T))
c = m.var("c", (G, T))
on = m.var("on", (G, T), upper=1.0, integer=True)
spot = m.var("spot", (T,))
m.constraint("balance", Sum(G, p[G, T]) + spot[T] == demand[T])
m.piecewise(
"fuel",
x=p[G, T],
x_points=power[G, B],
y=c[G, T],
y_points=cost[G, B],
sign=">=",
method="incremental",
active=on[G, T],
)
m.set_objective(Sum(G, T, c[G, T]) + 1.2 * Sum(T, spot[T]) + 2.0 * Sum(G, T, on[G, T]))
s = m.solve()
print(s.objective)
print(s.primal("on").to_dense())
print(s.primal("p").to_dense())
Output
29.0
[[0. 1.]]
[[ 0. 20.]]
In t0 the demand of 5 is below the minimum output of 10, and the unit is
off.
A declaration over some of the entities
where restricts a declaration to some entities of its breakpoints. It is
a parameter, a tuple of sets or a domain over the sets of x_points other
than the breakpoint set, the form of where on Model.constraint. The
breakpoint checks, the generated columns and the generated rows cover the
entities at its coordinates. x, y and active are compared at those
coordinates only.
Two declarations can share the breakpoints and split the entities. In the
example, a has a status variable and points that are not convex, b has
convex points, and c has no curve. on declares the curve of a with the
incremental method and active. free declares the curve of b with the
tangent method. A linear term prices the output of c. The variable fuel
is declared over the entities with a curve, and p over every entity.
import numpy as np
from nimopt import Model, Param, Set, Sum, subset
G = Set("G", np.array(["a", "b", "c"]))
T = Set("T", np.array(["t0", "t1"]))
B = Set("B", np.array(["b0", "b1", "b2"]))
points = {
"G": np.array(["a", "a", "a", "b", "b", "b"]),
"B": np.array(["b0", "b1", "b2", "b0", "b1", "b2"]),
}
power = Param.from_long("power", (G, B), points, [10.0, 20.0, 30.0, 0.0, 10.0, 20.0])
cost = Param.from_long("cost", (G, B), points, [10.0, 25.0, 30.0, 0.0, 10.0, 30.0])
committed = Param.from_long("committed", (G,), {"G": np.array(["a"])}, [1.0])
flexible = Param.from_long("flexible", (G,), {"G": np.array(["b"])}, [1.0])
price = Param.from_long("price", (G,), {"G": np.array(["c"])}, [3.0])
demand = Param.from_dense("demand", (T,), [5.0, 25.0])
curves = subset(
(G, T),
{"G": np.array(["a", "a", "b", "b"]), "T": np.array(["t0", "t1", "t0", "t1"])},
)
status = subset((G, T), {"G": np.array(["a", "a"]), "T": np.array(["t0", "t1"])})
m = Model("split")
p = m.var("p", (G, T))
fuel = m.var("fuel", (G, T), subset=curves)
u = m.var("u", (G, T), subset=status, upper=1.0, integer=True)
m.constraint("balance", Sum(G, p[G, T]) == demand[T])
m.piecewise(
"on",
p[G, T],
power[G, B],
fuel[G, T],
cost[G, B],
">=",
"incremental",
active=u[G, T],
where=committed,
)
m.piecewise(
"free",
p[G, T],
power[G, B],
fuel[G, T],
cost[G, B],
">=",
"tangent",
where=flexible,
)
m.set_objective(
Sum(G, T, fuel[G, T]) + Sum(G, T, price[G] * p[G, T]) + 2.0 * Sum(G, T, u[G, T])
)
s = m.solve()
print(s.objective)
print(m.variables["on_fill"].n_columns, m.constraints["free_tangent"].n_rows)
Output
34.5
4 4
on_fill has one column per segment of a and timestep. free_tangent
has one row per segment of b and timestep.
Saving a piecewise declaration
A model file of version 4 contains the declaration under piecewise. The
generated variables, constraints and parameters are not written. Loading
the file generates them again.
from nimopt import Definition, Sum, dumps
d = Definition("curve", sense="min")
G, B = d.set("G"), d.set("B")
power, cost = d.param("power", (G, B)), d.param("cost", (G, B))
p = d.var("p", (G,))
c = d.var("c", (G,))
d.constraint("demand", Sum(G, p[G]) == 25.0)
d.piecewise("fuel", p[G], power[G, B], c[G], cost[G, B], ">=", "incremental")
d.set_objective(Sum(G, c[G]))
print(dumps(d))
Output
version: 4
name: curve
sense: min
sets: [G, B]
parameters:
power: [G, B]
cost: [G, B]
variables:
p:
sets: [G]
c:
sets: [G]
constraints:
demand:
relation: Sum(G, p[G]) == 25
piecewise:
fuel:
x: p[G]
x_points: power[G, B]
y: c[G]
y_points: cost[G, B]
sign: '>='
method: incremental
objective: Sum(G, c[G])
version=3 writes a model in the format a reader of version 3 accepts. The
generated declarations are written in place of the declaration, and the
breakpoints are not written. A model loaded from that file contains the
same rows and no piecewise declaration. A definition has no data to
generate the rows from, and writing it as version 3 raises ValueError.
import numpy as np
from nimopt import Model, Param, Set, Sum, dumps
G = Set("G", np.array(["a"]))
B = Set("B", np.array(["b0", "b1"]))
power = Param.from_dense("power", (G, B), [[0, 10]])
cost = Param.from_dense("cost", (G, B), [[0, 20]])
m = Model("line")
p = m.var("p", (G,))
c = m.var("c", (G,))
m.piecewise("fuel", p[G], power[G, B], c[G], cost[G, B], ">=", "tangent")
print(dumps(m, version=3))
Output
version: 3
name: line
sense: min
sets: [G, fuel_segment]
parameters:
fuel_slope: [G, fuel_segment]
fuel_intercept: [G, fuel_segment]
fuel_x_low: [G]
fuel_x_high: [G]
variables:
p:
sets: [G]
c:
sets: [G]
constraints:
fuel_tangent:
relation: c[G] - fuel_slope[G, fuel_segment] * p[G] >= fuel_intercept[G, fuel_segment]
fuel_x_min:
relation: p[G] >= fuel_x_low[G]
fuel_x_max:
relation: p[G] <= fuel_x_high[G]