Decision Optimization

 View Only

  • 1.  Any way to reformulate a quadratic constraint?

    Posted Sun March 17, 2024 03:04 PM

    I am working two create a new set of constraints, which I've discovered are non-convex. These are derived from a problem such that given two populations, each with a defined subset, ensure that items picked from each subset are within a specified percentage of their respective superset, e.g. maximum difference between (sum(PopSubA) / sum(PopA)) and (sum(PopSubB) / sum(PopB)) would be 0.10 or 10%.

     

    After some work and a few iterations, I was able to discover a handful of ways to formulate this into a set of constraints that involved minimal quadratic terms - declare a variable within the model to act as a target percentage, which yields the non-convex constraints. The formulation with a maximum range of 10%: 
    sum(popSubA) <= sum(popA) * (target + 5%)
    sum(popSubA) >= sum(popA) * (target - 5%)
    sum(popSubB) <= sum(popB) * (target + 5%)
    sum(popSubB) >= sum(popB) * (target - 5%)

    Note that all variables from popA and popB are binary integers to denote whether or not these are picked, and we have tried declaring target as an integer variable with bounds [5, 95], as well as a continuous variable with bounds [0.05, 0.95]

    My original attempts to create the constraints involved a formula with large matrix multiplication:
    sum(popSubA) * sum(popB) - sum(popSubB) * sum(popA) <= 0.10 * sum(popA) * sum(popB)

    sum(popSubB) * sum(popA) - sum(popSubA) * sum(popB) <= 0.10 * sum(popA) * sum(popB)


    I have not been able to find another way to maintain a percentage relationship between two groups in a non-convex way. Is there something I'm overlooking?

    Thanks for any and all advice,

    Trey



    ------------------------------
    Trey Westrich
    ------------------------------


  • 2.  RE: Any way to reformulate a quadratic constraint?

    IBM Champion
    Posted Sun March 17, 2024 04:27 PM

    Your first four inequalities are fine, and are linear except for the product of target and sum(popA) or sum(popB). You can linearize each of those products by introducing auxiliary variables (continuous over [0,1]) and a gaggle of constraints. Let x_i denote the binary variable indicating selection of object i and y_i the variable that will capture target * x_i. I'm going to assume target's domain is [0, 1], but you can try tightening it if you wish. The product of target and whichever sum we are looking at will be the sum of the y_i variables. The constraints defining y_i are y_i <= x_i, y_i <= target, and y_i >= target - 1 + x_i. You can check that if x_i = 0 then y_i = 0, while if x_i = 1 then y_i = target.



    ------------------------------
    Paul Rubin
    Professor Emeritus
    Michigan State University
    ------------------------------

    Original Message


  • 3.  RE: Any way to reformulate a quadratic constraint?

    Posted Mon March 18, 2024 10:39 AM

    In order to generalize the formulation given by Paul, a linear formulation of z = x * y where x is a binary variable and y is a (integer or continuous) variable in interval [a, b] is :


    a*x <= z <= b*x
    a*(1-x) <= y - z <= b*(1-x) 

    It represents the convex hull of the constraint z = x*y.


    Original Message


  • 4.  RE: Any way to reformulate a quadratic constraint?

    Posted Wed March 20, 2024 03:00 PM

    Thanks for the advice, Paul and Philippe. I was able to take this information, and put it into place, and it worked as desired.



    ------------------------------
    Trey Westrich
    ------------------------------

    Original Message