干貨 | 10分鐘帶你徹底了解column generation（列生成）算法的原理附j(luò)ava代碼

OUTLINE

前言
預(yù)備知識(shí)預(yù)警
什么是column generation
相關(guān)概念科普
Cutting Stock Problem
CG求解Cutting Stock Problem
列生成代碼
reference

00 前言

這幾天勤奮的小編一直在精確算法的快樂(lè)學(xué)習(xí)之中不能自拔。到列生成算法這一塊俐镐，看了好幾天總算把這塊硬骨頭給啃下來(lái)了拌禾。然后發(fā)現(xiàn)網(wǎng)上關(guān)于列生成的教學(xué)資料也不是很多添祸，大部分講的不是那么通俗易懂。所以今天就打算寫(xiě)一寫(xiě)這個(gè)算法拟赊，盡可能寫(xiě)得通俗易懂嚼吞。

01 預(yù)備知識(shí)預(yù)警

由于列生成算法涉及的知識(shí)點(diǎn)非常多，所以在開(kāi)始之前希望讀者必須要具備以下的基礎(chǔ)知識(shí)桌肴，不然就沒(méi)法往下玩了：

線(xiàn)性規(guī)劃以及線(xiàn)性規(guī)劃對(duì)偶問(wèn)題
單純形法原理
原問(wèn)題的影子價(jià)格（shadow price）以及對(duì)偶變量
單純形法非基變量進(jìn)基時(shí)非基變量檢驗(yàn)數(shù)（reduce cost）的計(jì)算

以上內(nèi)容我就不展開(kāi)科普了。如果對(duì)這些概念還有不熟悉的小伙伴琉历，一定要回去搞清楚再往下看哦坠七。

Cutting Stock Problem[1]

講column generation怎么可能少得了Cutting Stock Problem這個(gè)經(jīng)典的問(wèn)題呢！在開(kāi)始之前我們將以這個(gè)問(wèn)題為鋪墊一步一步往下講解旗笔。

我們有以下問(wèn)題灼捂，原紙卷每個(gè)長(zhǎng)為L(zhǎng)=17m，顧客們分別需要25個(gè)3m長(zhǎng)换团，20個(gè)5m長(zhǎng)，18個(gè)7m長(zhǎng)的紙卷宫蛆。那么需要怎樣切割才能使得浪費(fèi)最小呢艘包？

建模

Column Generation Formulation：
對(duì)于一卷紙，可以有很多種切割方案耀盗。

$a_{ij}$ 表示第j種方案里類(lèi)別i的個(gè)數(shù)想虎。
$y_{j}$ 表示第 j 種方案的選擇個(gè)數(shù)。

于是叛拷，我們得到如下模型：
$min (y_1 +...+y_n) \\ a_{11}y_1+...+a_{1n}y_n \ge 25 \\ a_{21}y_1+...+a_{2n}y_n \ge 20 \\ a_{31}y_1+...+a_{3n}y_n \ge 18 \\ y_i \in Z$

從上面的模型中舌厨，所有可行的裁剪方案的總數(shù)為n，我們并不知道這個(gè)值是多少忿薇，也不需要知道裙椭，只需要知道它很大躏哩。并且，隨著一卷紙長(zhǎng)度的不斷增加揉燃，n是爆炸式增長(zhǎng)的扫尺。

總之，可行的裁剪方案非常多炊汤，在上面的模型中我們無(wú)法顯式地把所有裁剪方案給表現(xiàn)出來(lái)正驻。

02 什么是column generation？

2.1 相關(guān)背景

Column generation 是一種用于求解大規(guī)模線(xiàn)性?xún)?yōu)化問(wèn)題的非常高效的算法抢腐。[3]其理論基礎(chǔ)是由Danzig等于1960年提出姑曙。本質(zhì)上而言，列生成算法就是單純形法的一種形式迈倍，是用來(lái)求解線(xiàn)性規(guī)劃問(wèn)題的伤靠。列生成算法已被應(yīng)用于求解如下著名的NP-hard優(yōu)化問(wèn)題：機(jī)組人員調(diào)度問(wèn)題(Crew Assignment Problem)、切割問(wèn)題(Cutting Stock Problem)授瘦、車(chē)輛路徑問(wèn)題(Vehicle Routing Problem)醋界、單資源工廠選址問(wèn)題(The single facility location problem )等。

