0
$\begingroup$

I am solving an optimization problem, where I want to minimize the objective function $$Z = \sum_q \left(D_q \text{fare}_q - \sum_{p \ne q} \Delta D^p_q \text{fare}_q \right) (1-Z_q)$$

Each $q$ is an optional flight which the solver should decide whether to operate or not depending on some constraints.

$Z_q$ is a Boolean decision variable which has the following constraints.

$Z_q = 0$ if flight $q$ is cancelled. $Z_q = 1$ if flight $q$ is operated. The expression $$D_q \text{fare}_q - \sum_{p \ne q} \Delta D^p_q \text{fare}_q$$ represents a revenue loss, which should only occur when the flight $q$ is cancelled ($Z_q = 0$).

I am solving the problem using Matlab, and the question is how to practically implement this part in the objective function.

My first idea is to neglect the 1 in $(1-Z_q)$, and then my objective function becomes the following: $$-\sum_q \left(D_q \text{fare}_q - \sum_{p \ne q} \Delta D^p_q \text{fare}_q \right)(Z_q)$$

then re-add the neglected on the result of the objective function, or this solution will mess up the concept of the revenue loss

My 2nd idea is to add another decision variable and add constraints to ensure it to be equal 1 for example my objective function will be the following:

$$\sum_q\left(D_q \text{fare}_q - \sum_{p \ne q} \Delta D^p_q \text{fare}_q \right)(V_q-Z_q)$$

Then I should add the following constraint $V_q = 1$.

Note that this solution will have a great effect on the solving time

$\endgroup$
2
  • 2
    $\begingroup$ Please use MathJax on this site, don't upload text or equations as images. Thanks. $\endgroup$
    – Rob
    May 19 at 11:38
  • $\begingroup$ Maybe add a variable $NZ_q$ and a constraint $NZ_q = 1-Z_q$. Then you can write the objective in terms of $NZ_q$. (The solver usually is not bothered by this as the presolver may take this out). $\endgroup$ May 19 at 19:10

1 Answer 1

1
$\begingroup$

You want to optimize an (affine) objective function of the form $\sum_j c_j x_j + k$, where $c_j$ and $k$ are constants and $x_j$ is a decision variable.

If your solver requires that the “objective constant” or “offset” $k$ is $0$, a simple workaround is to omit $k$ and add it back in after the solver call, as you described in your first idea. This transformation preserves the set of optimal solutions.

Your second idea is also valid but makes the problem artificially larger. I would not expect much performance difference between the two approaches because a presolver would immediately eliminate the “fixed” variable $V_q$.

$\endgroup$
3
  • $\begingroup$ Thank you very much, really appreciate your time. concerning the first idea, since I want this +ve penalty coefficient to occur only when the binary variable Zq = 0, that's why it's multiplied by (1-Zq), so when Zq = 1 the penalty disappears, So, in case of the first idea wouldn't this affect the optimal solution cause there is a -ve coefficient occurs when Zq = 1 and when we add it back after the solver call this will only neutralize it and no penalty will be added then. $\endgroup$ May 19 at 13:36
  • $\begingroup$ No, for constant $k$, minimizing $f(x)+k$ and $f(x)$ will yield exactly the same set of optimal solutions, and it is a useful exercise to prove this by contradiction. Suppose $x^*$ is optimal for one objective and not the other… $\endgroup$
    – RobPratt
    May 19 at 13:50
  • $\begingroup$ @RobPratt, would you please, as $Z_q$ is a boolean decision variable, and if in the optimal solution for some $q$'s its values being zero, should not interpret the objective function as a logical expression? $\endgroup$
    – A.Omidi
    May 19 at 20:46

Your Answer

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

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