使用pycddlib求解A.x ≤ b定义的多面体极点的疑问

你的构造方式是完全正确的，并非巧合，下面详细解释规则和验证逻辑：

pycddlib的H-表示规则 #

pycddlib通过**半空间表示（H-representation）**定义多面体，每行对应一个约束，格式需满足：
原始约束 A_i·x ≤ b_i 必须转化为 b_i - A_i·x ≥ 0 的形式，对应矩阵行的结构为：
[b_i, -A_i[0], -A_i[1], ..., -A_i[n-1]]
其中n是变量的维度，linear=False表示所有约束都是不等式（无等式约束）。

结合你的例子验证 #

你的约束系统是：

1. x₁ + x₂ ≤ 1 → 转化为 1 - x₁ - x₂ ≥ 0 → 矩阵行：[1, -1, -1]
2. -x₁ ≤ 0 → 转化为 0 + x₁ ≥ 0 → 矩阵行：[0, 1, 0]
3. -x₂ ≤ 0 → 转化为 0 + x₂ ≥ 0 → 矩阵行：[0, 0, 1]

这三行正好对应你构造的矩阵M，完全符合pycddlib的要求。

输出结果解释 #

get_generators()返回的是顶点表示（V-representation），每行第一个元素的含义：

• 1 表示该行对应一个极点（vertex）
• 0 表示对应一条射线（ray）（你的例子中无射线，因为多面体是有界的）

后续元素就是极点的坐标：

• 1 0 0 → 极点 (0, 0)
• 1 1 0 → 极点 (1, 0)
• 1 0 1 → 极点 (0, 1)

和预期结果完全一致。

通用化代码写法 #

为了适配更复杂的任务，建议直接从原始的A和b自动构造矩阵，避免手动计算：

import numpy as np
import cdd

# 原始约束 A·x ≤ b
A = np.array([[1, 1], [-1, 0], [0, -1]])
b = np.array([1, 0, 0])

# 自动构造H-表示矩阵：列拼接b和-A
M = np.hstack([b.reshape(-1, 1), -A])

# 创建cdd矩阵，linear=False表示无等式约束
mat = cdd.Matrix(M, linear=False, number_type="fraction")
poly = cdd.Polyhedron(mat)

# 获取极点并打印
ext = poly.get_generators()
print(ext)

内容的提问来源于stack exchange，提问作者Arseniy Samsonov