I want to write some subroutines for integer programming – the minimization of a function of integer variables. For a function of N integer variables, I can think of two plausible iterative algorithms for finding a better solution given an initial guess:
(1) Shift each variable up or down by 1 and move to the solution with the lowest value. This requires 2N function evaluations per step. If the problem is small, or if this method has reached what seems to be a minimum, try all pairs of one-unit moves.
(2) Randomly select a variable to move up or down by 1, and move to that solution if the function value is smaller. Or randomly select a pair of variables and do the same thing.
One can try either of these algorithms for many random initial guesses. What other approaches would people recommend?
You may want to have a look at the Branch & Bound method for discrete problems. It has been a while since I learnt about it, but I recall it can be combined with relaxation if your problem permits it (e.g. integer linear programming).
IIRC the process involves removing the integer constraints and successively solving relaxed problems where the B&B method is used to find a feasible solution when the relaxed solution is either rounded up or down (two branches).
I would try simulated annealing, which is just a little more complicated than your solution (2). But still very simple to code. Far simple than a genetic algorithm, which could also make a great job.
If you don’t have any knowledge on the shape of the function and that there may be local minima, that kind of metaheuristic will help a lot.
1 Like
Thanks for the interesting link, which links to a biography of Ailsa H. Land. Maybe I’ll buy a used copy of the book she co-authored with Susan Powell,
Land, A., and S. Powell (1973). Fortran codes for mathematical programming: linear, quadratic and discrete Wiley
The Amazon review from 1998 testifies to the longevity of FORTRAN:
The title says it all; this book lists the source code for various Mathematical Programming algorithms: linear, quadratic, integer, branch & bound, and parametric linear, plus discusses enough of the mathematics involved to make it all rational. The codes were developed at the London School of Economics to support coursework, so they have been debugged by generations of students. This author has used the code for Quadratic Programming to do mean-variance optimization for selection of efficient investment portfolios and found it to be solid.
1 Like
Solving Constraint Integer Programs
1 Like