python调用SCIP求解下料问题(Cutting Stock Problem)

2023-10-24 11:59

本文主要是介绍python调用SCIP求解下料问题(Cutting Stock Problem),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 1. 问题示例
  • 2. 数学模型
  • 3. python调用开源求解器SCIP代码
  • 4. Todo
  • 参考文献

1. 问题示例

下料问题(Cutting Stock Problem,CSP)也叫板材切割问题。例如,有一批长度为110cm的板材(且称之为母料),需要切割成不同尺寸的小板材,例如下图所示,20cm的需要48个,45cm的需要35个, …,请问怎样切割,才能最省母料。

2. 数学模型

  • 数学模型直接参考《Column Generation》第五章中的Kantorovich Model
    请添加图片描述
    请添加图片描述

3. python调用开源求解器SCIP代码

  • python代码
import os
import pandas as pd
import numpy as np
import pyscipopt as opt# ========== 测试算例 ==========
W = 100  # 原料板材的长度
w = [3, 6 ,7, 11]  # 制造产品i需要的长度
b = [250, 200, 180, 100]  # 产品i的总需求量
I = len(w)  # 产品种类的数量
K = 100  # 假设原料板材的个数 (其实这个值可以提前预处理计算)model = opt.Model('MCP')
# ========== 定义变量 ==========
x0 = {}  
x = {}
# x0_k: 0-1变量,原料板材k是否被使用
for k in range(K):x0[k] = model.addVar(vtype='B', name='roll_' + str(k))# x_i_k: 在原料板材k中,切割产品i的数量
for i in range(I):for k in range(K):x[i, k] = model.addVar(vtype='C', name='num_' + str(i) + '_' + str(k))# ========== 定义约束 ==========
# 约束1: 所有切割得到产品i,满足需求
for i in range(I):model.addCons(opt.quicksum(x[i, k] for k in range(K)) >= b[i], name='demand_' + str(i))# 约束2: 如果原材料k被使用,则其切割的产品的总长度不能超过板材长度W
for k in range(K):model.addCons(opt.quicksum(x[i, k] * w[i] for i in range(I)) <= x0[k] * W, name='width_' + str(k))# 约束3: 原材料K是一样的,没有类似序列的属性, 可能多个解对应一样的切割方案,让选中的原料板材都在前面序列
for k in range(K-1):model.addCons(x0[k] >= x0[k+1])# ==========定义目标==========
# 目标: 原料板材使用数量最小
model.setObjective(opt.quicksum(x0[k] for k in range(K)))
model.setMinimize()
model.optimize()# ========== 输出结果 ==========
print('model_status = ', model.getGap())
print('model_gap =', model.getStatus())
print('model_obj =', model.getObjVal())roll_lst = []
for k in range(K):if model.getVal(x0[k]) > 0:roll_lst.append(k)
print(roll_lst)
  • 结果
    请添加图片描述

4. Todo

  • 当算例达到一定规模时,使用求解器求解效率可能会变慢很多,可以使用列生成算法 (Column Generation) 进行求解

参考文献

《Column Generation》Guy Desaulniers (Editor), Jacques Desrosiers (Editor), Marius M. Solomon (Editor), chapter 5

这篇关于python调用SCIP求解下料问题(Cutting Stock Problem)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/275004

相关文章

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别: 当你在一个模块(文件)中使用 global 声明变量时,这个变量只在该模块的全局命名空

好题——hdu2522(小数问题:求1/n的第一个循环节)

好喜欢这题,第一次做小数问题,一开始真心没思路,然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数,不能写作两整数之比*****************************(一开始没想到,小学没学好) 此题1/n肯定是一个有限循环小数,了解这些后就能做此题了。 按照除法的机制,用一个函数表示出来就可以了,代码如下

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

如何在页面调用utility bar并传递参数至lwc组件

1.在app的utility item中添加lwc组件: 2.调用utility bar api的方式有两种: 方法一,通过lwc调用: import {LightningElement,api ,wire } from 'lwc';import { publish, MessageContext } from 'lightning/messageService';import Ca

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如,在当前目录下创建一个名为 myenv 的虚拟环境: python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行: source myenv/bin/activate 3.与notebook连接 在虚拟环境中,使用 pip 安装 Jupyter 和 ipykernel: pip instal

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时,您应该注意以下几个关键点: 平衡精度 平衡精度是衡量平衡机性能的核心指标,直接影响到不平衡量的检测与校准的准确性,从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声,提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮,适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监

【机器学习】高斯过程的基本概念和应用领域以及在python中的实例

引言 高斯过程(Gaussian Process,简称GP)是一种概率模型,用于描述一组随机变量的联合概率分布,其中任何一个有限维度的子集都具有高斯分布 文章目录 引言一、高斯过程1.1 基本定义1.1.1 随机过程1.1.2 高斯分布 1.2 高斯过程的特性1.2.1 联合高斯性1.2.2 均值函数1.2.3 协方差函数(或核函数) 1.3 核函数1.4 高斯过程回归(Gauss

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k