Seeking Guidance: How to Access Dual Variables (Node Potentials) from SimpleMinCostFlow in Python OR-Tools?

[Marks Nannette]

Dear community,

I am currently working on a research project involving the Flexible Job Shop Scheduling Problem with Just-in-Time objectives. A key part of my solution method involves solving the timing subproblem, which is commonly modeled as a Minimum Cost Network Flow (MCNF) problem. According to the established literature, the optimal start times for the operations can be derived directly from the dual variables (i.e., the node potentials) of the solved MCNF model.

I am attempting to implement this using Google OR-Tools in Python, specifically with the SimpleMinCostFlow solver, which I understand is based on a highly efficient cost-scaling algorithm.

However, I have run into a very frustrating roadblock. After successfully solving the MCNF model, I am unable to find any method to retrieve the node potentials.

Here is a simplified representation of my workflow:

# Using the older API for illustration, but the issue persists with the new one
from ortools.graph import pywrapgraph

# 1. Define nodes, arcs, capacities, and costs for the MCNF model
#    - Precedence constraints are modeled as arcs with negative costs.
#    - E/T penalties are modeled as arcs connected to a source node.
# ...

# 2. Instantiate and solve the model
smcf = pywrapgraph.SimpleMinCostFlow()
# ... (add arcs using smcf.AddArcWithCapacityAndUnitCost(...))

status = smcf.Solve()

# 3. Attempt to retrieve dual variables (node potentials)
if status == smcf.OPTIMAL:
    print("Optimal solution found for the MCNF problem.")
   
    # PROBLEM HERE: This is what I need to do, but the method does not exist.
    try:
        # Based on C++ API documentation
        potentials = [smcf.NodePotential(i) for i in range(num_nodes)]
    except AttributeError as e:
        print(f"Error: {e}")
        # The object 'smcf' has no attribute 'NodePotential' or 'potential'.

My investigation so far has included:

1. Multiple OR-Tools Versions: I have systematically installed and tested several versions of ortools (including 9.3, 9.5, and more recent versions like 9.8+) across different Python environments (Python 3.8 and 3.11). The issue is consistent across all of them.

2. API Inspection: By inspecting the solver object (via dir(smcf)), I can confirm the presence of methods like OptimalCost() and Flow(), but there is no method named NodePotential(), potential(), or anything similar.

3. Documentation Review: The official Google OR-Tools documentation for the Python SimpleMinCostFlow wrapper also seems to completely omit any mention of a method for retrieving dual variables, whereas the C++ API documentation clearly lists the NodePotential() method.

This leads me to my main questions:

1. Is it correct to conclude that the official Python wrapper for SimpleMinCostFlow intentionally does not expose the functionality to access node potentials?

2. If this is the case, what is the recommended alternative approach within the OR-Tools Python ecosystem to obtain these dual values? Should I abandon the specialized SimpleMinCostFlow solver and instead model the primal problem (the timing problem with explicit start time variables and constraints) directly using the general-purpose LP solver (pywraplp)? While mathematically equivalent, this seems to forego the computational advantages of the specialized network flow algorithm.

Any guidance, clarification, or suggestions for a workaround would be greatly appreciated. This has become a significant bottleneck in my research.

Thank you for your time and expertise.

[Frederic Didier]

Yes, duals are not exposed in the API.

There are some complications to exposing the internal one, like scaling, and also I think some heuristic might cause them not to be always up to date.

If you need duals, I see two options:

- yes, you can use a LP solver instead.

- Or I think they are relatively easy to compute once you have the optimal min cost flow solution.

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/or-tools-discuss/9e73f2f3-5142-4449-b657-57d440faef28n%40googlegroups.com.

[Marks Nannette]

  Thank you very much for your quick and clear explanation! This helps me understand the design philosophy behind the API. Both options you provided—using an LP solver or computing the duals from the optimal flow—are very valuable. I will start by trying the LP solver approach, as it seems to be the most direct path forward.