[Coin-discuss] constraint deletion/compression/modification

[Lou Hafer]

Folks,

	Well, meet a solver that doesn't work that way. It's one of the
things I've been grappling with in the OSI interface for dylp.

	Dylp does dynamic constraint system modification as it runs, so I
wanted an underlying constraint structure that would support that. The result
is a row- and column-linked structure that moves constraints or variables to
fill holes in the index space left by deleted constraints. (I.e., if you have
10 constraints, and you delete constraint #5, constraint #10 is re-indexed to
be constraint #5.) The attractive aspect is that you get O(1) addition and
deletion. Keeping track of indices isn't really any harder than if you
compress all constraints after the hole. The solver deals with it
internally.

	In terms of associating duals with constraints, the convention is
that the solver returns a structure with three vectors: the active
constraints, the duals for those constraints, and the basic variables for
those constraints.

	What has been awkward in the OSI interface is that the test suite
enforces the expectations that Laci described for behaviour when constraints
are added or deleted. We ended up writing a special constraint deletion
routine that has the expected behaviour. The test suite also disallows
constraint system modification. dylp normally converts all >= constraints to
<= as it reads the mps file, and also deletes empty constraints (you'd think
these wouldn't happen, but they do).  In order to get an interface that
passes the test suite, I ended up suppressing the deletion of empty
constraints, and wrote a wrapper to convert >= to <= and back again on either
side of the solver call.

	The difficult aspect in deletion is exactly this problem of tracking
constraints. It really gets bad when you start adding new constraints, which
then reuse the index space. In general I don't see any way around it except
to tag constraints with a hash id. But isn't this the function of a cut
pool?

	I do think that OSI should incorporate some sort of support for
maintaining the MPS names. It'd make it much easier to produce meaningful
names if we decide to instrument the code for statistics or debugging.

							Lou