MAST 90014针对工业CA第3部分的优化，2021

1考虑一下Land和Doig在其开创性论文中使用的以下问题：

2 s.t.
10.9×1 + 3.6×2-40.8×3 + 43.9y1 + 7.1y2 + y3 = 82.3（2）
−86.8×1 + 32.7×2 + 24.3×3 + 13.8y1 − 12.6y2 + y4 = 77.3（3）
60.9×1 + 68.9×2 + 69.0×3-56.9y1 + 22.5y2 = 86.5（4）

x，x，x∈Z（5）
— 1 2 3 +
y，y，y，y∈R（6）
1 2 3 4 +

（7）
（a）使用以下规则获得完整的分支定界树。对于每个节点，

f•节点选择：深度优先（始终使用分支≤的子对象进行探索

（b）使用以下规则获得完整的分支定界树。 对于每个节点，

•变量选择：始终分支到具有最大索引的分数变量。
•节点选择：节点选择：最佳绑定（始终以最佳方式探索孩子

MAST 90014 Optimisation for Industry CA Part 3, 2021
Question 1
Consider the following problem, used by Land and Doig in their seminal paper:
max 77.9×1 + 76.8×2 + 89.6×3 + 97.1y1 + 31.3y2 (1)
s.t.
10.9×1 + 3.6×2 − 40.8×3 + 43.9y1 + 7.1y2 + y3 = 82.3 (2)
−86.8×1 + 32.7×2 + 24.3×3 + 13.8y1 − 12.6y2 + y4 = 77.3 (3)
60.9×1 + 68.9×2 + 69.0×3 − 56.9y1 + 22.5y2 = 86.5 (4)
x1, x2, x3 ∈ Z+ (5)
y1, y2, y3, y4 ∈ R+ (6)
(7)
(a) obtain the complete branch-and-bound tree using the following rules. For each node,
indicate its number (in order of exploration). Also indicate the branching constraints
and the reason for pruning leaf nodes.
• variable selection: always branch on the fractional variable with smallest index.
• node selection: depth-ﬁrst (always explore ﬁrst the child with the ≤ branching
constraint.

(b) obtain the complete branch-and-bound tree using the following rules. For each node,
indicate its number (in order of exploration). Also indicate the reason for pruning in
leaf nodes.
• variable selection: always branch on the fractional variable with largest index
• node selection: node selection: best-bound (always explore the child with the best
promising bound)

EasyDue™ 支持PayPal, AliPay, WechatPay, Taobao等各种付款方式!

E-mail: easydue@outlook.com  微信:easydue

EasyDue™是一个服务全球中国留学生的专业代写公司