sci.op-research

Peter wrote:

>
> As you said we have the following problems:
>
> (P) z(y) = min {d'x | Dx >= e + Hy}
> (P') min {c'y | Ay >= b, z(y) >= k}
> Dual: z(y) = max {u'e + u'Hy | u'D <= d', u >= 0}.
> min {c'y | Ay >= b, u'D <= d', u >= 0, u'e + u'Hy >= k}
>
> So, we have a nonlinear term u'e + u'Hy in the dual problem and in
> the constraint
> u'e + u'Hy >= k. If the variable y turns out to be binary, is there
> any way to get rid of it in the dual problem and in that constraint
> (with respect to the fact that y can take a value of only 0 or 1) so
> that have a linear problem?
>

You have to keep y in the dual, but with a bit of luck you can linearize
the corresponding constraint in the merged problem. The key is knowing
an upper bound for every dual variable u_i.

For notational simplicity, suppose that H is diagonal, so that each y_i
either relaxes or tightens a single constraint of (P). The nonlinear
constraint can be rewritten

sum_i h_i*u_i*y_i >= k - sum_i e_i*u_i.

Let U_i be a valid upper bound for u_i. Now introduce a new continuous
variable w_i along with the following constraints:

0 <= w_i <= U_i*y_i
-U_i*(1 - y_i) <= w_i - u_i <= 1 - y_i.

Both constraints are linear. If y_i = 1, the second constraint forces
w_i = u_i (= u_i*y_i) and w_i = u_i, y_i = 1 satisfies the first
constraint. If y_i = 0, the first constraint forces w_i = 0 (= u_i*y_i)
and the second constraint becomes -U_i <= -u_i <= 0, which is satisfied
by any u_i. So we can now rewrite the nonlinear constraint as

sum_i h_i*w_i >= k - sum_i e_i*u_i

and the problem is linear.

Something similar works for a more general H, using new continuous
variables w_ij to replace the u_i*y_j product.

The key is find the upper bounds U_i. Assuming that the feasible region
of the dual is bounded, you could maximize each u_i in turn subject to
the dual constraints, with the resulting objective value being U_i.

I think. It's been a long day -- you might want to check the details. :-)

/Paul