Discrete optimization

Our Journey with CP-SAT in Energy Trading

Jorge Rodriguez Vecino & Narve Sætre

Who?

A typical day @ NODES™

Greedy algorithm

                  %%{init: {'theme': 'dark', 'themeVariables': { 'darkMode': true }}}%%
                  graph LR
                      subgraph Buyers
                        B1[10 Wood]
                      end

                      subgraph Sellers
                        S1[1 Steak @ 3 Wood]
                        S2[1 Steak @ 5 Wood]
                        S3[1 Steak @ 6 Wood]
                      end

                      classDef highlighted stroke:#f00,stroke-width:4px;
                      B1 -- "Buys 1" --> S1
                      B1 -- "Buys 1" --> S2
                      B1 -- "Buys 1/3" --> S3
                

Greedy algorithm

                
    // Sort sell orders by lowest price
    var sortedOrders = sellOrders
        .Where(s => s.Price <= buy.Price)
        .OrderBy(p => p.Price);

    // Match orders until buy order is completed
    var matches = new List<(sellId, quantity)>();
    var quantityRemaining = buy.quantity;
    foreach (var sell in sortedOrders)
    {
        var matchQuantity = Math.Min(sell.Quantity, quantityRemaining);
        matches.Add(sell.Id, matchQuantity);
        quantityRemaining -= matchQuantity;

        if (quantityRemaining == 0)
            break;
    }
                
            

Greediness - not always good

Branch-And-Bound

                    %%{init: {'theme': 'dark', 'themeVariables': { 'darkMode': true }}}%%
                    flowchart TD
                        A["**Start**
                            Coins: 1500
                            Meat: 0KG
                            Bound: 5.66KG"] --> B1["**Take Seller 1**
                            Coins: 1100
                            Meat: 2KG
                            Bound: 5.66KG"]
                        A --> B2["**Skip Seller 1**
                            Coins: 1500
                            Meat: 0KG
                            Bound: 4.33KG"]

                        B1 --> C1["**Take Seller 2**
                            Coins: -100
                            Meat: -
                            Bound: -"]
                        B1 --> C2["**Skip Seller 2**
                            Coins: 1100
                            Meat: 2KG
                            Bound: 3KG"]

                        B2 --> C3["**Take Seller 2**
                            Coins: 300
                            Meat: 4KG
                            Bound: 4.33KG"]
                        B2 --> C4["**Skip Seller 2**
                            Coins: 1500
                            Meat: 0KG
                            Bound: **1KG**"]

                        C3 --> D5["**Take Seller 3**
                            Coins: -500
                            Meat: -
                            Bound: -"]
                        C3 --> D6["**Skip Seller 3**
                            Coins: 300
                            Meat: 4KG
                            Bound: 4KG"]

                    class C1,D5 red
                    class D6 green
                    class C4,C2 pruned
                

What we tried

• To be smart
• Split the problem into easier to tackle sub-problems
• Use heuristics to find feasible solutions to the sub-problems
• Use heuristics and branch-and-bound to find a good global solution

What it led to

• Great performance for easy optimization cases
• Great performance for medium optimization cases
• Splitting the problem at the wrong place led to impossible heuristics for some cases, which made optimization impossible.

What now?

Show me the code!

Using C# and Google OR-Tools

                
    using Google.OrTools.Sat;

    var model = new CpModel();
                
            

Define decision variables

                
    var intVariable = model.NewIntVar(0, 10, "intVar");
    var boolVariable = model.NewBoolVar("boolVar");
                
            

                
    var cells = new IntVar[9, 9];

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cells[i, j] = model.NewIntVar(1, 9, $"cell_{i}_{j}");
        }
    }
                
            

Define model constraints

                
    model.Add(x + y <= 15).OnlyEnforceIf(boolVariable);
                
            

                
    for (int i = 0; i < 9; i++) {
        var row = new IntVar[9];
        for (int j = 0; j < 9; j++) {
            row[j] = cells[i, j];
        }

        model.AddAllDifferent(row);
    }
                
            

Running the solver

                
    var solver = new CpSolver();
    var status = solver.Solve(model);

    if (status == CpSolverStatus.Optimal || status == CpSolverStatus.Feasible)
    {
        Console.WriteLine(@$"Solution found: x = {solver.Value(x)},
        y = {solver.Value(y)},
        condition = {solver.Value(condition)}");
    }
    else
    {
        Console.WriteLine("No solution found.");
    }
                
            

Insights from NODES

Final words

Model optimization

• Reification:
  • Link a boolean variable to the truth of a constraint.
  • Example: quantityOrderA > 0 => matchedOrderA = 1
• Global constraints:
  • Using built-in methods such as AllDifferent helps the solver deduce better.
• Breaking symmetry:
  • Identify and eliminate equivalent solutions
  • Example: For identical sell orders, enforce matching in a specific order

Beyond constraint programming

Solvers can be used for more than just constraint programming:

• Mixed Integer Programming (MIP)
• Linear Programming (LP)
• and other kinds of problems

How to use solvers?

There are many libraries, open-source and closed-source, for most programming languages.

In Java there is even a standard: JSR 331: Constraint Programming API.

Thank you!