3

I have a minimization problem with integer variables and would like to transform it to binary variables. The problem is, that my objective is to minimize the overall waiting time, which consists of number of passengers times their waiting times.

My current problem is: $$\min TWT = \sum_{l,la,h} w_{l,la,h} \,u_{l,la,h} \tag{1}$$
$w$ and $u$ are both integers.

If I consider $w_{l,la,h,t}$ to be binary with a time index (1 if waiting time is $t$, 0 otherwise), I don't know how capture the weight $t$. Multiplying by $t$ does not work in my model.

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
Laura
  • 79
  • 2
  • 1
    Can you specify the model and problem setting a bit more precisely? Is $u$ a decision variable as well? Or is that the number of passengers? Does $w$ depend on $t$ (as your later paragraph would suggest), or not (as the math seems to imply)? What are $l$, $la$, and $h$? – Nelewout Jun 25 '22 at 09:15
  • l and la are different lines. H is the stop. w is the waiting time of one passengers at stop h when changing from l to la. and u(l,la,h) is the number of passengers changing at stop h. While u is given, w is a positive variable. And w is defined by the difference of arrival of line l and depature of line la. The original model has w(l,la,h) as an integer variable, e.g. w=5 mins. But I would like to introduce w as a binary variable, such that it is e.g. w(l,la,h,'5') = 1. – Laura Jun 25 '22 at 09:46
  • 1
    Can I ask why you want to transform it to a 0-1 problem instead of a general integer problem – Sune Jun 25 '22 at 12:07
  • @Laura, would you see this link? – A.Omidi Jun 25 '22 at 12:57
  • 1
    @Sune because I need to include a constraint which ensures that not more than 3 lines arrive at the same stop at the same time. I can only do that if the arrival times at the stop are binary. – Laura Jun 25 '22 at 13:31

1 Answers1

2

To avoid confusion, I will use $\bar{w}$ for the original (integer) $w$ variable. Assuming you have a constant upper limit $T$ on possible waiting time, you can define your new binary variables via the constraints $$w_{\ell, \ell a, h} = \sum_{t=0}^T t \cdot w_{\ell, \ell a, h, t} \quad \forall \ell, \ell a, h$$ plus $$\sum_{t=0}^T w_{\ell, \ell a, h, t} = 1 \quad \forall \ell, \ell a, h$$ to ensure that exactly one binary variable is chosen.

prubin
  • 39,078
  • 3
  • 37
  • 104