Mixed Integer Programming - How to model a term in objective function with a constant multiplied by (1-Decision Variable)

Question

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

Answer 1

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$.