13
$\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.

Improve this question
$\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
    Commented Apr 24, 2020 at 10:21
  • 2
    $\begingroup$ Short answer is no, that's why GUROBI is pricey ;) $\endgroup$
    – Nikos Kazazakis
    Commented Apr 25, 2020 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$
    – Michael Lindahl
    Commented Apr 27, 2020 at 18:00

2 Answers 2

Reset to default
10
$\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.

Improve this answer
$\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.

Improve this answer
$\endgroup$

Your Answer

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

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