[SCIP] search direction from custom constraint function

[Marc Pfetsch]

Hi Brannon,

it seems that I do not understand your problem enough to help you, but 
here are some thoughts ...

On 20/10/2023 17:24, Brannon King wrote:
> Suppose I want to solve a problem of this form:
> min z : z >= g_i(Y) for all i, Y in D
> where Y is a binary matrix and z a real number.

So, this is a "robust" problem: the only variable is z and it should 
satisfy the constraints for all i and Y. Thus, in order to deal with 
this problem you need to be able to compute a worst-case Y, i.e., one 
that maximizes g_i(Y) for each i. But then you would just do this and 
take the maximum, since the Ys are not coupled across the i's.

> The problem: I can represent g as a linear function but not for all
> possible values of Y. (A SIP problem requires that the constraint be
> valid for all possible values of Y.) In other words, I need to see the
> Y to make a few adjustments before returning from g. The restrictions
> for Y in D are quite severe, significantly limiting the space of Y,
> but they don't provide any direction to the objective.

But I assume that you can represent D as a MIP or MINLP or something 
similar?

I am not sure, I understand what you mean by "direction to the 
objective" ...

> It seems that I could build a constraint handler to execute g.
> However, this seems like it would be slow, as it would not provide any
> search direction either, and that it would have to execute g on a huge
> number of possible Y values. How can I make this be performant? Is
> there some other values I can set in the constraint handler to give
> further clues about the search direction?

I am pretty sure that just evaluating g will not be enough. You either 
need a MINLP/MIP representation of g, so you can optimize over it or 
some algorithm that computes the worst case (see above). If g would be 
convex, then you can run a generalized Benders algorithm.

> I can compute g for fractional/relaxed values of Y (helpful?), or I
> could compute it only for feasible MIP solutions. I can set minimum
> bounds on z rather than adding constraints, which seems useful.

I suppose that any feasible Y gives you lower bounds on z.

Best

Marc