Decision Optimization

Expand all | Collapse all

transformation for a non-convex problem

  • 1.  transformation for a non-convex problem

    Posted 16 days ago
    Hi all,

    I am working a programming problem whose objective is where x and y are non-negative integer variables, and  tao[k], the upper bound of time, is also a decision variable.

    Do you know how to solve this problem by CPLEX solver rather than CP solver?

    What's more,  how to deal with the tao[k] when it comes to write the reduced cost for column generation?

    ------------------------------
    Ying Qi
    ------------------------------


  • 2.  RE: transformation for a non-convex problem

    Posted 15 days ago
    Is k being used as a superscript or as an exponent (power)? Is r (lower limit of time in the second summation) a constant or a variable?

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



  • 3.  RE: transformation for a non-convex problem

    Posted 12 days ago
    Hi Paul,
        
        Thanks for your reply.   k is the index, which presents a kind of commodity. The lower bound of time, r, is a constant.

    ------------------------------
    Ying Qi
    ------------------------------



  • 4.  RE: transformation for a non-convex problem

    Posted 11 days ago
    Let T be the largest time index, and let Y be an a priori upper bound for all y[k][t]. Introduce new nonnegative (continuous) variables w[k][t] and new binary variables z[k][t]. Replace y[k][t] with w[k][t] in the objective function (leaving the rest of the objective alone).

    Next, introduce the following constraints for all valid k and t:
    • w[k][t] <= Y * z[k][t]
    • w[k][t] <= y[k][t]
    • w[k][t] >= y[k][t] - Y * (1 - z[k][t]).
    You can easily confirm that z[k][t] = 1 => w[k][t] = y[k][t] and z[k][t] = 0 => w[k][t] = 0.
    Finally, introduce the following constraints for all valid k and t:
    • tau[k] >= t - T * (1 - z[k][t])
    • tau[k] <= t - 1 + (T - t +1) * z[k][t].
    Again, you can easily confirm that z[k][t] = 1 ==> tau[k] >= t and z[k][t] = 0 ==> tau[k] <= t - 1.

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



  • 5.  RE: transformation for a non-convex problem

    Posted 5 days ago
    Hi Paul,

    Thanks for your help! There is another question. Do you have any idea to linearize these constraint?
    forall( k in orders,p1,p2 in paths:p1!=p2)
    (z[k][p1]==z[k][p2]==1) => ( tao[k] == minl(p1.date,p2.date) );
    
    forall( k in orders,p in paths)
    (sum(p in paths)z[k][p]==1) => (tao[k]==sum(p in orders_paths[k])z[k][p]*p.date);
    

    Actually, I want to write down its dual problem.  Or can I write the dual problem directly without linearization?



    ------------------------------
    Ying Qi
    ------------------------------



  • 6.  RE: transformation for a non-convex problem

    Posted 4 days ago
    How to linearize the constraints depends on which things are variables and which are parameters (which you did not state) and also what types of variables (continuous, integer, binary) the variables are (which you also did not state). In general, you will need to use binary variables and (probably) "big M" constraints to linearize, which means your problem will be an integer program. There is a duality theory of sorts for IPs, but I suspect you are looking for the linear program dual, which may not be meaningful once your problem is an IP. To find out how to linearize things, you might try OR Stack Exchange, where this is a frequently asked question. Search for "linearize if-then".

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



  • 7.  RE: transformation for a non-convex problem

    Posted yesterday
    Hi Paul,

    Thanks for your advice. I got the linearization!

    z[k][p1]​ is a binary variable and tao[k] in a non-negative integer variable. Then the linearization is 

    forall( k in orders, p in paths)
    tao[k]<=p.date-p.date*(1-z[k][p])​;

    However, there is another question. I run CP solver with it and then run it with logical constraints with the same meaning. Well, I got different results. I delete all alternative paths except optimal paths provided by logical constraints and then I got the same answer. Does it mean the linearization is correct?

    ------------------------------
    Ying Qi
    ------------------------------



  • 8.  RE: transformation for a non-convex problem

    Posted yesterday
    Objective is minimizing the total cost. The result of original logical constraints is lower than it with this linearizing formula. It means logical constraints could find better result.
    However, when I delete other paths, this linearizing formula can get the same result as logical constraints. Do you have any idea?

    ------------------------------
    Ying Qi
    ------------------------------



  • 9.  RE: transformation for a non-convex problem

    Posted yesterday
    I don't know what "delete other paths" means. Your linearization of the first constraint looks incorrect to me. (I don't see any linearization of the second one.) If z[k][p] = 1 for any path p, your linearized constraint forces tau[k] = 0, which is not what the original constraint said.

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



  • 10.  RE: transformation for a non-convex problem

    Posted 22 hours ago
    Hi Paul,
    forall( k in orders, p in paths)
    tao[k]  <=  p.date  -  p.date*(1-z[k][p])​;​

    In my opinion, if z[k][p] = 1 , tao[k] should equal to p.date. If there are more than one path selected, tao[k] will be update by a smaller p.date.  Right?

    As for " delete other paths", I mean there are lots of alternative paths as input date of my modal, like path a,b,c,d,e,f, etc. Path "a" and 'c" are optimal paths by solving model with logical constraints. Then I deleted "b","d","e" and "f" paths, and solved model again with linearizing constaints with paths "a" and "c" . I got the same results.



    ------------------------------
    Ying Qi
    ------------------------------



  • 11.  RE: transformation for a non-convex problem

    Posted 7 hours ago
    So if z[k][p] = 1 and z[k][p'] = 0 for some other path p', you believe tao[k] will be p.date?

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