12
$\begingroup$

I currently have a complex Mixed Integer Program (a sort of vehicle routing problem variant, with multiple vehicle types and without assigned pickup -> delivery routes, among other complications) implemented in PuLP, which is taking far too long for CBC too solve. However,

  1. Getting a feasible solution is trivial.
  2. I don't need the optimal solution -- something within 10 % of optimality is just fine.

Are there any easy to implement, open-source heuristic tools to give me solutions? It looks like Gurobi has such tools, but it's quite pricey.

$\endgroup$
3
  • $\begingroup$ Disclaimer: I work for Gurobi. ------- If you are an academic, then Gurobi provides academic licenses at no cost, see here. Otherwise you can always request a trial license here, and we'll work with you to find a licensing scheme that fits your needs. Feel free to reach out and we'll do our best so that you can use our product. $\endgroup$
    – Richard
    Apr 24 '20 at 10:21
  • 2
    $\begingroup$ Short answer is no, that's why GUROBI is pricey ;) $\endgroup$ Apr 25 '20 at 2:54
  • $\begingroup$ I suggest you read the answers to this question: or.stackexchange.com/questions/2630/… Since you have a feasible solution, i would suggest to try a fix-and-optimize heuristic which is really simple to implement. $\endgroup$ Apr 27 '20 at 18:00
9
$\begingroup$

You can solve your model via the NEOS server which provides Gurobi, Cplex, and other solvers for free if it is the matter of not having a solver. I am not familiar with PuLP but I know it is easy to implement the solvers in NEOS if you model the problem in Pyomo. May it helps you to find PuLP syntax for it, I provide lines of code written for Pyomo using NEOS:

solver_manager = SolverManagerFactory('neos')
solution = solver_manager.solve(model, solver='gurobi', tee = True). 

Also you may have a look on this Github link. For example, a tabu search metaheuristic for Vehicle Routing Problems with Cross-Docking written in Python is given here.

$\endgroup$
3
$\begingroup$

I have some experience in solving large-scale airline crew pairing combinatorial optimization problems (an NP-hard problem) with difficulty similar to vehicle routing problems. Yes, solving such problems using standard open-source IP solvers is extremely time-consuming. You could customize/parallelize heuristics (such as Simulated Annealing, Variable Neighbourhood Search) and meta-heuristics (such as Genetic Algorithms) to solve your problem (if the problem-scale is not huge). If the problem-scale is huge (search space of million/billion-plus variables), then I would suggest you solving it using mathematical programming, particularly the Column Generation technique in which only the variables/columns promising objective gain are generated during the optimization in the continuous-domain (a relaxed form of the original IP). Useful articles-

Lübbecke, M. E., & Desrosiers, J. (2005). Selected topics in column generation. Operations research, 53(6), 1007-1023.

Lübbecke, M. E. (2010). Column generation. Wiley encyclopedia of operations research and management science.

$\endgroup$

This site is temporarily in read only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .