• w[k][t] <= Y * z[k][t]
• w[k][t] <= y[k][t]
• w[k][t] >= y[k][t] - Y * (1 - z[k][t]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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.

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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.

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].

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.

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]).

• tau[k] >= t - T * (1 - z[k][t])
• tau[k] <= t - 1 + (T - t +1) * z[k][t].