Sign Error on Dual values for >= Constraints

[PaulDL-RS]

Description: When using the method dual on a SolutionWithDual with a constraint expressed with >=, the returned dual value has the opposite sign of the one expected

I noticed this error using both Highs and Clarabel Solvers, the only ones implementing SolutionWithDual

Code Example:

The error is on constraint 3

use good_lp::{
    clarabel, constraint, highs, variable, DualValues, ProblemVariables, Solution,
    SolutionWithDual, SolverModel,
};

fn main() {
    let mut problem = ProblemVariables::new();
    let vars = problem.add_vector(variable().min(0), 4);
    let z = 4 * vars[0] + 6 * vars[1] + 7 * vars[2] + 8 * vars[3];
    let cst1 = constraint!(2 * vars[0] + 3 * vars[1] + 4 * vars[2] + 7 * vars[3] <= 4600);
    let cst2 = constraint!(3 * vars[0] + 4 * vars[1] + 5 * vars[2] + 6 * vars[3] <= 5000);
    let cst3 = constraint!(vars[3] >= 400);
    let cst4 = constraint!(vars[0] + vars[1] + vars[2] + vars[3] == 950);
    let mut problem = problem.maximise(z.clone()).using(highs);
    let c1 = problem.add_constraint(cst1);
    let c2 = problem.add_constraint(cst2);
    let c3 = problem.add_constraint(cst3);
    let c4 = problem.add_constraint(cst4);
    let mut solution = problem.solve().unwrap();

    for (idx, var) in vars.iter().enumerate() {
        println!("x{} = {}", idx, solution.value(*var));
    }
    let dual = solution.compute_dual();
    println!("shadow price cst1: {}", dual.dual(c1));
    println!("shadow price cst2: {}", dual.dual(c2));
    // The issue seems to only be for >= constraints
    println!("shadow price cst3: {}", dual.dual(c3)); // It should be -2
    println!("shadow price cst4: {}", dual.dual(c4));

    println!("objective value: {}", solution.eval(&z));
}

Output

x0 = 0
x1 = 400
x2 = 150
x3 = 400
shadow price cst1: 1
shadow price cst2: 0
shadow price cst3: 2 // Here should be -2
shadow price cst4: 3
objective value: 6650

[lovasoa]

I think good-lp just forwards the values returned by the solvers here. This is probably not the right place to open the issue. Except if you spot a place where we misinterpret the solvers' output.

[PaulDL-RS]

If I am not mistaken, good_lp transforms the constraint a x >= b into -a x <= -b when generating the model for the solver but does not seems to account for that this transformation was done when querying the dual values from the solver solution resulting in the incorrect sign.

I solved the same model using Highs directly and obtained the expected result of -2 for the third constraint

Here is my Highs model

use highs::*;
fn main() {
    // Row formulation
    let mut pb = RowProblem::new();
    let x1 = pb.add_column(4., 0..);
    let x2 = pb.add_column(6., 0..);
    let x3 = pb.add_column(7., 0..);
    let x4 = pb.add_column(8., 0..);

    pb.add_row(..=4600, [(x1, 2.), (x2, 3.), (x3, 4.), (x4, 7.)]);
    pb.add_row(..=5000, [(x1, 3.), (x2, 4.), (x3, 5.), (x4, 6.)]);
    pb.add_row(400.., [(x4, 1.)]);
    pb.add_row(950..=950, [(x1, 1.), (x2, 1.), (x3, 1.), (x4, 1.)]);

    let solved = pb.optimise(Sense::Maximise).solve();
    assert_eq!(solved.status(), HighsModelStatus::Optimal);
    let solution = solved.get_solution();
    for (idx, var) in [x1, x2, x3, x4].iter().enumerate() {
        println!("x{} = {}", idx, solution[*var]);
    }
    println!("Dual values: {:?}", solution.dual_rows());
}

[lovasoa]

Oh, yes that's it, you are correct! That's a bug 🐛! Pull request welcome!