[Coin-discuss] Suggestions on how to go about tuning?

[Tobias Achterberg]

Hi all,

> It occurs to me that sometimes it might be important to be able
> to distinguish between constraints that define the problem
> and constraints that can be inferred or can be accepted.
> 
> In the case at hand, at least one solver runs faster and gets
> the right answer with all variables specified as integer.
> 
> 'Twouldn't be a surprise if some solver ran faster with
> only the original integer variables declared integer.
> 
> A solver that knew which kind it was could accept or reject
> constraints that didn't define the problem accordingly.
> Better yet, it might use a strategy that enforces or relaxes
> a non-problem-defining constraint whichever is more efficient.
> 
> In the case at hand, a solver might employ a rounding heuristic
> that did not enforce integrality on all the variables,
> but it might nevertheless use Gomory fractional cuts,
> which require integer variables.

Btw: In SCIP, I call those variables (which are automatically integral whenever all integer 
variables are integral) "imlpied integers". The user may declare variables to be "implied integers" 
which means that presolving, cutting plane generation and so forth can exploit the integrality, but 
heuristics or branching don't need to enforce the integrality. One could think about detecting the 
"impliedness" of the integrality in presolving. However, this is a bit dangerous, because this would 
remove the variable from the branching decisions....

For example, if there is a set partitioning constraint

x1 + ... + xn == 1

with xi binary, one could easily detect one of the variables, e.g., xn, to be "implied integer". 
However, it might be that a branching on xn is the best thing you can do to split your problem into 
two pieces... so, in these cases I wouldn't declare a variable to be implied.

But on the other hand, if you have a model like the following:

min y
ax <= y
bx <= y
cx <= y

x binary (a integer)

it is clear that y will always take integer values in a feasible solution. Here, it can indeed be 
beneficial to detect the "implied integrality" of y. At least, one can conclude that the objective 
is always integral, such that the current cutoff bound can always be reduced by 1.


Best,  Tobias