Using lpsolver.py

[MurtAlsa]

Thank you for your excellent work!

I have been using your library for a while. I am now trying to use the "lpsolver.py" for a particular dataset. However, I am unsure how to set the correct "bit-length." Can you elaborate more, please?

Best,

[lschoe]

Oh, thanks!

Indeed to find the right bit length may be a bit tricky, especially if the dataset is large and you cannot try out options quickly (although a binary search should kind of work). But maybe first an important sanity check: namely if your dataset has x=0 as a feasible solution, which means that b >=0 is assumed to hold.

If b>=0 and hence x=0 is feasible, then there are in principle "Hadamard style" bounds for the lengths of the integers that will arise during the computation, as a function of the bit length of the numbers in the dataset and of the number of variables and the number of constraints. Not sure if you want to look into this.

(One further thing maybe, if your datasets contains floats you need to scale these to integers.)

[MurtAlsa]

Hello @lschoe

Thank you so much for the details. I am comparing a dataset that I am randomly generate using both CPLX and lpsolver.py.

Is there any suggestion you could give on how to solve a linear system in a minimization sense? Since lpsolver uses the "maximizing c.x subject to A x <= b and x >= 0" When I tried to change the sign of the objective function. It finds length-n vector x of multiple zeros as the result. But using CPLX finds a more accurate solution. The results of both runs are attached for your reference.

If you are interested, I could share with you the dataset.

Best!

[lschoe]

Hi, you can indeed adapt the code to handle a minimization problem instead of a maximization problem.

Here are the minimal changes that you need to apply:

1. Replace function argmin_int() by its counterpart argmax_int().
2. Negate the top row of the tableau T right after its initialization by inserting T[0] = [-a for a in T[0]].
3. In the main loop of the Simplex algorithm, now call argmax_int() like this: p_col_index, maximum = argmax_int(T[0][:-1]).
4. And change the corresponding termination condition into: await mpc.output(maximum <= 0).

I think this solves the corresponding minimization problem. (The print statements and the verification also need to be adapted if you want those to be correct as well).

[lschoe]

Actually, from the above screen shots it looks like you have an LP problem with constraints of the form A x >= b with b >= 0. But that means that x=0 is not a feasible solution. For lpsolver.py an LP problem with constraints of the form A x <= b with b >= 0 is required to ensure x=0 is a feasible solution.

[MurtAlsa]

That's correct. I am trying to adopt the code to work on a dynamic constrains forms that any kind of inequalities LP problem ( Something like what's proposed in the CPLEX) Please provide any sugession.

[lschoe]

If x=0 is not known to be a feasible solution, you need to find a feasible solution using another run of the secure Simplex algorithm on a suitably defined LP problem instance. Sebastiaan de Hoogh worked out the details for secure initializations using several methods. See Section 3.3 "Implementations of the Simplex Initializations" of his PhD thesis Design of Large Scale Applications of Secure Multiparty Computation: Secure Linear Programming.

[MurtAlsa]

Hello @lschoe

Is there any way that I can set zero as starting initialized point. Since zero is a visible solution as per your explanation earlier. And I would like to take an advantage of that.

[lschoe]

Well, I think the problem is that x=0 is not a feasible solution in your case. You have the requirement A x >= b and therefore x=0 is feasible only if b=0, but that's not the case (b > 0) for your problem instance,

[MurtAlsa]

Yes, you are correct. I am now thinking of a different approach somehow. Is there any explanation of the gauss method you implemented or have you implemented any linear system of equations solver?

Thank you again.

[lschoe]

The MPyC demo lpsolver.py includes pointers to the papers on which it is based. To extend the program for the case that x=0 is not a feasible solution is covered in Sebastiaan de Hoogh's PhD thesis mentioned above. However, this material is quite advanced if you're not familiar with the Simplex algorithm and its variants.