2.2 larger linear programs

在某些線(xiàn)性?xún)?yōu)化問(wèn)題的模型中,約束的數(shù)目有限提完，但是變量的數(shù)目隨著問(wèn)題規(guī)模的增長(zhǎng)會(huì)爆炸式的增長(zhǎng)形纺，因此不能把所有的變量都顯性的在模型中表達(dá)出來(lái)。

比如剛剛介紹的Cutting Stock Problem的模型徒欣。隨著一卷紙長(zhǎng)度的不斷增加逐样，行的裁剪方案數(shù)量是爆炸式增長(zhǎng)的。并且打肝，可行的裁剪方案非常多脂新，在模型中無(wú)法顯式地把所有裁剪方案給表現(xiàn)出來(lái)。

2.3 column generation

單純型法雖然能保證在數(shù)次迭代后找到最優(yōu)解粗梭，但像Cutting Stock Problem這一類(lèi)的問(wèn)題争便，由于變量太多根本無(wú)法把所有的變量都顯性的在模型中表達(dá)出來(lái)。所以單純形法在這里就無(wú)能為力了断医。

再有滞乙，在用單純形法求解這類(lèi)線(xiàn)性規(guī)劃問(wèn)題時(shí)，基變量(basic variable)只與約束的個(gè)數(shù)相關(guān)鉴嗤，每次迭代只會(huì)有一個(gè)新的非基變量(non-basic variable)進(jìn)基斩启，因此，在整個(gè)求解過(guò)程中其實(shí)只有很少一部分變量會(huì)被涉及到醉锅。

因此兔簇，有人基于單純型法提出了列生成算法。其思路大概如下：[1]

先把原問(wèn)題P_0給restrict到一個(gè)規(guī)模更小（即變量數(shù)比原問(wèn)題少的）的P_1垄琐，在P_1上用單純型法求最優(yōu)解边酒，但是此時(shí)求得的最優(yōu)解只是P_1上的，并不是P_0 的最優(yōu)解此虑。
此時(shí)甚纲，就需要通過(guò)一個(gè)subproblem去check在那些未被考慮的變量中是否有使得reduced cost小于零的？如果有朦前，那么就把這個(gè)變量的相關(guān)系數(shù)列加入到P_1的系數(shù)矩陣中介杆，回到第1步。

經(jīng)過(guò)反復(fù)的迭代韭寸，直到subproblem中的reduced cost rate大于等于零春哨，那么原問(wèn)題P_0就求到了最優(yōu)解。

看算法流程圖會(huì)更加直觀哦：[2]

03 相關(guān)概念科普

剛剛講的內(nèi)容涉及到了幾個(gè)概念恩伺，master problem赴背，linear master problem(LMP)，restricted linear master problem晶渠，subproblem等凰荚，這一節(jié)來(lái)把這幾個(gè)概念給講清楚。還是基于上面的Cutting Stock Problem的模型：
$min (y_1 +...+y_n) \\ a_{11}y_1+...+a_{1n}y_n \ge 25 \\ a_{21}y_1+...+a_{2n}y_n \ge 20 \\ a_{31}y_1+...+a_{3n}y_n \ge 18 \\ y_i \in Z$

3.1 master problem(MP)

對(duì)于一般問(wèn)題而言褒脯，如果要用列生成求解便瑟，一般需要重新建模成set covering model。也就是和上面的Cutting Stock Problem類(lèi)似形式的模型番川。重新建模成set covering model以后的問(wèn)題就是master problem了到涂。在Cutting Stock Problem中由于一開(kāi)始就是建成這種形式，所以其Master Problem就是原模型：
$min (y_1 +...+y_n) \\ a_{11}y_1+...+a_{1n}y_n \ge 25 \\ a_{21}y_1+...+a_{2n}y_n \ge 20 \\ a_{31}y_1+...+a_{3n}y_n \ge 18 \\ y_i \in Z$

3.2 linear master problem(LMP)

