3
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ 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$? $\endgroup$
    – Nelewout
    Jun 25, 2022 at 9:15
  • $\begingroup$ 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. $\endgroup$
    – Laura
    Jun 25, 2022 at 9:46
  • 1
    $\begingroup$ Can I ask why you want to transform it to a 0-1 problem instead of a general integer problem $\endgroup$
    – Sune
    Jun 25, 2022 at 12:07
  • $\begingroup$ @Laura, would you see this link? $\endgroup$
    – A.Omidi
    Jun 25, 2022 at 12:57
  • 1
    $\begingroup$ @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. $\endgroup$
    – Laura
    Jun 25, 2022 at 13:31

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I was thinking about this formulation as well, but I am coding in GAMS and it does not allow me to multiply by t. $\endgroup$
    – Laura
    Jun 26, 2022 at 8:57
  • 1
    $\begingroup$ I'm not a GAMS user, but I would be shocked if it did not allow you to use the index of summation as a coefficient in a constraint. $\endgroup$
    – prubin
    Jun 26, 2022 at 15:19
  • 1
    $\begingroup$ I am not a GAMS user also, but I think you can overcome this by creating a new array times[t] = t. $\endgroup$ Jul 3, 2022 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.