Fixing structural columns for column relaxations

[spoorendonk]

I am solving a fixed charge multi commodity flow problem and need to branch on the design variables.

See #121 for first issue on branching.

After resolving that, there are a too aggressive fixing of generated columns when looking at relaxations. A relaxed column is a column that allow cycles on the multi-commodity flow path. This Is also super common in vehicle routing problems. Hence we can construct columns where original space x variables appear multiple times giving a coefficient > 1 even if the variable has ub = 1. Clearly this cannot be part of the optimal solution but can be part of a relaxation.

The problem is in https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompAlgo.cpp#L2414-L2416

with the call to

https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompVar.cpp#L26

and in particular

https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompVar.cpp#L42-L52

where the xj value is actually the coefficient set in

https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompVar.cpp#L58-L69

That is, if ub = 1 and coef > 1 the column is fixed to 0 which is not correct.

I guess it is assumed that the coefficient can never exceed the variable ub - not sure why? Because of the convexity constraints?

Fixing only if ub = 0 and coef > 0 solves the problem in my case, but I am not sure in the general case.

[tkralphs]

I guess I know what you mean, but not sure. Basically, you may relax the restriction that an arc can only be used once in a path/cycle. Mathematically, though, the convexity constraint would not allow any column where the coefficient is above the upper bound to be part of any feasible solution. The multipliers are all non-negative so I don't see how such a column could be used in the solution unless there were negative coefficients in some other columns. Hmm, it's a good question whether we assume non-negativity of the column coefficients. Certainly, in your setting, I don't think there could be, but in general...

So when you say that your fix solves the problem, you mean that there is a case where such a column is used in the relaxed solution?

[spoorendonk]

Relaxed columns will not be part of a feasible IP solution but can be part of the LP relaxed solution.

For VRP all coefficients are positive (set partition constraints) but for instance 2-cycle elimination routes allows routes with cycles larger than two and are used to converge faster. At some point only the elementary routes are left for the set partition problem to be IP feasible.

So yes, relaxed columns can be part of the LP relaxed solution.

I guess the problem with the fixing will only occur if you solve the sub problem with your own algorithm that solves the relaxation sup problem. When setting up the entire problem in DIP as is I don’t think it will happen.

Could it be a parameter then? Column fix strategy 1 and 2?

[tkralphs]

Yes, I'm familiar with the techniques you're talking about. I was being a bit stupid, but have now rebooted my brain and it makes sense.

