0- 1 integer linear programming is a special case of integer linear programming, which is widely used in practice. Although variables have only two values, it is unexpectedly difficult to solve such problems. The following summarizes some related solutions.
Exhaustive method? All possible solutions are generated one by one, and then the solutions satisfying the constraints are compared to make the optimal solution of the objective function the optimal solution. This is a method, but not a good one. If the problem is large, it is impossible to find the optimal solution in an acceptable time. This is also the difficulty of solving integer programming.
2. Implicit enumeration method I? It is an improvement of the exhaustive method. The idea is to give a feasible solution first, and then substitute it into the objective function to calculate the function value to get an upper bound (if the minimum value is found) or a lower bound (if the maximum value is found). Then check the other solutions one by one. If the solution is greater than the upper bound or less than the lower bound, there is no need to check the feasibility, because it cannot be the optimal solution. Otherwise, we should check the feasibility. If it is a feasible solution, modify the upper or lower bound and continue to look up other solutions. Otherwise, you don't need to modify the upper bound or lower bound, and look up other solutions directly. This method controls whether the feasibility test is needed through the upper or lower limit, which improves the efficiency. However, it will take some time to find a feasible solution. When there are many constraints and variables, the workload is extremely large. To take a step back, even if the feasible solution is easy to find, its upper bound is too large or its lower bound is too small, and the filtering effect is not obvious. This is the defect of this method.
3. Implicit enumeration II? This method first transforms the problem into a standard form, and then according to the idea of branch and bound method, the optimal solution is found by testing the feasible solution as little as possible. This method is troublesome, and I can't describe it clearly here. I will write this part in a few days after I understand it thoroughly.
4. Implicit enumeration method 3? This is put forward by Cheng Dongshi and Zhang Shengnian in an article "Some Problems about 0- 1 integer programming" published in Journal of Jiangxi Vocational and Technical College of Electric Power. The general idea is to substitute all possible solutions into the calculated values of objective functions, and then sort these objective function values. If it is the maximum value, it will be sorted in descending order; if it is the minimum value, it will be sorted in ascending order. Then check the feasibility of the corresponding solutions one by one in this order, and get the optimal solution when you meet the first feasible solution, because other solutions will not be better than this one. The defects of this method are also obvious. If there are n variables, it needs n objective functions with a value of 2, and then it needs to be sorted, which is a lot of work. Another is that if the ranking result is that the feasible solution is ranked last, it is still necessary to test the n power of 2.
4. Heuristic algorithm? Genetic algorithm, ant colony algorithm and so on can all belong to this category. These are random algorithms. To put it bluntly, it is resignation. Even if you calculate the optimal solution, you don't know whether it is the optimal solution, because the convergence of this kind of algorithm is only the convergence of probability, and only God knows whether it has been optimized in the calculation process. Heuristic algorithms are only used as a last resort. We can only guarantee that the solution obtained by this method is better than that obtained by other methods, but it does not necessarily represent the best.
The solution of 0- 1 programming is still under study. Maybe you will find an effective algorithm.