Optimal function value when minimizing

[mateuszrycko]

I was solving the following:

var constraints = new Constraint[]
{
    new Constraint(new Fraction[] { 3, 2, 1, 0, 0 }, new Fraction(1), "="),
    new Constraint(new Fraction[] { 5, 1, 1, 1, 0 }, new Fraction(3), "="),
    new Constraint(new Fraction[] { 2, 5, 1, 0, 1 }, new Fraction(4), "="),
};

var function = new Function(new Fraction[] { 1, 1, 1, 1, 1 }, new Fraction(0), false);

according to readme file, optimal value should be found in result.Results.Last().FValue
In my case it's -4.5 when it should be 4.5. Variable values for optimal solution looks correct.

[Stukeley]

Hi. I think the problem might be in your "sign" parameters.

Since this is a linear programming problem, then it will be in the form of:

$$A_x <= b; x >= 0$$
which can be rewritten as (the code does it for you):
$$A_x >= -b; x>= 0$$
for certain problems.

You might also need to explicitly define variables to be greater than zero (if that's the case). For example:

new Constraint(new Fraction[] { 1, 0, 0, 0, 0 }, new Fraction(0), ">="),
// ...

Please try to update your signs to either ">=" or "<=", as well as the function definition for whether it is a minimization or a maximization problem, and test if it works that way.

[mateuszrycko]

Hi. I checked that sign "=" should be supported. Also, variables are never smaller than 0 so, it's not an issue either.
Actually, when calculating minimalization with "=" signs than variables are calculated correctly. Only optimal value is wrong, which I think is the small detail.

I found something more serious.
I tried calculating different things with this simplex and there is something fundamentally wrong with the method.
For example it's lost when changing a contraint "=" into 2 inequalities (">=" and "<=")

Also I tried to calculate very simple facilities location problem which simply gives values violating constraints. Just saying that I also tried different statements of constraints, signs, adding or removing some of the constraints. In summary, the algorithm in most of cases is lost and I was not able to make it work.

Below I'm pasting one of the examples which I think should find a solution, but it says it's unbounded. Also x4 can't be 1 if x1 is 0. This violates 5th constraint.

    var constraints = new Constraint[]
    {
        // each customer is assigned to exactly 1 facility
        new Constraint(new Fraction[] { 0, 0, 0,   1, 1, 1,   0, 0, 0,   0, 0, 0,   0, 0, 0 }, new Fraction(1), "="),
        new Constraint(new Fraction[] { 0, 0, 0,   0, 0, 0,   1, 1, 1,   0, 0, 0,   0, 0, 0 }, new Fraction(1), "="),
        new Constraint(new Fraction[] { 0, 0, 0,   0, 0, 0,   0, 0, 0,   1, 1, 1,   0, 0, 0 }, new Fraction(1), "="),
        new Constraint(new Fraction[] { 0, 0, 0,   0, 0, 0,   0, 0, 0,   0, 0, 0,   1, 1, 1 }, new Fraction(1), "="),

        // each customer might be assigned to facility only if it's opened
        new Constraint(new Fraction[] { -1, 0, 0,   1, 0, 0,   0, 0, 0,   0, 0, 0,   0, 0, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, -1, 0,   0, 1, 0,   0, 0, 0,   0, 0, 0,   0, 0, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, 0, -1,   0, 0, 1,   0, 0, 0,   0, 0, 0,   0, 0, 0 }, new Fraction(0), "<="),

        new Constraint(new Fraction[] { -1, 0, 0,   0, 0, 0,   1, 0, 0,   0, 0, 0,   0, 0, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, -1, 0,   0, 0, 0,   0, 1, 0,   0, 0, 0,   0, 0, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, 0, -1,   0, 0, 0,   0, 0, 1,   0, 0, 0,   0, 0, 0 }, new Fraction(0), "<="),

        new Constraint(new Fraction[] { -1, 0, 0,   0, 0, 0,   0, 0, 0,   1, 0, 0,   0, 0, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, -1, 0,   0, 0, 0,   0, 0, 0,   0, 1, 0,   0, 0, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, 0, -1,   0, 0, 0,   0, 0, 0,   0, 0, 1,   0, 0, 0 }, new Fraction(0), "<="),

        new Constraint(new Fraction[] { -1, 0, 0,   0, 0, 0,   0, 0, 0,   0, 0, 0,   1, 0, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, -1, 0,   0, 0, 0,   0, 0, 0,   0, 0, 0,   0, 1, 0 }, new Fraction(0), "<="),
        new Constraint(new Fraction[] { 0, 0, -1,   0, 0, 0,   0, 0, 0,   0, 0, 0,   0, 0, 1 }, new Fraction(0), "<="),

        // facilities has their capacity which can't be exceeded by assigned customers' demand
        new Constraint(new Fraction[] { 0, 0, 0,   50, 0, 0,   50, 0, 0,   75, 0, 0,   75, 0, 0 }, new Fraction(100), "<="),
        new Constraint(new Fraction[] { 0, 0, 0,   0, 50, 0,   0, 50, 0,   0, 75, 0,   0, 75, 0 }, new Fraction(100), "<="),
        new Constraint(new Fraction[] { 0, 0, 0,   0, 0, 50,   0, 0, 50,   0, 0, 75,   0, 0, 75 }, new Fraction(100), "<="),
    };

    var function = new Function(new Fraction[]
    {
        100, // cost of opening facility (x1)
        100, // cost of opening facility (x2)
        100, // cost of opening facility (x3)
        470, 474, 1976, // cost of the 1st customer being assigned to one of the facilities (x4 - x6)
        471, 475, 1977, // cost of the 2nd customer being assigned to one of the facilities (x7 - x9)
        472, 477, 1978, // cost of the 3rd customer being assigned to one of the facilities (x10 - x12)
        677, 673, 829,  // cost of the 4th customer being assigned to one of the facilities (x13 - x15)
    }, new Fraction(0), false);

[Stukeley]

Let me rephrase - this implementation does not support the "=" sign and the only two options are either ">=" or "<=", which could be why you are not getting a solution for your second problem and the first problem as well (if it cannot be rewritten using "greater than" and "less than" only).

If you do have tasks that require the use of the "equal to" constraint, then unfortunately I think this code will not help you solve them.

[mateuszrycko]

Thanks for explanation, however I think what I am trying to share is misunderstood.

1. The below code is valid for sure

var constraints = new Constraint[]
{
    new Constraint(new Fraction[] { 3, 2, 1, 0, 0 }, new Fraction(0.99999), ">="),
    new Constraint(new Fraction[] { 3, 2, 1, 0, 0 }, new Fraction(1.00001), "<="),
    new Constraint(new Fraction[] { 5, 1, 1, 1, 0 }, new Fraction(2.99999), ">="),
    new Constraint(new Fraction[] { 5, 1, 1, 1, 0 }, new Fraction(3.00001), "<="),
    new Constraint(new Fraction[] { 2, 5, 1, 0, 1 }, new Fraction(3.99999), ">="),
    new Constraint(new Fraction[] { 2, 5, 1, 0, 1 }, new Fraction(4.00001), "<="),
};
var function = new Function(new Fraction[] { 1, 1, 1, 1, 1 }, new Fraction(0), false);

Variables found looks correct: 0, 0.500005, 0, 2.499985, 1.499965

Solution found seems correct, although it's wrong that it's negative: -4.499955 (this is what I mentioned in my first post)

2. Equality sign "=" DO work correctly. Yet, has the same issue with optimal value being negative

var constraints = new Constraint[]
{
    new Constraint(new Fraction[] { 3, 2, 1, 0, 0 }, new Fraction(1), "="),
    new Constraint(new Fraction[] { 5, 1, 1, 1, 0 }, new Fraction(3), "="),
    new Constraint(new Fraction[] { 2, 5, 1, 0, 1 }, new Fraction(4), "="),
};
var function = new Function(new Fraction[] { 1, 1, 1, 1, 1 }, new Fraction(0), false);

Solution found: 0, 1/2, 0, 5/2, 3/2 Optimal value: -9/2

3. When provided another constraints which I think are valid too, it gives wrong solution. It should give the same solution as for the above cases, but it's lost.

var constraints = new Constraint[]
{
    new Constraint(new Fraction[] { 3, 2, 1, 0, 0 }, new Fraction(1), ">="),
    new Constraint(new Fraction[] { 3, 2, 1, 0, 0 }, new Fraction(1), "<="),
    new Constraint(new Fraction[] { 5, 1, 1, 1, 0 }, new Fraction(3), ">="),
    new Constraint(new Fraction[] { 5, 1, 1, 1, 0 }, new Fraction(3), "<="),
    new Constraint(new Fraction[] { 2, 5, 1, 0, 1 }, new Fraction(4), ">="),
    new Constraint(new Fraction[] { 2, 5, 1, 0, 1 }, new Fraction(4), "<="),
};
var function = new Function(new Fraction[] { 1, 1, 1, 1, 1 }, new Fraction(0), false);

Solution not found - Unbounded: 2, 0, 0, 0, 0

[Stukeley]

I did some testing and it seems like there is indeed an issue, particularly with problem number 1 that you posted. I will take a look and try to identify the problem as to why the result is incorrect.

However, to reiterate the later part of your message - the equality sign does not work, it is not explicitly handled, and if you get any result by specifying it, it's either going to be wrong, or it's going to be right by accident. There are no plans to add support for it, as this project is not really meant to target such problems anyway.

Edit: I took a closer look at point number 3, and it is the same as above - it will not work because there is no equal sign, and specifying constraints that (something) is both greater than and less than at the same time will not give the right results, if any.