Function order_sccs 

fn order_sccs(
    condensed_graph: &mut Graph<Vec<InvestmentSet>, GraphEdge>,
    original_graph: &Graph<InvestmentSet, GraphEdge, Directed>,
)

Order the members of each strongly connected component using a mixed-integer linear program.

condensed_graph contains the SCCs detected in the original investment graph, stored as Vec<InvestmentSet> node weights. Single-element components are already acyclic, but components with multiple members require an internal ordering so that the investment algorithm can treat them as near-acyclic chains, minimising potential disruption.

To rank the members of each multi-node component, we construct a mixed integer linear program (MILP). This MILP is adapted from the classical Linear Ordering Problem:

Marti, Rafael, and G Reinelt. The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization. 1st ed. 2011. Berlin: Springer-Verlag, 2011. Web.

The main features of the MILP are:

• Binary variables x[i][j] represent whether market i should appear before market j.
• Antisymmetry constraints force each pair (i, j) to choose exactly one direction (i.e. if i comes before j, then j cannot be before i).
• Transitivity constraints prevent 3-cycles, ensuring the resulting relation is acyclic (i.e. if i comes before j and j comes before k, then k cannot come before i).
• The objective minimises the number of “forward” edges (edges that would point from an earlier market to a later one), counted within the original SCC and treated as unit penalties. A small bias (<1) is added to nudge exporters earlier without outweighing the main objective (a bias

  1 would instead prioritise exporters even if it created extra conflicts in the final order).

Once the MILP is solved, markets are scored by the number of pairwise “wins” (how many other markets they precede). Sorting by this score — using the original index as a tiebreaker to keep relative order stable — yields the final sequence that replaces the SCC in the condensed graph. At least one pairwise mismatch is always inevitable (e.g. where X is solved before Y, but Y may consume X, so the demand for X cannot be guaranteed upfront).

Example

Suppose three markets (A, B and C) form a cycle in the original graph with the following edges:

A ← B ← C ← A

Additionally, C has an outgoing edge to a node outside the cycle.

The costs matrix in the MILP is set up to penalise any edge that points “forward” in the final order: if there’s an edge from X to Y we prefer to place Y before X so the edge points backwards:

   |   | A | B | C |
   | A | 0 | 0 | 1 |
   | B | 1 | 0 | 0 |
   | C | 0 | 1 | 0 |

On top of this, we give a small preference to markets that export outside the SCC, so nodes with outgoing edges beyond the cycle are pushed earlier. This is done via an EXTERNAL_BIAS parameter (B) applied to the cost matrix:

   |   | A | B | C     |
   | A | 0 | 0 | 1 + B |  i.e. extra penalty for putting A before C
   | B | 1 | 0 | 0 + B |  i.e. extra penalty for putting B before C
   | C | 0 | 1 | 0     |

Solving this problem with binary decision variables for each x[i][j], and constraints to enforce antisymmetry and transitivity, yields optimal decision variables of:

   x[A][B] = 1 (A before B)
   x[A][C] = 0 (C before A)
   x[B][A] = 0 (A before B)
   x[B][C] = 0 (C before B)
   x[C][A] = 1 (C before A)
   x[C][B] = 1 (C before B)

From these, summing the number of times each market is preferred over another gives an optimal order of:

C, A, B

• By scheduling C before A before B, the edges C ← A and A ← B incur no cost because their targets appear earlier than their sources.
• The preference towards having exporter markets early in the order keeps C at the front.
• As with any SCC, at least one pairwise violation is guaranteed. In this ordering, the only pairwise violation is between B and C, as C is solved before B, but B may consume C.

The resulting order replaces the original InvestmentSet::Cycle entry inside the condensed graph, providing a deterministic processing sequence for downstream logic.