1
$\begingroup$

I have formulated a MILP problem & solved it using Gurobi. Below is the link to the description of MILP problem (a brief document) clearly stating its variables, constraints, and objective function.

https://docs.google.com/document/d/1upkdHAkJ2UUIqz5GKvJWhXls-U9lA36f/edit?usp=sharing&ouid=104556000005791842995&rtpof=true&sd=true

However, I want to check if I can add heuristics or metaheuristics to my existing problem and remodify it.

Improve this question
$\endgroup$
2
  • $\begingroup$ Does gurobi solve your problem, and are you satisfied about it? why would you want to add a heuristic ? to try and converge faster ? $\endgroup$
    – Kuifje
    Dec 12, 2022 at 11:52
  • $\begingroup$ Hi @Kuifje , It does solve the problem but I want to study its converging capability. So I want to add heuristic. But I am unaware how do I add it in my current equations. $\endgroup$
    – Margi Shah
    Dec 12, 2022 at 12:55

2 Answers 2

Reset to default
3
$\begingroup$

There is a Gurobi video Faster MIPs Using Custom Heuristics

MIPs often solve faster with good integer feasible solutions. Thus, Gurobi contains a variety of MIP heuristics to create integer solutions and improve them. However, sometimes you can improve upon this with custom integer heuristics that exploit model structure.

In this webinar, you will learn:

What models may benefit from custom MIP heuristics, and how to build your own custom MIP heuristics by using the traveling salesman problem to illustrate different integer heuristics that take advantage of both model structure and relaxed solution values in the MIP tree.

Without going custom, the amount of time the Gurobi solver devotes to feasibility heuristics can be controlled by the Heuristics parameter.

https://www.gurobi.com/documentation/9.0/refman/heuristics.html

Heuristics Time spent in feasibility heuristics   Type: double   Default value: 0.05   Minimum value: 0   Maximum value: 1

Determines the amount of time spent in MIP heuristics. You can think of the value as the desired fraction of total MIP runtime devoted to heuristics (so by default, we aim to spend 5% of runtime on heuristics). Larger values produce more and better feasible solutions, at a cost of slower progress in the best bound.

Note: Only affects mixed integer programming (MIP) models

Improve this answer
$\endgroup$
8
  • $\begingroup$ Hi Mark, Thanks for sharing this details. It shows how to use heuristics in Gurobi. However I am keen to know how do I modify my problem from MILP to Evolutionary algorithm based problem, for ex: Genetic algorithm to add heuristics ? $\endgroup$
    – Margi Shah
    Dec 12, 2022 at 14:14
  • 1
    $\begingroup$ For what it's worth, I don't think the problem is a good candidate for an evolutionary algorithm. GAs are really designed for unconstrained problems. It might be possible to design a random key GA for the problem, but I am far from confident about that. $\endgroup$
    – prubin ♦
    Dec 12, 2022 at 16:05
  • 1
    $\begingroup$ I don't see anything there that would change my answer. $\endgroup$
    – prubin ♦
    Dec 12, 2022 at 17:48
  • 1
    $\begingroup$ "Can't" is a strong term. I think it would be difficult to find a reasonable chromosome definition, and performance might not be very good (particularly if you have to address the constraints by turning them into penalty terms in the objective). $\endgroup$
    – prubin ♦
    Dec 13, 2022 at 17:17
  • 1
    $\begingroup$ Yes @prubin . Nine years ago, just to give MATLAB';s GA so called global optimization algorithm a chance, I tried it on a Bilinear Matrix Inequality (BMI) problem, which is a special case of Nonlinear SDP.. I provided GA a feasible starting solution strictly and well in the interior of the constraints. After running full bore for 2 days, the GA did not produce another feasible solution (even though it could have moved in any direction from the starting value and had another feasible point). Using derivative-based methods, I solved the problem to global optimality in minutes. $\endgroup$
    – Mark L. Stone
    Dec 13, 2022 at 18:17
1
$\begingroup$

Please see if this answer helps you. Heuristics will have perturbation (changing values, first randomly, then based on a pattern if direction of min/max is ascertained) of variables, checking the constraints (called fitness function) and repeat.

Improve this answer
$\endgroup$

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.