ospf

English

简体中文

English

简体中文

Appearance

Bivariate Linear Piecewise Function ​

Function Form ​

z=Blp(x,y)=kix+ki′y+bi,x∈[ai,bi],y∈[ai′,bi′]i=0,1,2,…

Constants ​

M=maxt∈T(max(maxx∈R,y∈Rfut(x,y),maxx∈R,y∈Rfvt(x,y)))

Additional Variables ​

ut∈[0,1]: Weight of vector AiBi→ in the i-th triangle.

vt∈[0,1]: Weight of vector AiCi→ in the i-th triangle.

wt∈{0,1}: Indicator variable for the i-th triangle.

Derived Symbol ​

z=∑t∈T(wt⋅zt,0+ut⋅(zt,1−zt,0)+vt⋅(zt,2−zt,0))

Mathematical Model ​

s.t.ut+M⋅(1−wt)≥fut(x,y),∀t∈Tut−M⋅(1−wt)≤fut(x,y),∀t∈Tvt+M⋅(1−wt)≥fvt(x,y),∀t∈Tvt−M⋅(1−wt)≤fvt(x,y),∀t∈T∑t∈Twt=1ut+vt≤wt,∀t∈T

where:

St=12⋅(−yt,1⋅xt,2+yt,0⋅(−xt,1+xt,2)+xt,0⋅(yt,1−yt,2)+xt,1⋅yt,2),∀t∈Tfut(x,y)=12St⋅(yt,0⋅xt,2−xt,0⋅yt,2+(yt,2−yt,0)⋅x+(xt,0−xt,2)⋅y),∀t∈Tfvt(x,y)=12St⋅(xt,0⋅yt,1−yt,0⋅xt,1+(yt,0−yt,1)⋅x+(xt,1−xt,0)⋅y),∀t∈T

Derivation Process ​

Fundamental Principle ​

(P0P→=u⋅P0P1→+v⋅P0P2→)∧(u≥0)∧(v≥0)∧(u+v≤1))⇒(P∈△P0P1P2)(∃t∈T((P∈t)∧(∄t′∈T((t≠t′)∧(P∈t′)))))

Algebraic Formulation of Fundamental Principle ​

St=12⋅(−yt,1⋅xt,2+yt,0⋅(−xt,1+xt,2)+xt,0⋅(yt,1−yt,2)+xt,1⋅yt,2),∀t∈Tfut(x,y)=12St⋅(yt,0⋅xt,2−xt,0⋅yt,2+(yt,2−yt,0)⋅x+(xt,0−xt,2)⋅y),∀t∈Tfvt(x,y)=12St⋅(xt,0⋅yt,1−yt,0⋅xt,1+(yt,0−yt,1)⋅x+(xt,1−xt,0)⋅y),∀t∈T

Logical Properties: ​

∀t∈T(wt∈{0,1})∃t∈T((wt=1)∧(∄t′∈T((t≠t′)∧(wt=1))))∀t∈T((ut∈([0,1]∩R+))∧(vt∈([0,1]∩R+)))∀t∈T(((wt=1)⇒((ut=fut(x,y))∧(vt=fvt(x,y))))∧((wt=0)⇒((ut=0)∧(vt=0))))

(Quadratic) Mathematical Model: ​

s.t.ut=wt⋅fut(x,y),∀t∈Tvt=wt⋅fvt(x,y),∀t∈T∑t∈Twt=1ut+vt≤wt,∀t∈T

Linearization yields the aforementioned mathematical model.

Code Example ​

kotlin
import kotlinx.coroutines.*
import fuookami.ospf.kotlin.utils.math.*
import fuookami.ospf.kotlin.core.frontend.variable.*
import fuookami.ospf.kotlin.core.frontend.expression.polynomial.*
import fuookami.ospf.kotlin.core.frontend.expression.symbol.linear_function.*
import fuookami.ospf.kotlin.core.frontend.inequality.*
import fuookami.ospf.kotlin.core.frontend.model.mechanism.*
import fuookami.ospf.kotlin.core.backend.plugins.scip.*

val x = URealVar("x")
val y = URealVar("y")
x.range.leq(Flt64.two)
y.range.leq(Flt64.two)

val blp = BivariateLinearPiecewiseFunction(
    x = x,
    y = y,
    points = listOf(
        point3(),
        point3(x = Flt64.two),
        point3(y = Flt64.two),
        point3(x = Flt64.two, y = Flt64.two),
        point3(x = Flt64.one, y = Flt64.one, z = Flt64.one)
    ),
    name = "z"
)

val model = LinearMetaModel()
model.add(x)
model.add(y)
model.add(blp)
model.maximize(blp)

val solver = ScipLinearSolver()
val result = runBlocking { solver(model) }
assert(result.value!!.solution[0] eq Flt64.one)
assert(result.value!!.solution[1] eq Flt64.one)

Complete Implementation Reference:

Complete Example Reference: