Topic
  • 4 replies
  • Latest Post - ‏2013-02-23T15:15:57Z by SystemAdmin
Eumpfenbach
Eumpfenbach
198 Posts

Pinned topic How would you attack this problem?

‏2013-02-18T03:47:10Z |
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.
Updated on 2013-02-23T15:15:57Z at 2013-02-23T15:15:57Z by SystemAdmin
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: How would you attack this problem?

    ‏2013-02-18T14:35:59Z  
    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...

    Tobias
    Updated on 2014-03-24T22:39:49Z at 2014-03-24T22:39:49Z by iron-man
  • Eumpfenbach
    Eumpfenbach
    198 Posts

    Re: How would you attack this problem?

    ‏2013-02-18T18:56:19Z  
    First, because X2 is maximized (and between 0 and 1) it suffices to use
    <pre class="java dw" data-editor-lang="java" data-pbcklang="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
    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 out-of-the-box. Is that the case, though?
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: How would you attack this problem?

    ‏2013-02-23T15:15:37Z  
    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 out-of-the-box. Is that the case, though?
    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 max-dependencies in the model) will be exploited better at the nodes in the search tree.
    Tobias
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: How would you attack this problem?

    ‏2013-02-23T15:15:57Z  
    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 max-dependencies in the model) will be exploited better at the nodes in the search tree.
    Tobias
    ... and setting probing to 2 or 3 may also help.