Binarization

Form

$$y=Bin(x)=\{\begin{array}{ll}1,& x\\ \\ 0,& \mathrm{\neg }x\end{array}$$

Discrete

Constants

$$m=max(x)$$

Additional Variables

$y^{\prime }\in \{0,1\}$: logical value of the polynomial.

Basic Formula

$$y=y^{\prime }$$

Mathematical Model

$$\begin{array}{rlrl}\text{s.t.}& m\cdot y^{\prime }& \ge & x\\ \\ & y^{\prime }& \le & x\end{array}$$

That is:

$$y=\{\begin{array}{ll}1,& x\ge 1\\ \\ 0,& x=0\end{array}$$

Continuous (Non-Precise)

Constants

$$m=max(x)$$

Additional Variables

$b\in [0,1]$: normalized value of the polynomial.

$y^{\prime }\in \{0,1\}$: logical value of the polynomial.

Basic Formula

$$y=y^{\prime }$$

Mathematical Model

$$\begin{array}{rlrl}\text{s.t.}& x& =& m\cdot b\\ \\ & y^{\prime }& \ge & b\\ \\ & ϵ\cdot y^{\prime }& \le & b\end{array}$$

That is:

$$y=\{\begin{array}{ll}1,& x\ge ϵ\\ \\ 0,& x=0\end{array}$$

Continuous (Precise)

Basic Formula

$$y=Ulp(x)$$

$Ulp(x)$ can refer to Unit Linear Piecewise Function, using the sampling points $\{(0,0),(p-ϵ,0),(p,1),(max(x),1)\}$.

That is:

$$y=\{\begin{array}{ll}1,& x\ge p\\ \\ 0,& 0\le x<p\end{array}$$

Example

Discrete

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 = UIntVar("x")
x.range.leq(UInt64.two)
val bin = BinaryzationFunction(x, name = "bin")
val solver = ScipLinearSolver()

val model1 = LinearMetaModel()
model1.add(x)
model1.add(bin)
model1.minimize(bin)
val result1 = runBlocking { solver(model1) }
assert(result1.value!!.obj eq Flt64.zero)

val model2 = LinearMetaModel()
model2.add(x)
model2.add(bin)
model2.maximize(bin)
val result2 = runBlocking { solver(model2) }
assert(result2.value!!.obj eq Flt64.one)

val model3 = LinearMetaModel()
model3.add(x)
model3.add(bin)
model3.addConstraint(x eq Flt64.zero)
model3.maximize(bin)
val result3 = runBlocking { solver(model3) }
assert(result3.value!!.obj eq Flt64.zero)

val model4 = LinearMetaModel()
model4.add(x)
model4.add(bin)
model4.addConstraint(x eq Flt64.zero)
model4.minimize(bin)
val result4 = runBlocking { solver(model4) }
assert(result4.value!!.obj eq Flt64.zero)

Continuous

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")
x.range.leq(Flt64.two)
val bin = BinaryzationFunction(
    x,
    name = "bin"
)
val solver = ScipLinearSolver()

val model1 = LinearMetaModel()
model1.add(x)
model1.add(bin)
model1.minimize(bin)
val result1 = runBlocking { solver(model1) }
assert(result1.value!!.obj eq Flt64.zero)

val model2 = LinearMetaModel()
model2.add(x)
model2.add(bin)
model2.maximize(bin)
val result2 = runBlocking { solver(model2) }
assert(result2.value!!.obj eq Flt64.one)

val model3 = LinearMetaModel()
model3.add(x)
model3.add(bin)
model3.addConstraint(x eq Flt64.zero)
model3.maximize(bin)
val result3 = runBlocking { solver(model3) }
assert(result3.value!!.obj eq Flt64.zero)

val model4 = LinearMetaModel()
model4.add(x)
model4.add(bin)
model4.addConstraint(x eq Flt64(0.3))
model4.maximize(bin)
val result4 = runBlocking { solver(model4) }
assert(result4.value!!.obj eq Flt64.one)

Complete implementation reference:

• Kotlin

Complete example reference:

• Kotlin