python-3.x - 线性规划 - Google ortool - 错误的决策变量最终值

Question

我正在尝试解决线性规划问题。以下是问题的具体情况:

我有一个网络流问题，已转换为线性规划问题。因此，所有流量约束，例如容量、流量守恒等，都必须强制执行。我的目标是最大限度地降低成本。

决策变量 - 我通过定义字典并在这 128 个位置中的每个位置添加决策变量来构建两个 8x8 矩阵。

约束 - 总共有 24 个约束，即: 1) 流程从源头开始。两个 8x8 矩阵都有 2 个约束。 2) 水流在水槽处结束。两个 8x8 矩阵都有 2 个约束。 3) 流量守恒有 12 个约束，两个矩阵各有 8 个。 4) 有 2 个约束来遵守容量约束，每个矩阵 1 个。 5)有6个约束以避免重复

所有变量都必须是二进制的。

目标 - 8x8 矩阵中的某些变量的总和需要最小化。

同样，所有变量都必须是二进制的。

我已经能够在 Google ORTOOLS 中编写解决方案，并且解决方案收敛并显示最小值。但是，当我查看变量时，有些变量具有非二进制值。另外，该解决方案是错误的(我有一个在 Excel 中运行的现有解决方案，它是正确的且不同)。

如果有人能指出我正确的方向，我将不胜感激。以下是用 Python 36 编写的代码。

    from ortools.linear_solver import pywraplp
import numpy as np

def configure_constraints(cfg, solver, variable_list):

    print(cfg)
    dest_convs = cfg['dest_convs']
    msize = cfg['lookback_win'] + 1 + 1
    rem_capacity = cfg['rem_caps']

    # Constraint 1 - Flow starts at the source
    for i in range(dest_convs):
        # print([(i, 0, c) for c in range(1, msize)])
        solver.Add(solver.Sum([variable_list[(i,0,c)] for c in range(1, msize)]) == 1)

    # Constraint 2 - Flow ends at the sink
    for i in range(dest_convs):
        # print([(i, r, msize - 1) for r in range(1, msize)])
        solver.Add(solver.Sum([variable_list[(i,r,msize - 1)] for r in range(1, msize)]) == 1)

    # Constraint 3 - Flow Conservation
    for i in range(dest_convs):
        for r in range(msize - 1):
            if r+1 == msize - 1:
                continue

            solver.Add(solver.Sum([variable_list[(i,rind, r+1)] for rind in range(r + 1)]) - solver.Sum([variable_list[(i,r+1, cind + 1)] for cind in range(r+1, msize - 1)]) == 0)
    #
    # # Constraint 4 - Capacity Constraint
    for i in range(dest_convs):
        solver.Add(solver.Sum([variable_list[(i, r, c)] for r in range(1, msize-1) for c in range(r+1, msize - 1)]) <= rem_capacity[i] - 1)

    #
    # # Constraint 5 - 1-vehicle, 1-conveyor
    dest_conv_list = []
    for i in range(dest_convs):
        dest_conv_list.append([])
        for r in range(1, msize - 1):
            dest_conv_list[i].append(sum([variable_list[(i,r,c)] for c in range(r+1, msize)]))

    for items in zip(*dest_conv_list):
        solver.Add(solver.Sum(items) == 1)



def configure_objective(solver, variable_list, cost_vars):
    # Objective
    solver.Minimize(solver.Sum([variable_list[items] for items in zip(*np.where(cost_vars))]))


def solve(solver):
    result_status = solver.Solve()
    return result_status

def configure_variables(cfg, solver):

    # identify variables for the objective function
    # print(cfg)
    nvehs = cfg['vehicles']
    dest_convs = cfg['dest_convs']
    color_vec = cfg['color_vec']
    cur_cars = cfg['cur_cars']
    msize = cfg['lookback_win'] + 1 + 1

    # objective_mat = np.zeros((msize, msize), dtype="int32")
    mat = [[[0] * msize for i in range(msize)] for j in range(dest_convs)]

    # source to vehicles
    for i in range(dest_convs):
        for j in range(nvehs):
            # print(color_vec[j], cur_cars[i])
            if color_vec[j] != cur_cars[i]:
                mat[i][0][j+1] = 1


    for h in range(dest_convs):
        for i in range(0, nvehs):
            for j in range(i+1, nvehs):
                # print(i+1,j+1)
                # print(color_vec[i+1], color_vec[j])
                if color_vec[i] != color_vec[j]:
                    mat[h][i+1][j + 1] = 1

    cost_vars = np.array(mat).reshape(dest_convs, msize, msize)
    print(np.array(mat).reshape(dest_convs,msize,msize))

    dvars = {}
    for i in range(dest_convs):
        for j in range(msize):
            for k in range(msize):
                dvars[i, j, k] = solver.BoolVar('x[%i,%i, %i]' % (i, j, k))


    return  dvars, cost_vars

def main(cfg, what):
    solver = pywraplp.Solver('SolveSimpleSystem', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

    dvars_list, cost_vars = configure_variables(cfg, solver)

    configure_constraints(cfg, solver, dvars_list)
    configure_objective(solver, dvars_list, cost_vars)

    result_status = solve(solver)

    print('Number of Variables:', solver.NumVariables())
    print('Number of Constraints:', solver.NumConstraints())
    # print('Constraints:',     solver.)

    if result_status == solver.OPTIMAL:
        print('Solution Found.')
        # The problem has an optimal solution.
        print(('Problem solved in %f milliseconds' % solver.wall_time()))
        # The objective value of the solution.
        print(('Optimal objective value = %f' % solver.Objective().Value()))

        var_sum = 0
        for variable in dvars_list:
            print(('%s = %f' % (dvars_list[variable].name(), dvars_list[variable].solution_value())))
            var_sum += dvars_list[variable].solution_value()

        print(('Variable sum = %f' % var_sum))

        # The value of each variable in the solution.
    elif result_status == solver.INFEASIBLE:
        print('No solution found.')
    elif result_status == solver.POSSIBLE_OVERFLOW:
        print('Some inputs are too large and may cause an integer overflow.')


if __name__ == '__main__':
    cfg = {'vehicles': 6,
           'dest_convs': 2,
           'cur_cars':['B', 'R'],
           'rem_caps': [3,3],
           'lookback_win':6,
           'color_vec': ['W', 'W', 'B', 'B', 'R', 'B'],
           }

    main(cfg, 'cost')

Answer 1

参见:https://groups.google.com/forum/#!msg/or-tools-discuss/p5qVzZWIeIg/g77egaD-AAAJ

Glop is a pure LP. It will only solve the relaxation of the mip problem. So it is normal that the error checker tells you that the solution is not integral.

You can change GLOP_LINEAR_PROGRAMMING to BOP_INTEGER_PROGRAMMING if you program is purely boolean. Or you can stay with CBC

这就是为什么您应该使用:

• pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING
• pywraplp.Solver.BOP_INTEGER_PROGRAMMING
• pywraplp.Solver.SAT_INTEGER_PROGRAMMING

而不是pywraplp.Solver.GLOP_LINEAR_PROGRAMMING。