Column generation 是一種用于求解大規(guī)模線(xiàn)性?xún)?yōu)化問(wèn)題的颁督。而上面的模型中践啄，決策變量是整數(shù)，因此要用列生成算法的話(huà)沉御，要把整數(shù)變量給線(xiàn)性松弛了屿讽。得到linear master problem：
$min (y_1 +...+y_n) \\ a_{11}y_1+...+a_{1n}y_n \ge 25 \\ a_{21}y_1+...+a_{2n}y_n \ge 20 \\ a_{31}y_1+...+a_{3n}y_n \ge 18 \\ y_i \ge 0$

3.2 restricted linear master problem(RLMP)

把LMP給restrict到一個(gè)規(guī)模更小（即變量數(shù)比原問(wèn)題少的）的就是restricted linear master problem了吠裆。比如可以用啟發(fā)式算法伐谈，在上面的linear master problem找出滿(mǎn)足條件（也就是形成的restricted linear master problem必須要有能滿(mǎn)足LMP所有約束的可行解）的k個(gè)列，得到如下的restricted linear master problem：
$min (y_1+y_2+...+y_k) \\ a_{11}y_1+...+a_{1k}y_k \ge 25\\ a_{21}y_1+...+a_{2k}y_k \ge 20 \\ a_{31}y_1+...+a_{3n}y_n \ge 18 \\ y_i \ge 0$

可以看到硫痰，相比原來(lái)的linear master problem，restricted linear master problem相當(dāng)于把 $y_{k+1}...y_n$ 強(qiáng)制限制為非基變量了窜护。[4]

3.3 subproblem

核能預(yù)警效斑，如果這部分看不懂，請(qǐng)確保預(yù)備知識(shí)過(guò)關(guān)柱徙。如果預(yù)備知識(shí)不過(guò)關(guān)缓屠，請(qǐng)?jiān)谶\(yùn)籌學(xué)老師的陪同下觀看奇昙，謝謝合作！

上面的限制主問(wèn)題求解完成后敌完，我們想使用單純型法進(jìn)行基變量的轉(zhuǎn)換，看看 $y_{k+1}...y_m$ 中，是否有可以轉(zhuǎn)入基變量的列啸盏。還記得怎么找進(jìn)基的非基變量嗎埠通？（不記得就去問(wèn)你們的運(yùn)籌學(xué)老師）。當(dāng)然是通過(guò)非基變量的檢驗(yàn)數(shù)辣晦攒，通過(guò) $\sigma_j = c_j - c_BB^{-1}a_j$ 闽撤，在 $y_{k+1}...y_m$ 中尋找檢驗(yàn)數(shù)最小并且為負(fù)數(shù)的變量，將變量對(duì)應(yīng)的那一列添加到RMP中脯颜。

那么哟旗，在檢驗(yàn)數(shù)的計(jì)算公式中，大家還記得 $c_BB^{-1}$ 是什么嗎栋操？ $c_BB^{-1}$ 有兩重含義：

通過(guò)求解RLMP問(wèn)題得到的影子價(jià)格（shadow price）闸餐。
通過(guò)求解RLMP對(duì)偶問(wèn)題得到的對(duì)偶變量(dual variable)。

所以在開(kāi)始之前小編一直強(qiáng)調(diào)預(yù)備知識(shí)一定要過(guò)關(guān)矾芙。這兩個(gè)含義意味著我們有上面兩種方式得到 $c_BB^{-1}$ 舍沙，不過(guò)我們一般傾向于使用第二種，WHY蠕啄？

雖然通過(guò)單純型法直接求解restricted linear master problem能得到

c_BB^{-1}

场勤。但是restricted linear master problem也可能是一個(gè)變量很多的線(xiàn)性規(guī)劃。為了加快求解速度歼跟，通過(guò)單純型法求restricted linear master problemde的對(duì)偶問(wèn)題（將restricted linear master problem對(duì)偶一下和媳，就能使得變量數(shù)大幅減小，因?yàn)檫@些變量轉(zhuǎn)換成了對(duì)偶問(wèn)題中的限制條件了）哈街，能更快地得到子問(wèn)題想要的

c_BB^{-1}

留瞳。[1]

