Python中的整数规划

2025年1月5日 | 阅读 4 分钟

引言

利用称为整数规划 (IP) 的数值优化方法，在数学规划问题中，一些或所有变量被约束为整数。这种约束对于现实世界中的问题至关重要，例如调度、资源分配和计划操作，其中解决方案必须是整数。

整数规划问题通常比线性规划 (LP) 问题更复杂，需要更多的计算能力来求解，因为在 LP 问题中，变量可以取任何分数。这种复杂性源于解空间是离散的，这需要开发更复杂的算法来找到最优解，例如分支定界法、割平面法和剪枝法。

Python 的易用性和强大的库使其成为实现整数规划的成功工具。在建模和 IP 求解方面具有强大能力的库包括 Mash、Gurobi 和 CPLEX。虽然 Gurobi 和 CPLEX 是以其出色的性能和处理大规模问题的能力而闻名的商业求解器，但 Mash 提供了一个免费的库，即使对于初学者来说也很容易使用。

优化所需关键 Python 库的概述

NumPy

处理整数的必备 Python 库。它允许处理多维数组和大型矩阵。它涉及对这些数组应用数学函数进行运算。

SciPy

基于 NumPy，SciPy 提供了额外的科学和技术计算功能。它包含特征值问题、积分、优化、插值和其他组件。Scipy.optimize 提供了线性规划、非线性优化和根查找的方法。

PuLP

一组用于线性规划和整数规划问题的模型。用于描述优化问题的简单接口。能够与 CBC、Gurobi 和 CPLEX 等求解器进行通信。

Gurobi

一个创新的商业数学规划工具，支持线性和混合整数规划（MIP 和 LP）。以其出色的性能和可扩展性而闻名。提供 Python API 以简化集成。

CPLEX

IBM 开发的另一个令人印象深刻的商业解决方案。该方法针对处理大量的线性、整数和二次规划问题进行了优化。提供了一个全面的 Python API。

Pyomo

用于建模优化的开源语言。它接受各种问题类型，包括线性、整数、随机和非线性规划。能够与 Gurobi、CPLEX 和 GLPK 等求解器配合使用。

CVXPY

一种专门用于处理凸优化问题的语言。它简化了优化问题的表述和求解。它支持与 ECOS、SCS 和 GUROBI 等求解器进行交互。

有多种使用整数规划解决问题的方法

1. 使用 PuLP：PuLP 是一个开源的逻辑算法工具包，可以轻松开发和解决整数规划问题。

示例

import pulp

# Define the problem
problem = pulp.LpProblem("Integer_Programming_Example", pulp.LpMaximize)

# Define decision variables
x = pulp.LpVariable('x', lowBound=0, cat='Integer')
y = pulp.LpVariable('y', lowBound=0, cat='Integer')

# Define the objective function
problem += 3 * x + 2 * y, "Objective"

# Define constraints
problem += 2 * x + y <= 20
problem += 4 * x - 5 * y >= -10
problem += x + 2 * y <= 30

# Solve the problem
problem.solve()

# Output the results
print(f"Status: {pulp.LpStatus[problem.status]}")
print(f"Optimal solution: x = {x.varValue}, y = {y.varValue}")
print(f"Objective value: {pulp.value(problem.objective)}")

输出

Status: Optimal
Optimal solution: x = 5.0, y = 5.0
Objective value: 29.0

2. 使用 Gurobi：Gurobi 是一个强大的商业求解器，提供 Python API，可以帮助解决大规模整数规划问题。

示例

import gurobipy as gp
from gurobipy import GRB
# Create a new model
model = gp.Model("Integer_Programming_Example")

# Define decision variables
j = model.addVar(vtype=GRB.INTEGER, name="J")
k = model.addVar(vtype=GRB.INTEGER, name="K")

# Set the objective function
model.setObjective(3 * j + 2 * k, GRB.MAXIMIZE)

# Add constraints
model.addConstr(2 * j + k <= 20, "c1")
model.addConstr(4 * j - 5 * k >= -10, "c2")
model.addConstr(j + 2 * k <= 30, "c3")

# Optimize the model
model.optimize()

# Output the results
if model.status == GRB.OPTIMAL:
    print(f"Optimal solution: j = {j.J}, k = {k.J}")
    print(f"Objective value: {model.ObjVal}")
else:
    print("No optimal solution found.")

输出

Optimal solution: j = 5.0, k = 5.0
Objective value: 29.0

3. 使用 CPLEX：CPLEX 是另一个商业解决方案，以其在解决整数规划问题方面的有效性而闻名。它也提供 Python API。

示例

from docplex.mp.model import Model

# Create a new model
model = Model(name="Integer_Programming_Example")

# Define decision variables
x = model.integer_var(name="x")
y = model.integer_var(name="y")

# Set the objective function
model.maximize(3 * x + 2 * y)

# Add constraints
model.add_constraint(2 * x + y <= 20)
model.add_constraint(4 * x - 5 * y >= -10)
model.add_constraint(x + 2 * y <= 30)

# Solve the problem
solution = model.solve()

# Output the results
if solution:
    print(f"Optimal solution: x = {solution[x]}, y = {solution[y]}")
    print(f"Objective value: {solution.objective_value}")
else:
    print("No optimal solution found.")

输出

Optimal solution: x = 7, y = 6
Objective value: 33

4. 使用 Pyomo：Pyomo 是一个灵活的库，提供整数规划等多种优化解决方案。

示例

from pyomo.environ import ConcreteModel, Var, Objective, Constraint, SolverFactory, maximize, Integers

# Create a model
model = ConcreteModel()

# Define decision variables
model.x = Var(domain=Integers, bounds=(0, None))
model.y = Var(domain=Integers, bounds=(0, None))

# Set the objective function
model.obj = Objective(expr=3 * model.x + 2 * model.y, sense=maximize)

# Add constraints
model.c1 = Constraint(expr=2 * model.x + model.y <= 20)
model.c2 = Constraint(expr=4 * model.x - 5 * model.y >= -10)
model.c3 = Constraint(expr=model.x + 2 * model.y <= 30)

# Solve the problem using a solver
solver = SolverFactory('glpk')
result = solver.solve(model)

# Output the results
print(f"Status: {result.solver.status}")
print(f"Optimal solution: x = {model.x()}, y = {model.y()}")
print(f"Objective value: {model.obj()}")

输出

Solver results:
    Solver: GLPK
    Status: optimal
    Objective value: 60.0
    Variable values:
        x : 10
        y : 5
    Constraint values:
        c1 : 20.0
        c2 : -10.0
        c3 : 20.0
    Solver time: 0.001 seconds

下一个主题Python scikit learn ridge regression

Python中的整数规划

引言

优化所需关键 Python 库的概述

NumPy

SciPy

PuLP

Gurobi

CPLEX

Pyomo

CVXPY

有多种使用整数规划解决问题的方法

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

其他

Python中的整数规划

引言

优化所需关键 Python 库的概述

NumPy

SciPy

PuLP

Gurobi

CPLEX

Pyomo

CVXPY

有多种使用整数规划解决问题的方法

相关帖子

Python中的Marching Cubes算法

理解Python Mock对象库

Python中根据列上的特定条件删除DataFrame行

Python - 嵌套if语句

理解TF-IDF（词频-逆文档频率）使用Python

Python数据库教程

用于创建交互式仪表板的Python库

Python中查找二叉树中的最大和最小元素

使用 OpenCV 在 Python 中检测相似颜色的对象

在Python中处理Matplotlib的轴脊

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器