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?
Pinned topic How would you attack this problem?
Answered question This question has been answered.
Unanswered question This question has not been answered yet.
Updated on 2013-02-23T15:15:57Z at 2013-02-23T15:15:57Z by SystemAdmin
Re: How would you attack this problem?2013-02-18T14: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 2014-03-24T22:39:49Z at 2014-03-24T22:39:49Z by iron-man
Eumpfenbach 270004EPV1198 Posts
Re: How would you attack this problem?2013-02-18T18:56:19ZThis is the accepted answer. This is the accepted answer.
- SystemAdmin 110000D4XK
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 out-of-the-box. Is that the case, though?
Re: How would you attack this problem?2013-02-23T15:15:37ZThis is the accepted answer. This is the accepted answer.
- Eumpfenbach 270004EPV1
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 max-dependencies in the model) will be exploited better at the nodes in the search tree.