Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
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.