所以我們總結(jié)一下：
通過(guò)求解RLMP問(wèn)題或者RLMP對(duì)偶問(wèn)題，得到我們想要的 $c_BB^{-1}$ 以后骚秦，subproblem就是通過(guò) $\sigma_j = c_j - c_BB^{-1}a_j$ 這條公式她倘，在 $y_{k+1}...y_m$ 中尋找檢驗(yàn)數(shù)為負(fù)并且最小的變量，將變量對(duì)應(yīng)的那一列添加到RLMP中作箍。

3.4 算法流程圖

通過(guò)上面講了這么多以后硬梁，這里在給出一個(gè)更詳細(xì)的流程圖：[5]

04 CG求解Cutting Stock Problem

通過(guò)上面的問(wèn)題分析和建模以后，我們這一步一步一步來(lái)求解該問(wèn)題胞得，讓大家徹底理解column generation這個(gè)過(guò)程荧止。該過(guò)程模擬需要用到一個(gè)線(xiàn)性求解器，大家還記得小編以前講過(guò)的lpsolve的教程嗎?趕緊去翻一下以前的教程，把lpsolveIDE裝上跃巡，然后跟著小編的腳步一步一步往下走危号。

4.1 restricted linear master problem(RLMP)

前面我們完成了問(wèn)題的建模，得到了Cutting Stock Problem的linear Master Problem∷匦埃現(xiàn)在外莲，我們可以用啟發(fā)式算法找到一個(gè)滿(mǎn)足客戶(hù)需要的初始解：
首先，一個(gè)卷筒有三種切割方案：
方案1：切成5個(gè)3m
方案2：切成2個(gè)6m
方案3：切成2個(gè)7m

很容易得出兔朦，5個(gè)方案1偷线、10個(gè)方案2、8個(gè)方案3烘绽，是能滿(mǎn)足所有客戶(hù)需求的淋昭。即得LMP的一個(gè)RLMP如下：
$min (y_1 +...+y_3) \\ a_{11}y_1+...+a_{13}y_3 \ge 25 \\ a_{21}y_1+...+a_{23}y_3 \ge 20 \\ a_{31}y_1+...+a_{33}y_3 \ge 18 \\ y_i \ge 0$
其中，
$a_{11} = 5,a_{12} = 0, a_{13} = 0 \\ a_{21} = 0,a_{22} = 2, a_{13} = 0 \\ a_{31} = 0,a_{32} = 0, a_{13} = 2 \\$
這三列分別對(duì)應(yīng)著方案1安接、方案2翔忽、方案3。還有一點(diǎn)需要注意的盏檐，對(duì)于每一列歇式，都需要滿(mǎn)足：
$3a_{1j} + 6a_{2j}+ 7a_{3j} \le 16$ ，也就是每一卷紙只有16的長(zhǎng)度胡野，不能超出這個(gè)長(zhǎng)度材失。這個(gè)叫列生成規(guī)則，不同問(wèn)題有不同的規(guī)則約束硫豆。subproblem在尋找某些列或者生成某些列時(shí)龙巨，就是受到列生成規(guī)則的約束的。

4.2 開(kāi)始列生成過(guò)程

iteration 1

RLMP：
$min (y_1 +...+y_3) \\ 5y_1+0y_2+0y_3 \ge 25 \\ 0y_1+2y_2+0y_3 \ge 20 \\ 0y_1+0y_2+2y_3 \ge 18 \\ y_i \ge 0$
將該模型輸入lpsolve熊响，得到對(duì)偶變量如下：

得到 $c_BB^{-1} = [0.2, 0.5, 0.5]$ ≈急穑現(xiàn)在要找一列加入RMP，是哪一列呢汗茄？現(xiàn)在還不知道秸弛，我們暫記為 $\alpha_4 = [a_{14},a_{24},a_{34}]^T$ 。非基變量檢驗(yàn)數(shù) $\sigma_4 = c_4 - c_BB^{-1}\alpha_4 = 1 - 0.2a_{14}-0.5a_{24}-0.5a_{34}$ 洪碳。

subproblem：
$min (1 - 0.2a_{14}-0.5a_{24}-0.5a_{34}) \\ s.t. 3a_{14} + 6a_{24}+ 7a_{34} \le 16 \\ a_{ij} \in Z$
求解結(jié)果得 $\alpha_4 = [1,2,0]^T, \sigma_4= -0.2 < 0$ ,reduced cost 為負(fù)數(shù)递览，因此將 $\alpha_4$ 加入RLMP，開(kāi)始第二輪迭代瞳腌。

iteration 2

RLMP：
$min (y_1 +...+y_3+y_4) \\ 5y_1+0y_2+0y_3 +1y_4\ge 25 \\ 0y_1+2y_2+0y_3+2y_4 \ge 20 \\ 0y_1+0y_2+2y_3+0y_3 \ge 18 \\ y_i \ge 0$
將該模型輸入lpsolve绞铃，得到對(duì)偶變量如下：

得到 $c_BB^{-1} = [0.2, 0.4, 0.5]$ 。現(xiàn)在要找一列加入RLMP嫂侍，是哪一列呢儿捧？現(xiàn)在還不知道冷离，我們暫記為 $\alpha_5 = [a_{15},a_{25},a_{35}]^T$ 。非基變量檢驗(yàn)數(shù) $\sigma_5 = c_5 - c_BB^{-1}\alpha_5 = 1 - 0.2a_{15}-0.4a_{25}-0.5a_{35}$ 纯命。

subproblem：
$min (1 - 0.2a_{15}-0.4a_{25}-0.5a_{35}) \\ s.t. 3a_{15} + 6a_{25}+ 7a_{35} \le16 \\ a_{ij} \in Z$
求解結(jié)果得 $\alpha_5 = [1,1,1]^T, \sigma_5= -0.1 < 0$ ,reduced cost 為負(fù)數(shù)，因此將 $\alpha_5$ 加入RLMP痹栖，開(kāi)始第三輪迭代亿汞。

iteration 3

RMP：
$min (y_1 +...+y_3+y_4+y5) \\ 5y_1+0y_2+0y_3 +1y_4+1y_5\ge 25 \\ 0y_1+2y_2+0y_3+2y_4+1y_5 \ge 20 \\ 0y_1+0y_2+2y_3+0y_3 +1y_5\ge 18 \\ y_i \ge 0$
將該模型輸入lpsolve，得到對(duì)偶變量如下：

得到 $c_BB^{-1} = [0.2, 0.4, 0.4]$ 【景ⅲ現(xiàn)在要找一列加入RLMP疗我，是哪一列呢？現(xiàn)在還不知道南捂，我們暫記為 $\alpha_6 = [a_{16},a_{26},a_{36}]^T$ 吴裤。非基變量檢驗(yàn)數(shù) $\sigma_6 = c_6 - c_BB^{-1}\alpha_6 = 1 - 0.2a_{16}-0.4a_{26}-0.5a_{36}$ 。

subproblem：
$min (1 - 0.2a_{16}-0.4a_{26}-0.5a_{36}) \\ s.t. 3a_{16} + 6a_{26}+ 7a_{36} \le16 \\ a_{ij} \in Z$
求解結(jié)果得 $\alpha_6 = [5,0,0]^T, \sigma_6 = 0$ ,reduced cost 不為負(fù)數(shù)溺健，因此不用將 $\alpha_6$ 加入RLMP麦牺，列生成算法結(jié)束。

最終鞭缭，我們求解最后一次迭代的RLMP：
$min (y_1 +...+y_3+y_4+y_5) \\ 5y_1+0y_2+0y_3 +1y_4+1y_5\ge 25 \\ 0y_1+2y_2+0y_3+2y_4+1y_5 \ge 20 \\ 0y_1+0y_2+2y_3+0y_3 +1y_5\ge 18 \\ y_i \ge 0$

得到RLMP的最優(yōu)解 $y = [1.2, 0,0,1, 18]$ 剖膳，這里因?yàn)榘袽P的整數(shù)決策變量給線(xiàn)性松弛了，求解的是MP問(wèn)題的一個(gè)lower bound岭辣。畢竟列生成是用于求解linear program的吱晒。如果要求解大規(guī)模整數(shù)規(guī)劃問(wèn)題，后面我們會(huì)介紹結(jié)合column generation的branch and price方法沦童。

至此仑濒，我們已經(jīng)完完整整把列生成算法給走了一遍。相信列生成算法的原理已經(jīng)深入各位讀者的心里啦偷遗。

05 列生成代碼

獲取方式

06 reference

