我试图创建一个具有以下约束的矩阵
如果UserInput = [427.7, 12.2, 352.7, 58.3, 22.7, 31.9, 396.4, 29.4, 171.5, 474.5, 27.9, 200]
我想要像这样的输出矩阵
编辑1
我使用Pyomo尝试了以下方法,但是,我遇到了第五个约束,即列值应该在矩阵中对角对齐
import sys
import math
import numpy as np
import pandas as pd
from pyomo.environ import *
solverpath_exe= 'glpk-4.65\\w64\\glpsol.exe'
solver=SolverFactory('glpk',executable=solverpath_exe)
# Minimize the following:
# Remaining pieces to be zero for all et values
# The number of cells containg non-zero values
# Constraints
# 1) Column sum, CS, is: 300 <= CS <= 390
# 2) Row sum, RS, is equal to user-specified values, which are present in the E&T ticket column of the file
# 3) Number of non-zero values, NZV, in each column, should be: 0 < NZV <= 4
# 4) The NZV in the matrix should be: NZV >= 10
# 5) The pieces are stacked on top of each other. So, a the cell under a non-zero value cell is zero, than all cells underneath should have zeros.
maxlen = 390
minlen = 300
npiece = 4
piecelen = 10
# Input data: E&T Ticket values
etinput = [427.7, 12.2, 352.7, 58.3, 22.7, 31.9,
396.4, 29.4, 171.5, 474.5, 27.9, 200]
# Create data structures to store values
etnames = [f'et{i}' for i in range(1,len(etinput) + 1)]
colnames = [f'col{i}' for i in range(1, math.ceil(sum(etinput)/minlen))] #+1 as needed
et_val = dict(zip(etnames, etinput))
# Instantiate Concrete Model
model2 = ConcreteModel()
# define variables and set upper bound to 390
model2.vals = Var(etnames, colnames, domain=NonNegativeReals,bounds = (0, maxlen), initialize=0)
# Create Boolean variables
bigM = 10000
model2.y = Var(colnames, domain= Boolean)
model2.z = Var(etnames, colnames, domain= Boolean)
# Minimizing the sum of difference between the E&T Ticket values and rows
model2.minimizer = Objective(expr= sum(et_val[r] - model2.vals[r, c]
for r in etnames for c in colnames),
sense=minimize)
model2.reelconstraint = ConstraintList()
for c in colnames:
model2.reelconstraint.add(sum(model2.vals[r,c] for r in etnames) <= bigM * model2.y[c])
# Set constraints for row sum equal to ET values
model2.rowconstraint = ConstraintList()
for r in etnames:
model2.rowconstraint.add(sum(model2.vals[r, c] for c in colnames) <= et_val[r])
# Set contraints for upper bound of column sums
model2.colconstraint_upper = ConstraintList()
for c in colnames:
model2.colconstraint_upper.add(sum(model2.vals[r, c] for r in etnames) <= maxlen)
# Set contraints for lower bound of column sums
model2.colconstraint_lower = ConstraintList()
for c in colnames:
model2.colconstraint_lower.add(sum(model2.vals[r, c] for r in etnames) + bigM * (1-model2.y[c]) >= minlen)
model2.bool = ConstraintList()
for c in colnames:
for r in etnames:
model2.bool.add(model2.vals[r,c] <= bigM * model2.z[r,c])
model2.npienceconstraint = ConstraintList()
for c in colnames:
model2.npienceconstraint.add(sum(model2.z[r, c] for r in etnames) <= npiece)
# Call solver for model
solver.solve(model2);
# Create dataframe of output
pdtest = pd.DataFrame([[model2.vals[r, c].value for c in colnames] for r in etnames],
index=etnames,
columns=colnames)
pdtest
输出
我认为你把它设置为LP是正确的。它可以表示为MIP
我没有在这里修改过任何种类的输入,我也不确定您是否能保证所有具有约束的输入都有可行的结果
我惩罚非对角选择以鼓励对角选择,并设置一些“选择完整性”约束以强制块选择
在大约1/10秒内解决
结果
如果您已经知道哪些接近对角线的元素是非零的,那么它是线性方程组(对于列和345和指定的行和),但是您必须在组合上迭代。你有19个方程,其中有10个未知数(非零项的数量),这通常是不可解的。它变得容易了一点,因为你可以选择10个未知数,其中7个方程只需要大致满足,但我认为只有当你运气好的时候,解才存在(或者这是一个有解的练习)
假设12行中的每一行都必须有一个正确的和,那么至少需要12个非零元素。很可能,每行至少需要两个,每列至少需要两个
找到有解的最优集可能是一个NP完全问题,这意味着您必须系统地迭代所有组合,直到找到一个解
对于您的示例,大约有m=31个矩阵元素;不可能对所有组合进行迭代。你需要反复试验
下面是一个示例代码,用于使用numpy的最小二乘解算器优化所有31个元素
这将产生以下输出:
最小二乘解算器无法处理硬约束;如果您看到一列有点超出范围(例如299),您可以使用相同的
priority
技巧使解算器对该列更努力一些。您可以尝试逐个禁用较小的元素(例如<;10)。您还可以尝试使用linear programming optimizer,它更适合于具有硬相等要求和边界的问题相关问题 更多 >
编程相关推荐