ospf

简体中文

English

简体中文

English

Appearance

二元分段线性函数 ​

形式 ​

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

常量 ​

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

额外变量 ​

ut∈[0,1] ：在第 i 个三角形中 AiBi→ 向量的权重。

vt∈[0,1] ：在第 i 个三角形中 AiCi→ 向量的权重。

wt∈{0,1} ：在第 i 个三角形中的判定。

导出符号 ​

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

数学模型 ​

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

其中：

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

推理过程 ​

基本原理 ​

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

代数化基本原理 ​

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

逻辑特性： ​

∀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))))

（二次型）数学模型： ​

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

线性化即可得到前述数学模型。

样例 ​

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)

完整实现请参考：

完整样例请参考：