拓冰网站定制 
科学计算【免费下载链接】cvxpyA Python-embedded modeling language for convex optimization problems.项目地址https://gitcode.com/gh_mirrors/cv/cvxpy点击查看免费下载混合整数二次规划Mixed-Integer Quadratic ProgramMIQP是凸优化与整数规划的交叉领域目标函数为半正定二次型而优化变量被约束为整数值。本文以 CVXPY 官方示例 mixed_integer_quadratic_program.rst 为骨架系统讲解 MIQP 的数学形式、整数变量的建模方式、混合整数求解器的选择与安装并结合仓库源码给出一个可完整运行的混合整数最小二乘示例。读完本文你将掌握用 CVXPY 声明整数变量、求解 MIQP 问题、解读求解结果以及在不同求解器SCIP、HiGHS、GLPK_MI、CBC 及商业求解器之间做出正确选择。MIQP 的数学形式混合整数二次规划的标准形式为$$ \begin{array}{ll} \mbox{minimize} x^T Q x q^T x r \ \mbox{subject to} x \in \mathcal{C}\ x \in \mathbf{Z}^n, \end{array} $$其中$x \in \mathbf{Z}^n$ 是优化变量$\mathbf{Z}^n$ 表示所有分量为整数的 $n$ 维向量集合$Q \in \mathbf{S}_^n$ 是 $n \times n$ 对称半正定矩阵保证目标函数为凸二次型$q \in \mathbf{R}^n$ 与 $r \in \mathbf{R}$ 分别是线性项系数与常数项连同 $Q$ 一起构成问题数据$\mathcal{C}$ 是某个凸集用于承载等式、不等式等附加约束。需要特别指出的是MIQP 与普通 QP 的本质区别在于整数约束 $x \in \mathbf{Z}^n$。这一约束使可行域不再连续问题整体属于非凸的混合整数优化范畴因而无法用内点法等连续优化算法直接求解必须依赖专门的混合整数求解器MIP solver。一个典型实例混合整数最小二乘MIQP 最常见也最具代表性的特例是混合整数最小二乘mixed-integer least squares其形式为$$ \begin{array}{ll} \mbox{minimize} |Ax-b|_2^2 \ \mbox{subject to} x \in \mathbf{Z}^n, \end{array} $$其中 $x \in \mathbf{Z}^n$ 是优化变量$A \in \mathbf{R}^{m \times n}$ 与 $b \in \mathbf{R}^{m}$ 是问题数据。该问题的最优解 $x^{\star}$ 是一个使残差平方和 $|Ax-b|_2^2$ 达到最小的整数向量。从 CVXPY 建模的角度看目标 $|Ax-b|_2^2$ 恰好对应cp.sum_squares(A x - b)属于二次凸函数配合整数变量约束即构成一个标准 MIQP。该问题常出现在需要将连续估计结果整数化的场景例如离散信号恢复、量化误差最小化等。求解器选择与安装运行 MIQP 示例前必须安装一个混合整数非线性求解器。CVXPY 首选的开源混合整数非线性求解器是 SCIP可通过以下任一方式安装pip install pyscipopt或conda install -c conda-forge pyscipopt为什么需要单独安装根据 doc/source/tutorial/constraints/index.rst 的说明For licensing reasons, CVXPY does not install any of the preferred solvers by default——出于许可原因CVXPY 默认不随包安装任何首选求解器因此你需要自行安装。仓库 cvxpy/reductions/solvers/defines.py 从各求解器接口类的类属性自动推导出混合整数求解器列表# Mixed-integer solver lists, derived from solver class attributes. MI_SOLVERS [ name for name, slv in SOLVER_MAP_CONIC.items() if slv.MIP_CAPABLE ] MI_SOCP_SOLVERS [ name for name, slv in SOLVER_MAP_CONIC.items() if slv.MIP_CAPABLE and SOC in getattr(slv, MI_SUPPORTED_CONSTRAINTS, slv.SUPPORTED_CONSTRAINTS) ]也就是说一个求解器是否可用于混合整数问题由其在 conic 求解器接口类中声明的MIP_CAPABLE标志决定。在当前仓库中声明MIP_CAPABLE True的求解器包括开源求解器SCIPscip_conif.pyMIP_CAPABLE True依赖pyscipopt、HiGHShighs_conif.py、GLPK_MIglpk_mi_conif.py、CBCcbc_conif.py、ECOS_BBecos_bb_conif.py以及 SciPy 的milp接口scipy_conif.py商业求解器GUROBIgurobi_conif.py、CPLEXcplex_conif.py、MOSEKmosek_conif.py、XPRESSxpress_conif.py、COPTcopt_conif.py、KNITRO 及 CUOPT。从源码结构看MI_SOCP_SOLVERS进一步筛选出同时支持混合整数二阶锥约束SOC的求解器SCIP 的MI_SUPPORTED_CONSTRAINTS即包含 SOC。对于非线性混合整数模型如含指数锥、SOCP 约束的问题官方文档建议使用 SCIP 或商业求解器GLPK_MI 与 CBC 只支持线性混合整数模型参见 tutorial/constraints 的相关说明。求解器能力对比要点求解器类型MIP 能力备注SCIP开源支持含非线性模型CVXPY 首选的开源混合整数非线性求解器pip install pyscipoptHiGHS开源支持经 SciPy版本 1.9.0集成也支持大规模 MIPGLPK_MI开源支持仅线性通过pip install cvxopt获得CBC开源支持仅线性线性混合整数模型GUROBI / CPLEX / MOSEK / XPRESS / COPT商业支持需商业许可学术用户可申请免费许可关于商业求解器的许可政策tutorial/constraints 给出如下细节CPLEX、GUROBI 和 MOSEK 为学术界学生和教师提供免费许可也为非学术界提供试用版CPLEX Free Edition 不限学术身份但需在线注册且限制问题规模不超过 1000 个变量和 1000 个约束XPRESS 的免费社区版无需注册但限制变量数与约束数之和不超过 5000COPT 的免费社区版限制在至多 2000 个变量和 2000 个约束。如果混合整数问题规模很大、或模型对 SCIP/HiGHS 而言过于困难官方文档建议转向 CPLEX、GUROBI、XPRESS、MOSEK 或 COPT 等商业求解器。完整的 MIQP 求解示例以下代码改编自官方示例 mixed_integer_quadratic_program.rst演示了如何在 CVXPY 中构建并求解一个混合整数最小二乘问题。第 1 步生成随机问题数据import cvxpy as cp import numpy as np # Generate a random problem np.random.seed(0) m, n 40, 25 A np.random.rand(m, n) b np.random.randn(m)这里固定随机种子np.random.seed(0)以保证问题可复现A是 $40 \times 25$ 的均匀分布随机矩阵b是 40 维标准正态随机向量。求解目标是从 25 个整数分量中找到一个 $x$使 $Ax$ 尽可能接近 $b$。第 2 步声明整数变量并构建问题# Construct a CVXPY problem x cp.Variable(n, integerTrue) objective cp.Minimize(cp.sum_squares(A x - b)) prob cp.Problem(objective) prob.solve()关键点在于cp.Variable(n, integerTrue)。查看 cvxpy/expressions/leaf.py 中Leaf.__init__的签名整数/布尔属性由以下参数控制def __init__( self, shape, valueNone, nonnegFalse, nonposFalse, complexFalse, imagFalse, symmetricFalse, diagFalse, PSDFalse, NSDFalse, hermitianFalse, booleanFalse, integerFalse, sparsityFalse, posFalse, negFalse, boundsNone ) - None:其中integerTrue表示变量的每个分量都必须取整数值。该属性在内部被展开为索引集合if integer is True: shape max(shape, (1,)) flat_idx np.arange(np.prod(shape)) self.integer_idx np.unravel_index(flat_idx, shape, orderF) elif integer is False: self.integer_idx [] else: self.integer_idx integer也就是说integerTrue会把整个变量的所有坐标都标记为整数而integer参数也支持传入坐标元组列表Iterable用于只对变量的一部分下标施加整数约束——这正是 leaf.py 注释中所说的in some indices andintegerin others。booleanTrue的语义与之完全对称用于布尔0/1变量。目标函数cp.sum_squares(A x - b)展开即 $|Ax-b|_2^2$构成凸二次目标。由于整数约束的存在prob.solve()会自动选择一个已安装的混合整数求解器。从 conic_solver.py 的实现可以看出非 MIP 求解器MIP_CAPABLE False如 Clarabel、CUCLARABEL在遇到混合整数问题时会直接被过滤掉。第 3 步查看求解结果print(Status: , prob.status) print(The optimal value is, prob.value) print(A solution x is) print(x.value)在安装了 SCIP或其他混合整数求解器的环境中上述代码的典型输出为Status: optimal The optimal value is 13.66000322824753 A solution x is [-1. 1. 1. -1. 0. 0. -1. -2. 0. 0. 0. 1. 1. 0. 1. 0. -1. -1. -1. 0. 2. -1. 2. 0. -1.]其中prob.status为optimalprob.value为最优目标值13.66000322824753x.value则是一个 25 维的整数向量。可以验证该向量的每个分量都是整数符合 $x \in \mathbf{Z}^{25}$ 的约束而prob.value正是该整数向量代入 $|Ax-b|_2^2$ 后得到的最小残差平方和。整数变量的进阶用法MIQP 只是 CVXPY 混合整数建模能力的一个入口。结合 tutorial/constraintsCVXPY 的整数/布尔变量还支持以下常见模式# Creates a 10-vector constrained to have boolean valued entries. x cp.Variable(10, booleanTrue) # expr1 must be boolean valued. constr1 (expr1 x) # Creates a 5 by 7 matrix constrained to have integer valued entries. Z cp.Variable((5, 7), integerTrue) # expr2 must be integer valued. constr2 (expr2 Z)booleanTrue变量每个分量为 0 或 1用于 0-1 整数规划、选址、指派等组合优化问题integerTrue变量每个分量为任意整数可配合bounds参数如bounds[-1.5, 2]见 test_attributes.py限定取值范围矩阵变量同样支持整数/布尔属性如cp.Variable((5, 7), integerTrue)。仓库测试 test_attributes.py 还覆盖了整数变量与nonneg、symmetric等属性组合的合法性与求解行为。此外对布尔变量 CVXPY 还支持~NOT、AND、|OR、^XOR等逻辑运算详见 tutorial/constraints这些逻辑原子都是仿射的可兼容混合整数线性与锥求解器。总结MIQP 的数学本质凸二次目标$Q \succeq 0$ 整数变量约束属于混合整数非线性优化的子类建模方式在 CVXPY 中通过cp.Variable(n, integerTrue)或booleanTrue声明整数变量再组合cp.sum_squares、cp.quad_form等二次原子即可构造 MIQP约束 $\mathcal{C}$ 通过cp.Problem(objective, constraints)附加求解器选型默认需自行安装求解器开源首选 SCIPpip install pyscipopt支持非线性混合整数模型其次 HiGHS、GLPK_MI、CBC大规模或高难度问题可考虑 CPLEX、GUROBI、MOSEK、XPRESS、COPT 等商业求解器验证输出检查prob.status optimal、prob.value与x.value确认最优值与整数解的正确性。掌握了上述流程你就可以将 CVXPY 的 MIQP 能力直接应用到离散信号恢复、整数资源分配、组合优化等实际工程问题中。赞分享科学计算【免费下载链接】cvxpyA Python-embedded modeling language for convex optimization problems.项目地址https://gitcode.com/gh_mirrors/cv/cvxpy点击查看免费下载相关推荐Nettu Meet测试策略与实践单元测试到集成测试的完整覆盖Nettu Meet测试策略与实践单元测试到集成测试的完整覆盖 Nettu Meet作为一款开源视频会议系统为确保其在教学场景下的稳定运行采用了从单元测试音视频后端前端Cbc混合整数线性规划求解器实用教程从安装到实战优化Cbc混合整数线性规划求解器实用教程从安装到实战优化 一、认识Cbc优化问题的智能翻译官 CbcCoin or Branch and Cut是一款开科学计算使用CVXPY求解半定规划(SDP)问题详解使用CVXPY求解半定规划 SDP 问题详解 什么是半定规划 SDP 半定规划 Semidefinite Programming, SDP 是凸优化领域中的一个科学计算上一篇Kilo 企业级 MCP 管控设计提案组织级 MCP 服务器白名单与受管配置机制下一篇Beekeeper Studio 新手入门指南从安装到 SQLite 演示库实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 使用 CVXPY 求解混合整数二次规划（MIQP）：数学建模、求解器选型与实战示例
科学计算【免费下载链接】cvxpyA Python-embedded modeling language for convex optimization problems.项目地址https://gitcode.com/gh_mirrors/cv/cvxpy点击查看免费下载混合整数二次规划Mixed-Integer Quadratic ProgramMIQP是凸优化与整数规划的交叉领域目标函数为半正定二次型而优化变量被约束为整数值。本文以 CVXPY 官方示例 mixed_integer_quadratic_program.rst 为骨架系统讲解 MIQP 的数学形式、整数变量的建模方式、混合整数求解器的选择与安装并结合仓库源码给出一个可完整运行的混合整数最小二乘示例。读完本文你将掌握用 CVXPY 声明整数变量、求解 MIQP 问题、解读求解结果以及在不同求解器SCIP、HiGHS、GLPK_MI、CBC 及商业求解器之间做出正确选择。MIQP 的数学形式混合整数二次规划的标准形式为$$ \begin{array}{ll} \mbox{minimize} x^T Q x q^T x r \ \mbox{subject to} x \in \mathcal{C}\ x \in \mathbf{Z}^n, \end{array} $$其中$x \in \mathbf{Z}^n$ 是优化变量$\mathbf{Z}^n$ 表示所有分量为整数的 $n$ 维向量集合$Q \in \mathbf{S}_^n$ 是 $n \times n$ 对称半正定矩阵保证目标函数为凸二次型$q \in \mathbf{R}^n$ 与 $r \in \mathbf{R}$ 分别是线性项系数与常数项连同 $Q$ 一起构成问题数据$\mathcal{C}$ 是某个凸集用于承载等式、不等式等附加约束。需要特别指出的是MIQP 与普通 QP 的本质区别在于整数约束 $x \in \mathbf{Z}^n$。这一约束使可行域不再连续问题整体属于非凸的混合整数优化范畴因而无法用内点法等连续优化算法直接求解必须依赖专门的混合整数求解器MIP solver。一个典型实例混合整数最小二乘MIQP 最常见也最具代表性的特例是混合整数最小二乘mixed-integer least squares其形式为$$ \begin{array}{ll} \mbox{minimize} |Ax-b|_2^2 \ \mbox{subject to} x \in \mathbf{Z}^n, \end{array} $$其中 $x \in \mathbf{Z}^n$ 是优化变量$A \in \mathbf{R}^{m \times n}$ 与 $b \in \mathbf{R}^{m}$ 是问题数据。该问题的最优解 $x^{\star}$ 是一个使残差平方和 $|Ax-b|_2^2$ 达到最小的整数向量。从 CVXPY 建模的角度看目标 $|Ax-b|_2^2$ 恰好对应cp.sum_squares(A x - b)属于二次凸函数配合整数变量约束即构成一个标准 MIQP。该问题常出现在需要将连续估计结果整数化的场景例如离散信号恢复、量化误差最小化等。求解器选择与安装运行 MIQP 示例前必须安装一个混合整数非线性求解器。CVXPY 首选的开源混合整数非线性求解器是 SCIP可通过以下任一方式安装pip install pyscipopt或conda install -c conda-forge pyscipopt为什么需要单独安装根据 doc/source/tutorial/constraints/index.rst 的说明For licensing reasons, CVXPY does not install any of the preferred solvers by default——出于许可原因CVXPY 默认不随包安装任何首选求解器因此你需要自行安装。仓库 cvxpy/reductions/solvers/defines.py 从各求解器接口类的类属性自动推导出混合整数求解器列表# Mixed-integer solver lists, derived from solver class attributes. MI_SOLVERS [ name for name, slv in SOLVER_MAP_CONIC.items() if slv.MIP_CAPABLE ] MI_SOCP_SOLVERS [ name for name, slv in SOLVER_MAP_CONIC.items() if slv.MIP_CAPABLE and SOC in getattr(slv, MI_SUPPORTED_CONSTRAINTS, slv.SUPPORTED_CONSTRAINTS) ]也就是说一个求解器是否可用于混合整数问题由其在 conic 求解器接口类中声明的MIP_CAPABLE标志决定。在当前仓库中声明MIP_CAPABLE True的求解器包括开源求解器SCIPscip_conif.pyMIP_CAPABLE True依赖pyscipopt、HiGHShighs_conif.py、GLPK_MIglpk_mi_conif.py、CBCcbc_conif.py、ECOS_BBecos_bb_conif.py以及 SciPy 的milp接口scipy_conif.py商业求解器GUROBIgurobi_conif.py、CPLEXcplex_conif.py、MOSEKmosek_conif.py、XPRESSxpress_conif.py、COPTcopt_conif.py、KNITRO 及 CUOPT。从源码结构看MI_SOCP_SOLVERS进一步筛选出同时支持混合整数二阶锥约束SOC的求解器SCIP 的MI_SUPPORTED_CONSTRAINTS即包含 SOC。对于非线性混合整数模型如含指数锥、SOCP 约束的问题官方文档建议使用 SCIP 或商业求解器GLPK_MI 与 CBC 只支持线性混合整数模型参见 tutorial/constraints 的相关说明。求解器能力对比要点求解器类型MIP 能力备注SCIP开源支持含非线性模型CVXPY 首选的开源混合整数非线性求解器pip install pyscipoptHiGHS开源支持经 SciPy版本 1.9.0集成也支持大规模 MIPGLPK_MI开源支持仅线性通过pip install cvxopt获得CBC开源支持仅线性线性混合整数模型GUROBI / CPLEX / MOSEK / XPRESS / COPT商业支持需商业许可学术用户可申请免费许可关于商业求解器的许可政策tutorial/constraints 给出如下细节CPLEX、GUROBI 和 MOSEK 为学术界学生和教师提供免费许可也为非学术界提供试用版CPLEX Free Edition 不限学术身份但需在线注册且限制问题规模不超过 1000 个变量和 1000 个约束XPRESS 的免费社区版无需注册但限制变量数与约束数之和不超过 5000COPT 的免费社区版限制在至多 2000 个变量和 2000 个约束。如果混合整数问题规模很大、或模型对 SCIP/HiGHS 而言过于困难官方文档建议转向 CPLEX、GUROBI、XPRESS、MOSEK 或 COPT 等商业求解器。完整的 MIQP 求解示例以下代码改编自官方示例 mixed_integer_quadratic_program.rst演示了如何在 CVXPY 中构建并求解一个混合整数最小二乘问题。第 1 步生成随机问题数据import cvxpy as cp import numpy as np # Generate a random problem np.random.seed(0) m, n 40, 25 A np.random.rand(m, n) b np.random.randn(m)这里固定随机种子np.random.seed(0)以保证问题可复现A是 $40 \times 25$ 的均匀分布随机矩阵b是 40 维标准正态随机向量。求解目标是从 25 个整数分量中找到一个 $x$使 $Ax$ 尽可能接近 $b$。第 2 步声明整数变量并构建问题# Construct a CVXPY problem x cp.Variable(n, integerTrue) objective cp.Minimize(cp.sum_squares(A x - b)) prob cp.Problem(objective) prob.solve()关键点在于cp.Variable(n, integerTrue)。查看 cvxpy/expressions/leaf.py 中Leaf.__init__的签名整数/布尔属性由以下参数控制def __init__( self, shape, valueNone, nonnegFalse, nonposFalse, complexFalse, imagFalse, symmetricFalse, diagFalse, PSDFalse, NSDFalse, hermitianFalse, booleanFalse, integerFalse, sparsityFalse, posFalse, negFalse, boundsNone ) - None:其中integerTrue表示变量的每个分量都必须取整数值。该属性在内部被展开为索引集合if integer is True: shape max(shape, (1,)) flat_idx np.arange(np.prod(shape)) self.integer_idx np.unravel_index(flat_idx, shape, orderF) elif integer is False: self.integer_idx [] else: self.integer_idx integer也就是说integerTrue会把整个变量的所有坐标都标记为整数而integer参数也支持传入坐标元组列表Iterable用于只对变量的一部分下标施加整数约束——这正是 leaf.py 注释中所说的in some indices andintegerin others。booleanTrue的语义与之完全对称用于布尔0/1变量。目标函数cp.sum_squares(A x - b)展开即 $|Ax-b|_2^2$构成凸二次目标。由于整数约束的存在prob.solve()会自动选择一个已安装的混合整数求解器。从 conic_solver.py 的实现可以看出非 MIP 求解器MIP_CAPABLE False如 Clarabel、CUCLARABEL在遇到混合整数问题时会直接被过滤掉。第 3 步查看求解结果print(Status: , prob.status) print(The optimal value is, prob.value) print(A solution x is) print(x.value)在安装了 SCIP或其他混合整数求解器的环境中上述代码的典型输出为Status: optimal The optimal value is 13.66000322824753 A solution x is [-1. 1. 1. -1. 0. 0. -1. -2. 0. 0. 0. 1. 1. 0. 1. 0. -1. -1. -1. 0. 2. -1. 2. 0. -1.]其中prob.status为optimalprob.value为最优目标值13.66000322824753x.value则是一个 25 维的整数向量。可以验证该向量的每个分量都是整数符合 $x \in \mathbf{Z}^{25}$ 的约束而prob.value正是该整数向量代入 $|Ax-b|_2^2$ 后得到的最小残差平方和。整数变量的进阶用法MIQP 只是 CVXPY 混合整数建模能力的一个入口。结合 tutorial/constraintsCVXPY 的整数/布尔变量还支持以下常见模式# Creates a 10-vector constrained to have boolean valued entries. x cp.Variable(10, booleanTrue) # expr1 must be boolean valued. constr1 (expr1 x) # Creates a 5 by 7 matrix constrained to have integer valued entries. Z cp.Variable((5, 7), integerTrue) # expr2 must be integer valued. constr2 (expr2 Z)booleanTrue变量每个分量为 0 或 1用于 0-1 整数规划、选址、指派等组合优化问题integerTrue变量每个分量为任意整数可配合bounds参数如bounds[-1.5, 2]见 test_attributes.py限定取值范围矩阵变量同样支持整数/布尔属性如cp.Variable((5, 7), integerTrue)。仓库测试 test_attributes.py 还覆盖了整数变量与nonneg、symmetric等属性组合的合法性与求解行为。此外对布尔变量 CVXPY 还支持~NOT、AND、|OR、^XOR等逻辑运算详见 tutorial/constraints这些逻辑原子都是仿射的可兼容混合整数线性与锥求解器。总结MIQP 的数学本质凸二次目标$Q \succeq 0$ 整数变量约束属于混合整数非线性优化的子类建模方式在 CVXPY 中通过cp.Variable(n, integerTrue)或booleanTrue声明整数变量再组合cp.sum_squares、cp.quad_form等二次原子即可构造 MIQP约束 $\mathcal{C}$ 通过cp.Problem(objective, constraints)附加求解器选型默认需自行安装求解器开源首选 SCIPpip install pyscipopt支持非线性混合整数模型其次 HiGHS、GLPK_MI、CBC大规模或高难度问题可考虑 CPLEX、GUROBI、MOSEK、XPRESS、COPT 等商业求解器验证输出检查prob.status optimal、prob.value与x.value确认最优值与整数解的正确性。掌握了上述流程你就可以将 CVXPY 的 MIQP 能力直接应用到离散信号恢复、整数资源分配、组合优化等实际工程问题中。赞分享科学计算【免费下载链接】cvxpyA Python-embedded modeling language for convex optimization problems.项目地址https://gitcode.com/gh_mirrors/cv/cvxpy点击查看免费下载相关推荐Nettu Meet测试策略与实践单元测试到集成测试的完整覆盖Nettu Meet测试策略与实践单元测试到集成测试的完整覆盖 Nettu Meet作为一款开源视频会议系统为确保其在教学场景下的稳定运行采用了从单元测试音视频后端前端Cbc混合整数线性规划求解器实用教程从安装到实战优化Cbc混合整数线性规划求解器实用教程从安装到实战优化 一、认识Cbc优化问题的智能翻译官 CbcCoin or Branch and Cut是一款开科学计算使用CVXPY求解半定规划(SDP)问题详解使用CVXPY求解半定规划 SDP 问题详解 什么是半定规划 SDP 半定规划 Semidefinite Programming, SDP 是凸优化领域中的一个科学计算上一篇Kilo 企业级 MCP 管控设计提案组织级 MCP 服务器白名单与受管配置机制下一篇Beekeeper Studio 新手入门指南从安装到 SQLite 演示库实战创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考