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

[Michael Hennebry]

On Sun, 4 Jun 2006, Tobias Achterberg wrote:

> Hi all,

[I wrote]
> > 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.

I should have been more clear here.
There are three categories of constraints:
Problem-defining constraints are those
necessary for defining the feasible set.
There are also constraints that can be inferred
and therefore are not mathematically necessary
to define the feasible set, but might be useful.
Cutting planes are an example.
In the case at hand, some integrality constraints are also.
The third category chops off some of the feasible set.
If it doesn't chop off too much, whether to enforce it
might depend on whether doing so would speed up the search.
In effect, the optimization problem is transformed into something like this:

Given S subsetof T and function c,
find y in T
such that for all x in S, c(y)<=c(x)

The solver would be allowed, but not
required to chop off anything in T-S.

If, for example, S==T intersection Z^n,
we can use Gomory's IP cuts without
insisting that y be all-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....

In principle, a solver might detect that a declared integer
would be integer even if it were not delcared integer or
that a declared continuous variable will be integer.

> 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.

It's not obvious that an implied integer would have
to be removed from branching consideration.
One might just remove it from a formula used to measure
how close a solution is to integrality.

In the case of a set partitioning constraint, just deciding which
variable to declare an implied integer is interesting.

-- 
Mike   hennebry at web.cs.ndsu.NoDak.edu
"it stands to reason that they weren't always called the ancients."
                                                      --  Daniel Jackson