So if z[k][p] = 1 and z[k][p'] = 0 for some other path p', you believe tao[k] will be p.date?
Original Message:
Sent: Fri June 11, 2021 11:10 PM
From: Ying Qi
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Fri June 11, 2021 11:55 AM
From: Paul Rubin
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Fri June 11, 2021 07:33 AM
From: Ying Qi
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Fri June 11, 2021 04:42 AM
From: Ying Qi
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Tue June 08, 2021 01:12 PM
From: Paul Rubin
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Mon June 07, 2021 09:41 PM
From: Ying Qi
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Tue June 01, 2021 03:07 PM
From: Paul Rubin
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Mon May 31, 2021 08:56 PM
From: Ying Qi
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Fri May 28, 2021 03:04 PM
From: Paul Rubin
Subject: transformation for a non-convex problem
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
Original Message:
Sent: Thu May 27, 2021 09:01 PM
From: Ying Qi
Subject: transformation for a non-convex problem
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
------------------------------