# MIP Model with relaxed integer constraints takes longer to solve than normal model, why?

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.

• Welcome to OR.SE. Do you ensure the solution provided by the solver is really what you want? (I mean, do you verify and validate the solution to ensure that the original problem works well?) Commented May 1, 2023 at 9:42
• Hi, thanks for the welcoming. Yes, I do obtain the values from the solution and interpret them, passing the solution through a function that detects any unfeasible violation of all the constraints of the model, furthermore I plot the results so that I can visually understand the decisions that are taken and so far I have never had a problem with invalid solutions or solutions that don't represent what I want. Commented May 1, 2023 at 14:15