0
$\begingroup$

What are the available approaches to find an approximate solution to a large mixed integer programming problem?

I ran my problem in the Gurobi MIP solver.
It can find a feasible solution in reasonnable time.
But I need to solve several different MIP problems, and in the end, it takes too much.

Is there something like a least-square approximation to a MIP problem?
Or, any other approach, which can deliver a sub-optimal solution very quickly?

Can a general non-linear optimization solver quickly find an approximate solution of a MIP problem?

My model has one million variables.

I know there is a litterature on quickly finding a feasible solution to a MIP.
But I couldn't find a litterature body on approximate MIP solution.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

You might try a local optimization approach. Guess values for the integer variables and solve the remaining continuous linear programming problem. Using sensitivity analysis, see if the solution can be improved by changing one of the integer variables. Repeat as many times as you can or until no further improvements can be found.

You might also try simulated annealing or tabu search: these may produce better results but are more time-consuming, and a million variables might be too much.

Improve this answer
$\endgroup$
0
$\begingroup$

You could also try genetic programming; that is, start with say 100 assignments of variables, and then, keep the 50 best, clone/mutate a new set of variable assignments, and repeat.

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.