How to force sending of xsi:type in web service call out

We are trying to call a third party web service. The web service expects a xsi:type specified for one of the elements, which is a complex type. But, the xsi:type is not sent in the request genrated by Apex generated web service client which results in a fault from the web service.

How de we make Apex to send out the xsi:type?