4
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ 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?) $\endgroup$
    – A.Omidi
    May 1 at 9:42
  • $\begingroup$ 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. $\endgroup$ May 1 at 14:15

1 Answer 1

5
$\begingroup$

First, it is risky to draw conclusions with so few data. It could just be luck.

Still, there are some possible reasons why setting some variables as integer might be beneficial:

  • It can trigger more deductions in the presolve step
  • It can lead to new cuts being generated
$\endgroup$
1
  • 1
    $\begingroup$ Good points. I would bet on presolve doing the job. A quick look at the solver log would reveal the number of variables before and after presolve. $\endgroup$
    – Sune
    May 1 at 18:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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