线性规划 - Google ortools - 不正确的决策变量最终值

Question

我正在尝试解决线性规划问题。以下是问题的规格：

我有一个已转换为线性规划问题的网络流问题。因此，必须强制执行所有流量约束，例如容量、流量守恒等。我的objective是为了最小化成本。

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

约束——总共有24个约束，即： 1）流量从源头开始。两个 8x8 矩阵的 2 个约束。 2）流程在汇点结束。两个 8x8 矩阵的 2 个约束。 3) 流量守恒有 12 个约束条件，两个矩阵各有 8 个约束条件。 4) 有 2 个约束来遵守容量约束，每个矩阵 1 个。 5) 有6条约束可以避免重复

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

Objective - 那些8x8矩阵中有一些变量的总和需要最小化。

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

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

如果有人能指出正确的方向，我将不胜感激。下面是写在Python36.

中的代码

    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。

线性规划 - Google ortools - 不正确的决策变量最终值

Linear Programming - Google ortools - incorrect decision variable final values

linear-programming

python-3.x

network-flow

or-tools