I have a graph $G$ and the following variables.

$b_{i,j}$ is $(i,j)$ edge is taken or not.

$t_{i,j}$ is time to travel $(i,j)$

$A_{i}$, $D_{i}$ are arrival and departure time at node $i$.

My first objective is :

$$\min \sum_{i,j} b_{i,j}\cdot t_{i,j} + \sum_{i} D_{i} - A_{i}$$

My second objective is :

$$\min A_{e}$$

where $e$ is the end location of the path.

My question is why the solver takes a long time to solve the second objective as compared to the first objective.


Your first objective is a minisum objective; your second is a minimax objective. Minimax objectives are usually much harder to solve.

See this related question: Why are integer minimax problems hard?

As an analogy, the $p$-median problem is a minisum facility location problem, while the $p$-center problem is a minimax problem with nearly the same constraints. I once ran a test on both problems using a classic 88-node benchmark instance. CPLEX solved the $p$-median problem in 0.5 seconds but took more than 1600 seconds to solve the $p$-center problem.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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