使用pulp在整数线性程序中处理大参数

Question

在pulp的文档中https://coin-or.github.io/pulp/guides/how_to_debug.html，它这么说

检查数字的精度。如果您有非常大的数字（具有高精度），这通常会导致求解器出现问题。例如，永远不要在问题中使用 100000000000 的参数。

问题是我的 LP 参数这么大。我可以对这个问题做一些有帮助的转变吗？我尝试通过将所有参数除以相同的大数来缩放参数，但最终我得到了一些参数的非常小的小数值，因为只有每个方程/不等式的右侧很大。一个示例约束是

3*x + 4*y == 10000000000

，其中

x

和

y

必须是整数。

这是我的一套更完整的代码

f = open('data\input13_test.txt', 'r')
lines = f.readlines()
cost = 0
for i in range(0, len(lines), 4):
    a_coeff_eq_1 = int(lines[i].split(':')[1].split(',')[0].split('+')[1])
    a_coeff_eq_2 = int(lines[i].split(':')[1].split(',')[1].split('+')[1])
    b_coeff_eq_1 = int(lines[i+1].split(':')[1].split(',')[0].split('+')[1])
    b_coeff_eq_2 = int(lines[i+1].split(':')[1].split(',')[1].split('+')[1])
    c_eq_1 = int(lines[i+2].split(':')[1].split(',')[0].split('=')[1]) + 10000000000000
    c_eq_2 = int(lines[i+2].split(':')[1].split(',')[1].split('=')[1]) + 10000000000000
    
    a_coeff_eq_1
    a_coeff_eq_2
    b_coeff_eq_1 
    b_coeff_eq_2
    c_eq_1
    c_eq_2
    
    prob = LpProblem("MyProb", LpMinimize)
    a = LpVariable("a", 0, None, LpInteger)
    b = LpVariable("b", 0, None, LpInteger)
    prob += a_coeff_eq_1 * a + b_coeff_eq_1 * b == c_eq_1
    prob += a_coeff_eq_2 * a + b_coeff_eq_2 * b == c_eq_2
    prob += 3*a + b
    prob.solve(PULP_CBC_CMD(msg=1))
    if LpStatus[prob.status] == 'Optimal':
        for v in prob.variables():
            if v.name == 'a':
                cost += 3*v.varValue
            elif v.name == 'b':
                cost += v.varValue
            print(v.name, "=", v.varValue)
            
print(cost)

与 cs 相比，a 和 b 上的系数可能非常小。

输入文件中的示例

Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706

Answer 1

这个问题有一个与线性规划无关的单一解析整数解：

import io
import re
import typing


DELTA = int(1e13)


class Params(typing.NamedTuple):
    a1: int
    a2: int
    b1: int
    b2: int
    c1: int
    c2: int

    @classmethod
    def from_match(cls, match: re.Match) -> typing.Self:
        return cls(
            a1=int(match['a1']),
            a2=int(match['a2']),
            b1=int(match['b1']),
            b2=int(match['b2']),
            c1=int(match['c1']),
            c2=int(match['c2']),
        )

    def solve(self) -> tuple[
        int,  # x
        int,  # y
        int,  # offset
    ]:
        a1, a2, b1, b2, c1, c2 = self
        xoff = (
            (
                DELTA*(a1 + b1 - a2 - b2)  # this is zero!
                + c2*(a1 + b1) - c1*(a2 + b2)
            )//(
                b2*(a1 + b1) - b1*(a2 + b2)
            )
        )

        x = (c1 - b1*xoff + DELTA)//(a1 + b1)
        y = x + xoff

        return x, y, xoff

    def errors(self, x: int, y: int) -> tuple[int, int]:
        a1, a2, b1, b2, c1, c2 = self
        return (
            a1*x + b1*y - c1 - DELTA,
            a2*x + b2*y - c2 - DELTA,
        )


param_pat = re.compile(r'''(?ix)
    Button\ A:\      # first line
    X(?P<a1>         # named capture group
        [+\-][0-9]+  # integer with explicit sign
    ),\              # intermediate space
    Y(?P<a2>         # named capture group
        [+\-][0-9]+  # integer with explicit sign
    )\s*             # newline
    
    Button\ B:\      # second line
    X(?P<b1>         # named capture group
        [+\-][0-9]+  # integer with explicit sign
    ),\              # intermediate space
    Y(?P<b2>         # named capture grooup
        [+\-][0-9]+  # integer with explicit sign
    )\s*             # newline
    
    Prize:\          # third line
    X=(?P<c1>        # named capture group
        [0-9]+       # integer without sign
    ),\              # intermediate space
    Y=(?P<c2>        # named capture group
        [0-9]+       # integer without sign
    )
''')


def parse_all(f: typing.TextIO) -> typing.Iterator[Params]:
    return map(Params.from_match, param_pat.finditer(f.read()))


def main() -> None:

    with io.StringIO('''
Button A: X+51, Y+11
Button B: X+38, Y+78
Prize: X=16146, Y=3706''') as f:
        param, = parse_all(f)

    print('For single sample input of')
    print(param)

    x, y, xoff = param.solve()

    print('y - x =', xoff)
    print(f'x = {x:,}')
    print(f'y = {y:,}')
    print('errors:', param.errors(x, y))


if __name__ == '__main__':
    main()

For single sample input of
Params(a1=51, a2=11, b1=38, b2=78, c1=16146, c2=3706)
y - x = -311
x = 112,359,550,876
y = 112,359,550,565
errors: (0, 0)