Originally posted by: gangulo

Hi,

I have to solve a series of LPs with objective function zero (I just have to find a feasible solution which always exists), where at each iteration I have to add and remove around 20 rows before reoptimizing. I know that dual simplex is efficient in handling new constraints, but what happens if some rows are deleted? Q1: Does this destroy the current basis information? I tried deleting, reoptimizing, adding, reoptimizing. I also tried applying only primal reductions. At the end, by turning off the use of advanced information (that is, solving from scratch each time) and keeping the remaining parameters at default, I obtained a 5x-9x speedup. Q2: Do you have some advice for this type of reoptimization problems?

Thanks!

Adding constraints potentially makes the previous basis infeasible, in which case dual simplex pivots are usually (but not always) the preferred way to regain feasibility. Delete constraints keeps the previous basis feasible (but not necessarily optimal). Primal simplex might well be the fastest route to regain optimality in most cases where only deletions occurred, but given your objective function, that would not seem to be applicable here.

So my first choice would be to make all changes (deletions and additions), then reoptimize letting CPLEX choose the algorithm, and maybe compare that to the same thing mandating dual simplex as the algorithm.

Originally posted by: T_O

Paul,

I agree, that a basis (always) remains dual feasible if you add a constraint (and add the concering slack-variable to the basis). But I am wondering why a basis should (always) remain primal feasible if you remove a constraint. Can't the basis even become singular? If you remove a constraint, you have to remove a variable from the basis. Which variable has to be removed?

Best regards,
Thomas

Sorry, I'm running on fumes today and I skipped a key step. Let's assume that the constraint to be deleted contains a slack variable. If the constraint is nonbinding in the previously optimal solution, the slack will be basic. Deleting the slack from the basis yields a new valid basis. If the constraint is binding, though, you first have to reintroduce the slack variable into the basis (the step I skipped). Possibly excepting some pathological cases (I need to think more about the possible pathologies, which first requires a good night's sleep), you should be able to get the slack back into the basis with primal simplex pivots (for instance, by perturbing the objective function to richly reward slack in the constraint).

So the current basis remains a feasible solution when you drop the constraint but not necessarily a basic solution, unless the slack is basic; and if the basis needs repair, it can be done with primal simplex pivots. I don't think it typically requires a large number of extra pivots, but it's been close to 30 years since I actually messed with doing this myself.

Thanks for the catch, Thomas.

Paul

Originally posted by: EdKlotz

OK, so as Paul said, if you can ensure that the slacks for the rows you want to remove are basic, the resulting smaller basis remains primal feasible.    But, unless you know something very specific about your LPs, you probably cannot prove that.   So, you either need to pivot the slack into the basis yourself, or call functions do so.   If you are using CPLEX's C API, the CPXpivotin routine will do this.   However, it does assume that the constraints in question are inequality.    If you use the C++ or Java APIs, no function explicitly does this.   However, I had a look, and if you get delete the rows in any of the usual ways (e.g. IloModel::remove, IloRange.end(), IloLPMatrix.removeRows in Java), CPLEX internally will call the CPXpivotin routine, so it should work.   I don't think this is documented functionality.   However, I doubt it will change in future versions.

So, give this a try, and see if it works better.  

Regarding some of the other comments on this thread, they all sound on target to me.   If you delete constraints without ensuring the slacks of those constraints are basic, the resulting "basis" that CPLEX tries to use could be singular, or infeasible.   Based on experience, it would take only a slight change to this advanced "basis" to make it less helpful than starting from scratch.

Originally posted by: gangulo

Thanks for your reply, Ed.

In my case, all the constraints I add/delete are of the form ax >= 0, with row a having 0-1 entries only. Recently I realized that after each complete add-and-delete iteration, the feasible regions of the previous and current LPs are disjoint. Maybe that makes reoptimization harder.

Originally posted by: EdKlotz

In the context of the primal feasible region, the disjoint feasible regions might make reoptimization harder,p articularly if the feasible regions are disjoint because you are doing disjunctions on constraints (i.e. the constraint you remove and the constraint you add have the same left hand side, but a different sense and right hand side).   In that case, pivoting the slack into the basis, under nondegeneracy, will increase the infeasibility relative to the feasible region resulting from the delete-and-add operation to follow.    But, I'm less clear regarding how it would affect dual feasibility.

Overall, however, the deletion of constraints preserves primal feasibility but potentially compromises dual feasibility.   Then, the addition of other constraints does the reverse, preserving dual feasibility but potentially compromising primal feasibility.    So, together you lose both primal and dual feasibility, which potentially limits the effectiveness of any sort of advanced start.   I suppose you could try a two step approach where you first delete constraints, then reoptimize with the primal simplex method,   After that, add constraints and reoptimize with the dual simplex method.    This would avoid any primal or dual infeasibilities.   But, that first reoptimization would be done without any knowledge of the constraints you planned to subsequently add; that could make this approach worse than just solving the actual LP that follows the add and delete iteration from scratch.   Still, it might be worth a try just to see.

Originally posted by: gangulo

Thanks for your replies.

I tried Paul's suggestion of keeping warm-starts and letting CPLEX decide which solver to use, but it didn't work. Solving from scratch remains the best option in my case.

As Thomas pointed out, the current solution may not be a vertex of the new polyhedron after a constraint is removed. I would have to extract a smaller basis from the current one, but it looks nontrivial to me.

Originally posted by: VivekPeriaraj

I too have observed that starting from scratch was always faster instead of starting from a basis and repairing it. In my application, I was adding more columns in each iteration and the number of rows remained the same. However, the dual basis was different in the each of the cases. When started from a basis, I got better duals. They were better because it helped in faster convergence.

Regards,

Vivek.