Construction heuristics in binary integer programming

201 views Asked by At

I have been trying for find answers to this question, but I cannot find anything comprehensive. I am looking to find an algorithm or heuristic to construct an initial feasible solution to the binary integer programming problems, more specifically the set packing, set partitioning, and set covers problems.

If one has the following binary integer programming problem

Minimize      ax_1 + bx_2 + cx_3
Subject to    x_1 + x_2 <= 2
              3x_1 + 3x_2 >= 6
              x_2 + 2x_3 = 2

With the solution representation

[x_1, x_2, x_3]

where x_i = 0 or 1.

Then how would one go about to construct an initial feasible solution to this problem. Going through every possible solution will obviously not work when the problem consists of thousands of variables and constraints.

The goal here is to construct an initial feasible such that one can perform a local search to obtain a local minima, and then applying a metaheuristic to this.

1

There are 1 answers

3
sascha On BEST ANSWER

The problem of finding a feasible solution to some Binary Integer Programming problem is already NP-complete. It's one of Karp's popular 21 NP-complete problems -> wiki: 0–1 integer programming!

In a general setting, not much will beat the following complete approaches (complete: they will find a feasible solution if one exists in finite time or prove there is none):

  • Integer Programming solvers (Simplex + Branch and Bound + Cutting planes)
  • Constraint-Programming solvers
  • SAT solvers

These are also using heuristics internally (in fact they have to: because the problem is NP-complete).

If you don't want to use general algorithms/software, you have to tune your heuristics specially for some problem. But these problems you are mentioning differ a bit and different heuristics might be needed. It's also important to analyze special-structure in your instances (random-instances behave very very different from most real-world problems)! While designing these special-purpose heuristics you might implement some non-complete approach which might be working better for your case.

The problem you are facing, finding an initial feasible-solution is also very common in many Meta-Heuristics!

It's a complex topic!