[1] 從單純型法到列生成算法, Xijun (Ted) LI
[2] A tutorial on column generation and branch-and-price
for vehicle routing problems, Dominique Feillet
[3] https://en.wikipedia.org/wiki/Column_generation
[4] 運(yùn)籌系列8：Set partitioning問(wèn)題的列生成方法
[5] Column generation algorithms

最后編輯于：2021.07.18 20:37:00

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

禁止轉(zhuǎn)載墩瞳，如需轉(zhuǎn)載請(qǐng)通過(guò)簡(jiǎn)信或評(píng)論聯(lián)系作者。

人面猴
序言：七十年代末鹦肿，一起剝皮案震驚了整個(gè)濱河市矗烛，隨后出現(xiàn)的幾起案子，更是在濱河造成了極大的恐慌箩溃，老刑警劉巖瞭吃，帶你破解...
沈念sama閱讀 217,406評(píng)論 6贊 503
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件，死亡現(xiàn)場(chǎng)離奇詭異涣旨，居然都是意外死亡歪架，警方通過(guò)查閱死者的電腦和手機(jī)，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,732評(píng)論 3贊 393
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門(mén)霹陡，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)和蚪，“玉大人止状，你說(shuō)我怎么就攤上這事≡芘” “怎么了怯疤？”我有些...
開(kāi)封第一講書(shū)人閱讀 163,711評(píng)論 0贊 353
道士緝兇錄：失蹤的賣(mài)姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)催束。經(jīng)常有香客問(wèn)我集峦，道長(zhǎng)，這世上最難降的妖魔是什么抠刺？我笑而不...
開(kāi)封第一講書(shū)人閱讀 58,380評(píng)論 1贊 293
?港島之戀（遺憾婚禮）
正文為了忘掉前任塔淤，我火速辦了婚禮，結(jié)果婚禮上速妖，老公的妹妹穿的比我還像新娘高蜂。我一直安慰自己，他們只是感情好罕容，可當(dāng)我...
茶點(diǎn)故事閱讀 67,432評(píng)論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布备恤。她就那樣靜靜地躺著，像睡著了一般锦秒。火紅的嫁衣襯著肌膚如雪烘跺。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書(shū)人閱讀 51,301評(píng)論 1贊 301
城市分裂傳說(shuō)
那天脂崔，我揣著相機(jī)與錄音滤淳，去河邊找鬼。笑死砌左，一個(gè)胖子當(dāng)著我的面吹牛脖咐，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播汇歹，決...
沈念sama閱讀 40,145評(píng)論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼屁擅，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了产弹？” 一聲冷哼從身側(cè)響起派歌，我...
開(kāi)封第一講書(shū)人閱讀 39,008評(píng)論 0贊 276
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎痰哨，沒(méi)想到半個(gè)月后胶果，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 45,443評(píng)論 1贊 314
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡斤斧，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,649評(píng)論 3贊 334
?白月光啟示錄
正文我和宋清朗相戀三年早抠，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片撬讽。...
茶點(diǎn)故事閱讀 39,795評(píng)論 1贊 347
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡蕊连，死狀恐怖悬垃，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情甘苍，我是刑警寧澤尝蠕，帶...
沈念sama閱讀 35,501評(píng)論 5贊 345
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站载庭，受9級(jí)特大地震影響趟佃，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜昧捷，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,119評(píng)論 3贊 328
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一、第九天我趴在偏房一處隱蔽的房頂上張望罐寨。院中可真熱鬧靡挥，春花似錦、人聲如沸鸯绿。這莊子的主人今日做“春日...
開(kāi)封第一講書(shū)人閱讀 31,731評(píng)論 0贊 22
一樁弒父案，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)瓶蝴。三九已至毒返，卻和暖如春，著一層夾襖步出監(jiān)牢的瞬間舷手，已是汗流浹背拧簸。一陣腳步聲響...
開(kāi)封第一講書(shū)人閱讀 32,865評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留男窟，地道東北人盆赤。一個(gè)月前我還...
沈念sama閱讀 47,899評(píng)論 2贊 370
代替公主和親
正文我出身青樓，卻偏偏與公主長(zhǎng)得像歉眷，于是被迫代替她去往敵國(guó)和親牺六。傳聞我的和親對(duì)象是個(gè)殘疾皇子，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,724評(píng)論 2贊 354