sci.op-research

golabidoon@gmail.com wrote:
> Hi Paul,
>
> Thank you for the clarification, I now understand your idea. I googled
> about "complementarity constraints" and gained some shallow knowledge.
> It seems that problems with such constraints cannot be solved
> efficiently because of combinatorial flavor of the constraints.
>
> I think a naive approximation would be to write a complementarity
> constrain between u and a as a>=0, u>=0 a*u<=0 (or a*u> numerical reasons) and then replace a*x with convex envelope of the
> bilinear term.
>
> I also found a paper titled "A semidefinite programming heuristic for
> quadratic programming problems with complementarity constraints",
> which seems to be more efficient than my naive bilinear relaxation
> idea.
>
> I would be very thankful if someone who knows about complimentarity
> constraints could confirm or correct my understanding about hardness
> and lack of any efficient method for solving it.
>
> P.S. Enumeration of all posibilities is not an option due to the large
> number of variables and exponential growth of possibilities in # of
> variables.
>
> Thanks
>
> G.D.
>
>

Bob Daniel kindly reminded me that complementarity constraints are a
form of SOS1 constraint. So a solver that handles SOS1 can be used,
although that's still going to turn it into a partial enumeration
problem (and raises some questions in my mind about how the bounding
will be done).

It occurs to me that I may have missed something obvious. Going back to
your original question, why not just solve the inner problem (to get the
a_k), then treat them as parameters (freezing the values) and solve the
outer problem to get the x_i?

/Paul