In principle, the bound constraints could actually be relaxed in the subproblem (that is effectively what you're suggesting), but the modeling of that is not directly supported at the moment. You could achieve it by making the tighter bound constraints explicit constraints and the looser ones the implicit bounds. then you could relax the tighter bound constraints in the usual way. This would also address the issue.

I guess I would prefer introducing some way to be able to relax the bound constraints in the subproblem, since that would be cleaner and would make the whole framework more flexible. I can think of some different ways of doing it, not sure what is best. For examples, one could define a relaxation in terms of an entirely new RHS and vectors of of upper and lower bounds on the variables. Then by specifying infinite RHS for some constraints, you get the current behavior, but would also be able to relax any constraint (including bounds) partially. What do you think?

[spoorendonk]

Do I understand you correctly if your suggestion is to somehow add a relaxed version of the col and row bounds in

https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompConstraintSet.h#L30-L41

And then use the relaxed col bounds for fixing master variables? And be able to drop constraints in the subproblem by setting the row bounds to +/- infinity?

When checking feasibility one should take into account the real bounds then, I guess. In https://github.com/coin-or/Dip/blob/b0e1f03ee3cb6656a52ff6b7e86c1f8fbd708cd2/Dip/src/DecompAlgo.cpp#L6148 perhaps. I think branching wrt. the non-relaxed bounds would ensure that you end up with the optimal IP solution to the non-relaxed problem.

Not sure how to handle relaxed constraints? In this cases I think you could end up with IP feasible solutions for the relaxed problem that, if you use the col bounds procedure above would be accepted as the optimal solution. Would it be enough to just check against the constraints when testing IP feasibility?

[tkralphs]

I've only spent a little bit of time poking back into this and the picture is not perfectly clear to me yet. At the moment, it doesn't seem to me that anything needs to be added. We just need to allow the bounds on variables in the relaxations to be different from the bounds on the same variables in the core, which I think may actually already be the case. It can certainly already be the case when solving the subproblem yourself because you can interpret the constraints as you like (and just ignore variable bounds if you want). I recall that there used to be check to make sure that the solutions returned by the user were actually feasible for what the user said were the subproblem constraints, but I think that's been removed. Given that the submodels are created and stored separately with their own variable bounds, I guess allowing this even when solving the subproblem as an MILP should be easy.

So now that I'm thinking through this again, the problematic check just seems to be a bug even with the current version of the code. Currently, If the subproblem is solved as an MILP, then either

• the bounds on the variables should be the same as in the master (or possibly tighter, if tightened by branching), in which case the check is not needed anyway, or
• the bounds are not the same, but then they must have been intentionally relaxed by the user, so the check is actually wrong.

I'm not sure if the bounds can be relaxed when solving the subproblem as an MILP, but I don't actually see why this cannot be done at least through the C++ interface somehow. If you just create the sub model from a constraint set with different bounds on the variables, this should be fine.

I don't actually see right now why we can't just delete the check in master on whether coefficients exceed variable bounds. I can't see why this would be needed. Of course, you do need to check variables bounds in isIPFeasible().

Does this makes sense?

[spoorendonk]

I guess the purpose of the check is fix columns that have changed/are invalid because of branching (or bound propagation?). I am unsure if zero fixing is a special case when talking about relaxed columns?

In my case I am only setting the activeColumns indices in the subproblem models. The rest is left to default. So the subproblem bounds are free in my case.

I am thinking that in this particular check the bounds check should be wrt subproblem bounds otherwise columns will be generated again which is what is happening now.

[tkralphs]

Hmm, yes, looking a bit deeper into it, checking for violation of branching constraints does seem to be the motivation, but if branching constraints are the issue, then it may not be that easy to tell what bounds to check against. If branching is enforced in the master, then master bounds are relevant, but only the bounds imposed by branching, not other bounds. And the user may still wish to generate columns violating those bounds. In this case, the branching constraints are imposed in the master anyway, so algorithmically, I guess it doesn't matter much if columns violating those bounds are included. A question: are the columns you want to add that violate bounds ones that violate the original variable bounds or a bound imposed by branching? I suppose that either could be possible and that is what seems a bit tricky here. It's not actually clear at all what bounds the user intends to be checked.

Another thing that's not clear to me is that this removal of columns seems to only happen when setting up the node. I don't see anywhere that columns are purged within the node processing loop. So is it just that a column generated at node A is being purged when switching to node B and then re-generated at node B (one time)? Or is the code getting into an infinite loop? I can't see how that's possible at the moment.

There seems to be a tradeoff in which columns to purge. I suppose any column that is purged may end up being re-generated. It seems to make sense to check bounds when setting up the subproblem, but perhaps limiting the check only to bounds that have been changed due to branching makes sense. Even then, we may purge a column that is later re-generated.

This is all related also to one of my long-term goals, which is to be smarter about setting up the subproblems. Rather than just taking the columns from the previous node, we should think about setting up from scratch using some kind of global column pool as an initial generator.

Thoughts?

[tkralphs]

Interestingly, I just noticed #91 from Matt, which seems to address this same issue. I guess we'll be able to close that one, too, once we resolve this.

[spoorendonk]

A question: are the columns you want to add that violate bounds ones that violate the original variable bounds or a bound imposed by branching?

The relaxed columns violate the original bounds, but the check is not made until after the root node. The original ub is 1 and relaxed columns may have coef > 1.

So is it just that a column generated at node A is being purged when switching to node B and then re-generated at node B (one time)? Or is the code getting into an infinite loop?

Columns are regenerated but not added to the problem the second time because the first version exist with the same string hash. In theory, this is OK since these columns cannot be part of an optimal solution. However, it may lead to unwanted behavior since the solveRelaxed function suddenly do not return any columns (except the regenerated once) and branching is prematurely initiated.

This is all related also to one of my long-term goals, which is to be smarter about setting up the subproblems. Rather than just taking the columns from the previous node, we should think about setting up from scratch using some kind of global column pool as an initial generator.

From a simplex point of view I guess that starting with the current column set is not too bad. Non-basic variables could maybe be removed/changed in a smarter way. As far as I can read the code there is not global column pool at the moment right?

[tkralphs]

OK, so now the picture is a little clearer. If I understand correctly, the columns with bound violations are getting their upper and lower bounds set to 0 (rather than being completely removed), so they are still present in the RMP. They are then getting re-generated, but the fact that they are already in the RMP is detected and they are not added again. So it seems that at the very least, the duplicate check shouldn't apply to columns that are fixed to zero. That is a bug. They should be allowed to be "re-added," which would amount to restoring their column bound back to 1. Effectively, they should be treated as if they are not present in the RMP to being with, since fixing them to zero is meant to effectively remove them (but we just don't want to go to the expense of actually removing them).

The question of which columns to remove to being with is a separate issue that is not very clear. But as long as any column that is "removed" is allowed to be re-added (which can happen), then this shold fix the issue you're seeing for now at least. Am I right?

As far as I remember, there is no global column pool, just a pool of columns waiting to enter the RMP.

[spoorendonk]

Re-adding would be OK from a feasibility stand point. Although not super efficient. Perhaps playing with the subproblem bounds as you suggested can also be a workaround.

But for now, this check

https://github.com/coin-or/Dip/blob/cf4f848a4987e3a4b606cf4c7c5c788c6262b638/Dip/src/DecompVarPool.cpp#L150-L164

should not be done on columns fixed to zero. Or more precisely we should unfix the existing column ub to 1?

[tkralphs]

Yes, exactly, that is my current understanding.