PrimalSimplex outputs infeasible, while there should be a solution

[iainnz]

PrimalSimplex outputs infeasible, while there should be a solution

[IainNZ]

Let me just make sure I understand your problem.
You have 3 variables, 4 constraints, 1 of which is redundant. The constraints are:
x1 = 1
x2 = 1
x1+x2+x3 = 1

This problem is infeasible as (x1+x2) = 2 so x3 would have to be -1 to satisfy this problem.

I think there is something wrong with your modelling. One way to do a bipartite matching would be to have a variable for each pair (i,j) that have an arc between them. Then the constraints are that for each node i, the sum across all nodes that this node is connected j is less than or equal to 1

e.g.
sum_{j such that i and j are connected} x_ij <= 1 for all i on one side of the graph
x_ij

Unfortunately SimplexJS only handles equality constraints, so you'll need to add a slack variable s_i to each constraint, e.g.

sum_{j such that i and j are connected} x_ij + s_i == 1
s_i >= 0
x_ij >= 0

[tr3ddy]

Thank you for your advice.
I assume to get a maximum bipartite matching I have to model the cost-vectors with -1 for all x and with 0 for the slack variables?

So I modelled the problem above again:

var test = new Object();
    test.A = [[1, 0, 0 ,1, 0, 0, 0],
              [1, 0, 0, 0, 1, 0, 0],
              [0, 1, 0, 0, 0, 1, 0],
              [1, 1, 1, 0, 0, 0, 1]];
    test.b = [1, 1, 1, 1];
    test.c = [-1, -1, -1, 0, 0, 0, 0];
    test.m = 4;
    test.n = 7;
    test.xLB = [0, 0, 0, 0, 0, 0, 0];
    test.xUB = [Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity];

This works pretty good and results in x = (0,1,0) and s = (1,1,0,0).

[IainNZ]

Can you describe the graph that you are trying to model with those constraints?

[tr3ddy]

There are 4 nodes and 3 edges. One node is connected to each other:

a - b
  - c
  - d

[tr3ddy]

Oh, there is a little "typo" in the example above. The JavaScript-obejct should look like that:

var test = new Object();
    test.A = [[1, 0, 0 ,1, 0, 0, 0],
              [0, 1, 0, 0, 1, 0, 0],
              [0, 0, 1, 0, 0, 1, 0],
              [1, 1, 1, 0, 0, 0, 1]];
    test.b = [1, 1, 1, 1];
    test.c = [-1, -1, -1, 0, 0, 0, 0];
    test.m = 4;
    test.n = 7;
    test.xLB = [0, 0, 0, 0, 0, 0, 0];
    test.xUB = [Infinity, Infinity, Infinity, Infinity, Infinity, Infinity, Infinity];

Results are x = (0,0,1) and s = (1,1,0,0).

[IainNZ]

Oh I see, right. Looks good then! Let me know if you have any other issues.