Abstract:
INTENT Un Algoritmo Interior para Programación Entera
Some ideas are presented that suggest a heuristic to solve integer linear
programming problems {\bf ILP}. Interior points are successively explored
inside a convex of a {\bf LP({\it e})} problem. The latter linear
programming problem has a convex, that contains the original integer
solutions, at a fixed distance $e$ $>$ $0$ from the convex defined by the
problem restrictions, and is obtained relaxing the integer condition on
variables. Within the convex cone with origin in the {\bf LP({\it e})}
optimal finite real solution, an interior polyhedron is constructed at
certain distance from vertex, with extreme points in the convex cone edges.
Inside that polyhedron are sampled points, and also inside a cube with
origin in those points. Points, that rounded give integer vectors. The {\bf %
ILP} feasibility is checked. The interior polyhedrons are recalculated,
inside the convex cone, increasing its distance from the real optimum. If a
feasible integer solution is founded, then the searching path is retraced
looking for a better point. Using {\bf INTENT} the solution for some test
problems are been obtained.