I've wasted a lot of time with a "try and see" approach to solving problems. Figured I would just ask for some expert advice up front.
I have an objective with bilinear terms. So something like Max X * y, where X is a vector of continuous variables and y is a binary variable (I am obviously simplifying a bit but I hope it is clear). To remove the nonlinearity, I introduce a new vector of variables X2 of the same dimension as X, with 3 constraints for each variable:
X2 <= y
X2 <= X + 1  y (X is bounded between zero and 1)
X2 >= X  1 + y
When I am done with all the transformations to keep things linear, I end up with something like 900k constraints and 300k variables.
Is there any way to exploit this special structure in Cplex? Obviously, if I branch down on y, then I do not need X2 as they will all be zero. If I branch up, X and X2 become perfect substitutes.
After reading this site, I am well aware that cplex cannot handle changes to the number of variables throughout the tree. If I cannot remove the variables, I cannot remove the constraints, either. Would lazyconstraints be a good option? Essentially I would be querying whether the solver has branched on y, then add the appropriate constraints? Is this likely to yield good results, as I might be adding thousands of lazyconstraints at a time? Any other ideas?
Thanks.
Topic

Re: How would you attack this problem?
20130218T14:35:59ZThis is the accepted answer. This is the accepted answer.First, because X2 is maximized (and between 0 and 1) it suffices to use
X2_j <= y for all j X2_j <= X_j for all j
You do not need the additional constraints that will make X2_j equal to X_j if y = 1, because maximizing X2 will already push X2 towards X.
But if there is really only one binary variable y, then you should probably solve this as two individual MIPs, one with y = 0 and one with y = 1. But I guess you have multiple y's, each triggering a different set of X variables...
TobiasUpdated on 20140324T22:39:49Z at 20140324T22:39:49Z by ironman 
Re: How would you attack this problem?
20130218T18:56:19ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130218T14:35:59Z
First, because X2 is maximized (and between 0 and 1) it suffices to use
<pre class="java dw" dataeditorlang="java" datapbcklang="java" dir="ltr">X2_j <= y for all j X2_j <= X_j for all j </pre>
You do not need the additional constraints that will make X2_j equal to X_j if y = 1, because maximizing X2 will already push X2 towards X.
But if there is really only one binary variable y, then you should probably solve this as two individual MIPs, one with y = 0 and one with y = 1. But I guess you have multiple y's, each triggering a different set of X variables...
Tobias
You are correct, I could lose one of the constraints. That helps a little. Thanks.
But I am still wondering if there is a way to customize settings / callbacks to speed up a problem with this type of structure.
Ideally, I would let cplex do all the searching and I would solve an LP at each node that would let me remove all unnecessary variables and constraints.
I've previously tried to do something similar (relying on a rudimentary branching scheme that I created, and then just using Cplex to solve the LP subproblems) and it had horrible performance. Nothing I create is going to have as advanced a search as Cplex, so I am really trying to avoid that route.
If the answer is that there is really nothing I can do, then I will just rely on cplex outofthebox. Is that the case, though? 
Re: How would you attack this problem?
20130223T15:15:37ZThis is the accepted answer. This is the accepted answer. Eumpfenbach
 20130218T18:56:19Z
Correct. I have many binary variables and many X variables. I was just trying to give a general sense of the problem. Picture X being of dimension 1000 and something like 100 different binary y variables.
You are correct, I could lose one of the constraints. That helps a little. Thanks.
But I am still wondering if there is a way to customize settings / callbacks to speed up a problem with this type of structure.
Ideally, I would let cplex do all the searching and I would solve an LP at each node that would let me remove all unnecessary variables and constraints.
I've previously tried to do something similar (relying on a rudimentary branching scheme that I created, and then just using Cplex to solve the LP subproblems) and it had horrible performance. Nothing I create is going to have as advanced a search as Cplex, so I am really trying to avoid that route.
If the answer is that there is really nothing I can do, then I will just rely on cplex outofthebox. Is that the case, though?
One guess is that it could help to crank up node presolving, i.e., setting the "node presolve" parameter to 2 or even 3. This way, the additional structure that was created by branching (and thus fixing some of the maxdependencies in the model) will be exploited better at the nodes in the search tree.
Tobias 
Re: How would you attack this problem?
20130223T15:15:57ZThis is the accepted answer. This is the accepted answer. SystemAdmin
 20130223T15:15:37Z
Models where a single variable is specified to be the max over a set of variables are pretty tough for MIP solvers, because the dependencies between the variables and between variables and objective are kind of indirect.
One guess is that it could help to crank up node presolving, i.e., setting the "node presolve" parameter to 2 or even 3. This way, the additional structure that was created by branching (and thus fixing some of the maxdependencies in the model) will be exploited better at the nodes in the search tree.
Tobias