Originally posted by: davidfk

Hi all,

I'm trying to delete a subset of constraints (IloRange objects) from a large IloRangeArray object. The context is: I solve an LP over many iterations and at some iterations I modify the model adding and deleting constraints. I need to keep my IloRangeArray object for other methods that use it as input (e.g. cplex.getDuals()).

• Using IloRangeArray[x].end() removes a particular constraint 'x', but not the handle. How can I remove the handles? What would be an efficient implementation?
• What are arguments for or against usingstd::vector<IloRange> instead of an IloRangeArray? For example: Is calling cplex.getDual() multiple times in a loop over the vector<IloRange> less efficient than calling cplex.getDuals() for an IloRangeArray object?

(A question similar to my first question was asked here https://www.ibm.com/developerworks/community/forums/html/topic?id=77777777-0000-0000-0000-000014396935 and it was suggested to either set the handles of removed constraints to a null pointer or create a new IloRangeArray object with only the remaining constraints each time some constraints have to be deleted)

Thanks!

In general, there is no efficient way to delete elements from the middle of an array since you always have to shift the remaining elements to the front. So deletion of elements is always an O(n) operation.

If you want to pass this array to getDuals() later on then setting the deleted slots to NULL will not work. However, you could create a dummy constraint or identify a constraint that you will never delete and put that into these slots. That might work. You probably want to clean up your array from time to time if a lot of elements have been deleted.

In case the order of elements in the array does not matter, another option would be swap the element to be deleted with the last element and then end() the new last element and shrink the array size by 1.

Calling getDuals() on an array is faster then calling getDual() in a loop.

Originally posted by: davidfk

Thanks Daniel. In my case I delete a rather large amount of constraints on rather few occasions, hence I would like to do the cleanup immediately. I do not care about the order of the constraints (I manually keep track).

Would the following be a valid way of deleting constraints? And not leak?

IloRangeArray constraints;
// Fill constraints with e.g. 5 IloRange objects 
[...]
// Delete element with index 2:
constraints[2].end();
// Copy last handle to constraints[2]
constraints[2] = constraints[constraints.getSize()-1];
// Decrease size of array:
constraints.setSize(constraints.getSize()-1);

May it be a problem that both constraints[2] and constraints[4] contain the same handle before decreasing the array size? Should I set the last slot to NULL before decreasing the array size?

And a last question: In case I remove many constraints (M constraints), does it matter performance-wise whether I decrease the array size by 1 multiple times or a single time by M?
 

I think the safest way to swap and delete the constraint is this ('del' is the index of the constraint to be deleted, 'last' is the index of the last constraint):

   constraints[del].end();
   std::swap(constraints[del], constraints[last]);
   constraints.setSize(last);

If the new size is smaller than the old one then setSize() only sets a field in the array object. Thus calling setSize(getSize()-1) M times or setSize(getSize()-M) once should not make a big difference. The latter of course saves some (inline) function calls. I would use whatever looks cleanest and most simple in your code. Decrementing the length of the array by 1 after each deletion is slightly less error-prone :-)