Or-tools: Potential bug about dual_value by pywraplp

[ghost]

Hi, I was using "pywraplp" to solve a LP and wanted to get the dual value corresponding to some of the constraints. Below is the problem setup:

from ortools.linear_solver import pywraplp

cost = [[100, 120], [150, 140]]
# Instantiate a Glop solver.
solver = pywraplp.Solver('SolveLP', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

num_workers = len(cost)
num_tasks = len(cost[1])
x = {}

# Objective: minimize the total cost.
objective = solver.Objective()
for i in range(num_workers):
    for j in range(num_tasks):
        x[i, j] = solver.NumVar(0.0, 1.0, 'x[%i,%i]' % (i, j))
        objective.SetCoefficient(x[i, j], cost[i][j])

objective.SetMinimization()

worker_constraints = {}
# Each worker is assigned to at most 1 task.
for i in range(num_workers):
    worker_constraints[i] = solver.Constraint(0.0, 1.0, 'c[%i]' % i)
    for j in range(num_tasks):
        worker_constraints[i].SetCoefficient(x[i, j], 1)

# Each task is assigned to exactly one worker.
for j in range(num_tasks):
    solver.Add(solver.Sum([x[i, j] for i in range(num_workers)]) == 1)

status = solver.Solve()

if status == solver.OPTIMAL:
    for i in worker_constraints:
        print `worker_constraints[i].dual_value()

The resulting dual values for the two worker_constraints are -50 and 0, respectively. However, I think by definition, the dual value for the first work_constraint (corresponding to worker 0) should be -20 since adding an additional worker 0 will reduce the objective function by 20. Specifically, the primal optimal solution is worker 0 -> task 0 and worker 1 -> task 1, which has cost 240. Adding one more worker 0, the optimal solution becomes worker 0 -> task 0 and worker 0 -> task 1, which has cost 220.

[ghost]

@lperron just wanted to bump this up and get your feedback on this. Thanks!

[lperron]

Thanks, we will have a look.

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

2017-06-20 0:24 GMT+02:00 jianzhe-luo [e-mail]:

@lperron https://github.com/lperron just wanted to bump this up and get
your feedback on this. Thanks!

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/419#issuecomment-309590532,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17RwBEhy_qveaUEKvCZooBcYXbPQkks5sFvUGgaJpZM4N6g1h
.

[ghost]

Really appreciate that!

[lperron]

Have you tried with another solver (CLP_LINEAR_PROGRAMMING)?

Laurent Perron | Operations Research | [email protected] | (33) 1 42 68 53
00

2017-06-20 0:24 GMT+02:00 jianzhe-luo [e-mail]:

@lperron https://github.com/lperron just wanted to bump this up and get
your feedback on this. Thanks!

—
You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
https://github.com/google/or-tools/issues/419#issuecomment-309590532,
or mute the thread
https://github.com/notifications/unsubscribe-auth/AKj17RwBEhy_qveaUEKvCZooBcYXbPQkks5sFvUGgaJpZM4N6g1h
.

[ghost]

Thanks for the recommendation! CLP_LINEAR_PROGRAMMING produced the correct dual value -20, so we can use it as a workaround for our application for now. However, I am still interested in GLOP_LINEAR_PROGRAMMING as if I understand it correctly GLOP is the in-house LP solver, which means its performance is supposed to be better than CLP.

[KoenCobbaert]

Has any progress been made on this potential bug ? I've built a pretty large optimisation model (20K variables, 10K constraints) where a range of capacity constraints is the blocking factor for higher performance. Nevertheless, the dual values for all of these constraints appear to be 0, which does not really make sense. So I was wondering whether there is truely a bug in these dual value calculation.