如何读取scipy milp的MPS文件

aor9mmx1  于 2022-11-10  发布在  其他
关注(0)|答案(1)|浏览(219)

Scipy 1.9现在支持milp。这是一个好消息,但是要使用它,我需要读入一个MPS文件来说明问题。Scipy似乎没有读入MPS文件的功能。
我怎么能那样做呢?

djmepvbi

djmepvbi1#

正如在注解中提到的,这个特性还没有实现。作为一种解决方案,你可以用PuLPpython-mip这样的建模框架读取.mps文件,然后提取底层MILP的所有数据。
下面是通过python-mip实现这种方法的一个简单的(因此很慢)实现:

import numpy as np
from mip import Model
from scipy.sparse import csr_matrix

def read_mps(file: str):
    """
    Reads a .mps and saves all the data of the MILP:

    min c^T * x

    s.t. b_l <= A*x <= b_u
          lb <=   x <= ub
                x_i integer if integrality[i] = 1
    """
    mdl = Model(solver_name="CBC")
    mdl.read(file)

    # model parameters
    num_vars = len(mdl.vars)
    num_cons = len(mdl.constrs)

    # variable types and bounds
    lb = np.zeros(num_vars)
    ub = np.inf*np.ones(num_vars)
    integrality = np.zeros(num_vars)
    for i, var in enumerate(mdl.vars):
        lb[i] = var.lb
        ub[i] = var.ub
        if var.var_type != "C":
            integrality[i] = 1

    # objective
    c = np.zeros(num_vars)
    for i, var in enumerate(mdl.vars):
        if var in mdl.objective.expr:
            c[i] = mdl.objective.expr[var]
    if mdl.sense != "MIN":
        c *= -1.0

    # constraint coefficient matrix
    b_l = -np.inf*np.ones((num_cons))
    b_u = np.inf*np.ones((num_cons))
    row_ind = []
    col_ind = []
    data    = []
    for i, con in enumerate(mdl.constrs):
        if con.expr.sense == "=":
            b_l[i] = con.rhs
            b_u[i] = con.rhs
        elif con.expr.sense == "<":
            b_u[i] = con.rhs
        elif con.expr.sense == ">":
            b_l[i] = con.rhs
        for j, var in enumerate(mdl.vars):
            if var in (expr := con.expr.expr):
                coeff = expr[var]
                row_ind.append(i)
                col_ind.append(j)
                data.append(coeff)
    A = csr_matrix((data, (row_ind, col_ind)), shape=(num_cons, num_vars))
    return c, b_l, A, b_u, lb, ub, integrality

然后,您可以读取所有数据并将其传递给milp,如下所示:

from scipy.optimize import milp, Bounds, LinearConstraint

c, b_l, A, b_u, lb, ub, integrality = read_mps("example.mps")
bounds = Bounds(lb, ub)
constraints = LinearConstraint(A, b_l, b_u)

res = milp(c=c, constraints=constraints, bounds=bounds, integrality=integrality)

尽管如此,上述解决方法仅适用于中小型模型文件。
顺便说一下,值得一提的是,scipy.optimize.milp在幕后使用了HiGHS solver,为此,PuLP最近也内置了一个接口,并且有计划为python-mip做同样的事情。这两个建模框架都可以读取.lp和.mps文件,并将它们传递给接口的求解器,所以没有迫切需要等待scipy中的这个特性。然而,公平地说,PuLP只连接了一些解算器的可执行文件,而不是随python包一起提供,并且进一步假设最终用户已经安装了它们。

相关问题