I am currently working on my undergrad thesis which is a mathematical optimization problem of the territory design family of problems. I am using the mathematical formulation of the problem to solve it using commercial software and comparing the time and gap to optimum to my metaheuristics.
One step of my heuristics involves solving a relaxed version of the problem. I have two decision variables: $Y_i$ and $X_{ij}$, where $Y_i =1$ if the territory center $i$ is selected for use, 0 if not, where I must select $P$ centers to be used. On the other hand, $X_{ij}=1$ if the client $j$ is served by the center $i$, 0 if not. In the relaxed version of the problem, I tell the solver to work with $X$ as a continuous variable bounded from 0.0 to 1.0, but the $Y$ is left alone as an integer.
In theory, this should make the model easier to solve, leaving me with infactible solutions for my original model as $X$ should be an integer, but I really don't care much as I use this relaxation to initialize my $Y$, working with my $X$ later on the heuristic.
With some sizes of the instances that I generate, this appears to hold. My heuristic containing the relaxed version of the model and my algorithm to construct the $X$ runs in less time than the normal version of the model for the same instance. However, working with larger instances shows me that the relaxed version is harder to solve than the non-relaxed version.
What I mean by this is that an instance with 2650 clients, 500 centers and $P = 220$ takes the following time to be solved and a cutoff time of 1800 seconds:
| Gurobi | CPLEX | HiGHS |
|---|---|---|
| Relaxed: 1490 seconds | Relaxed: 1800 seconds | Relaxed: 1800 seconds |
| Non-Relaxed: 925 seconds | Non-Relaxed: 1800 seconds | Non-Relaxed: Unfeasible |
In this specific case, only Gurobi finds an optimal solution to the model, with CPLEX and HiGHS failing to achieve so, even HiGHS failing to find a feasible solution for the problem. I don't want this question to be a technical implementation or solvers comparison question. The same model is built for the three solvers, using the JuMP.jl package in the Julia language.
It really puzzles me how the only solver that found the optimum takes longer to solve the relaxed version, and I would like to know if there is a solver agnostic explanation for this or if my idea of relaxing the integer constraints is flawed. I would be more than happy to provide the code and logs of the solvers if required but I don't want to make this question any longer than it should be.
