# 线性化方法

### 乘积式

多个0-1变量相乘 $$x\_{1}x\_{2}..x\_{n}$$ 等同于

$$
\begin{aligned}
& y \leq x\_{i} & \forall i = 1,...,n \\
& y \geq \sum\_{i=1}^{n}x\_{i} - (n - 1)\\
& x\_{i},y \in{0,1} & \forall i = 1,...,n
\end{aligned}
$$

若 $$x\_{1} \in {0,1}$$, $$x\_{2} \in \[0,u]$$. 则 $$x\_{1}x\_{2}$$ 等同于

$$
\begin{aligned}
& y \leq ux\_{1} \\
& y \leq x\_{2}\\
& y \geq x\_{2} - u(1-x\_{1})\\
& x\_{1} \in {0,1}, x\_{2} \in \[0,u], y \in \[0,u]
\end{aligned}
$$

若 $$x\_{1} \in {0,1}$$, $$x\_{2} \in \[l,u]$$. 则 $$x\_{1}x\_{2}$$ 等同于

$$
\begin{aligned}
& y \leq x\_{2}\\
& y \geq x\_{2} - u(1-x\_{1})\\
& lx\_{1} \leq y \leq ux\_{1}\\
& x\_{1} \in {0,1}, x\_{2} \in \[l,u], y \in \[l,u]
\end{aligned}
$$

对于两个连续变量相乘的情况是无法进行等价线性化的, 只能进行近似. 近似的常用方法是 [McCormick Envelope](https://optimization.cbe.cornell.edu/index.php?title=McCormick_envelopes)

***

### 取整

等式 $$\lceil \frac{x}{Q} \rceil$$ ($$x$$ 为非负连续变量, $$y$$ 是非负整数变量, $$Q$$ 为任意整数) 等同于

$$
\begin{aligned}
min \quad & y \\
s.t \quad & y \geq \frac{x}{Q}\\
\quad & y - 1 \leq \frac{x}{Q}
\end{aligned}
$$

***

### 绝对值

对于约束 $$z = |x|$$, 其中 $$x$$ 为任意类型的决策变量, $$z$$ 为非负决策变量. 假设 $$|x| \leq M$$, 我们引入辅助决策变量 $$x\_{p} \geq 0$$, $$x\_{n} \geq 0$$, $$y \in {0,1}$$, $$x\_{p}$$ 和 $$x\_{n}$$ 分别表示 $$x$$ 为正数和负数时的绝对值, $$y$$ 表示 $$x$$ 的正负性 (若 $$x\geq 0$$, 则 $$y=1$$; 否则 $$y=0$$). 这时原约束等同于

$$
\begin{aligned}
& z = x\_{p} + x\_{n}\\
& x = x\_{p} - x\_{n}\\
& x\_{p} \leq My\\
& x\_{n} \leq M(1-y)\\
& y\in{0,1}, z,x\_{p},x\_{n} \geq 0
\end{aligned}
$$

***

### $$min/max$$ 函数

考虑约束 $$y = max{x\_{1}, x\_{2}}$$, 其中 $$y, x\_{1}, x\_{2}$$ 均为决策变量. 该约束等同于

$$
\begin{aligned}
min \quad & y \\
s.t \quad & y \geq x\_{1}\\
\quad & y \geq x\_{2}
\end{aligned}
$$

对于约束 $$y = min{x\_{1}, x\_{2}}$$, 其中 $$y, x\_{1}, x\_{2}$$ 均为决策变量. 该约束等同于

$$
\begin{aligned}
max \quad & y \\
s.t \quad & y \leq x\_{1}\\
\quad & y \leq x\_{2}
\end{aligned}
$$

***

### 分式函数

***

### 分段线性函数

考虑分段线性函数 $$f(x)$$, 假设该函数有 $$N$$ 个区间: 

定义域 ($$x$$ 轴) 被分为 $$\[a\_{i}, a\_{i+1}), i = 0,1,...,N-2$$ 和 $$\[a\_{N-1}, a\_{N}]$$

值域被 ($$y$$ 轴) 分为 $$\[b\_{i}, b\_{i+1}), i = 0,1,...,N-2$$ 和 $$\[b\_{N-1}, b\_{N}]$$

我们可以引入一组辅助变量 $$x\_{j} \in {0,1} (j = 1,2,...,N)$$ 来表示 $$x$$ 落在哪个定义域区间, 一组辅助变量 $$\alpha\_{j} (j = 0, 1,...,N)$$ 来表示 $$x$$ 的取值在所处区间的具体位置

$$
\begin{aligned}
\quad & x = \sum\_{j=0}^{N} \alpha\_{j} a\_{j} \\
\quad & y = \sum\_{j=0}^{N} \alpha\_{j} b\_{j} \\
\quad & \sum\_{j=0}^{N} \alpha\_{j} = 1 \\
\quad & \sum\_{j=1}^{N} x\_{j} = 1 \\
\quad & \alpha\_{0} - x\_{1} \leq 0 \\
\quad & \alpha\_{j-1} - (x\_{j-1} + x\_{j}) \leq 0 & j = 1,...,N-1 \\
\quad & \alpha\_{N} - x\_{N} \leq 0 \\
\quad & x\_{j} \in {0, 1} & j = 1,...,N \\
\quad & 0 \leq \alpha\_{j} \leq 1 & j = 0,...,N
\end{aligned}
$$


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yutians-organization.gitbook.io/yun-chou-xue-he-you-hua-dao-lun/xian-xing-gui-hua-wen-ti/xian-xing-hua-fang-fa.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.