Adding constraints for a known solution causes out of bounds exception

Question

I have a linear optimization goal to Maximize EE+FF, where EE and FF each consist of some C and D.

With code I've written, I can get solver to find:

EE_quantity: 0, FF_quantity: 7

...but I know there to be another solution:

EE_quantity: 1, FF_quantity: 6

In order to validate user input for other valid solutions, I added a constraint for both EE and FF. So I added the EE_quantity == 0, FF_quantity == 7 in the code below, which is a runnable example:

SolverContext c2 = SolverContext.GetContext();
Model m2 = c2.CreateModel();
p.elements = elements_multilevel_productmix();

Decision C_quantity = new Decision(Domain.IntegerNonnegative, "C_quantity"); 
Decision D_quantity = new Decision(Domain.IntegerNonnegative, "D_quantity");
Decision EE_quantity = new Decision(Domain.IntegerNonnegative, "EE_quantity");
Decision FF_quantity = new Decision(Domain.IntegerNonnegative, "FF_quantity");
m2.AddDecisions(C_quantity, D_quantity, EE_quantity, FF_quantity);

m2.AddConstraints("production",
    6 * C_quantity + 4 * D_quantity <= 100,
    1 * C_quantity + 2 * D_quantity <= 200,
    2 * EE_quantity + 1 * FF_quantity <= C_quantity,
    1 * EE_quantity + 2 * FF_quantity <= D_quantity,
    EE_quantity == 0,
    FF_quantity == 7
);
m2.AddGoal("fixed_EE_FF", GoalKind.Maximize, "EE_quantity + FF_quantity");

Solution sol = c2.Solve(new SimplexDirective());             
foreach (var item in sol.Decisions)
{
    System.Diagnostics.Debug.WriteLine(
        item.Name + ": " + item.GetDouble().ToString()
    );
}

It seems that Solver Foundation really doesn't like this specific combination. Using EE_quantity == 1, FF_quantity == 6 is fine, as is using just EE_quantity == 0 or FF_quantity == 7. But using both, AND having one of them being zero, throws an exception:

Index was outside the bounds of the array.

What is going on under the hood, here? And how do I specify that I want to find "all" solutions for a specific problem?

Answer 1

(Note: no new releases of Solver Foundation are forthcoming - it's essentially been dropped by Microsoft.)

The stack trace indicates that this is a bug in the simplex solver's presolve routine. Unfortunately the SimplexDirective does not have a way to disable presolve (unlike InteriorPointDirective). Therefore the way to get around this problem is to specify the fixed variables differently.

Remove the last two constraints that set EE_quantity and FF_quantity, and instead set both the upper and lower bounds to be 0 and 7 respectively when you create the Decision objects. This is equivalent to what you wanted to express, but appears to avoid the MSF bug:

Decision EE_quantity = new Decision(Domain.IntegerRange(0, 0), "EE_quantity");
Decision FF_quantity = new Decision(Domain.IntegerRange(7, 7), "FF_quantity");

The MSF simplex solver, like many mixed integer solvers, only returns the optimal solution. If you want MSF to return all solutions, change to the constraint programming solver (ConstraintProgrammingDirective). If you review the documentation for Solution.GetNext() you should figure out how to do this.

Of course the CP solver is not guaranteed to produce the globally optimal solution immediately. But if you iterate through solutions long enough, you'll get there.