Methods for binary linear programming I have an LP problem (linear objective with eq and ineq constraints) in binary variables.
Except for the objective, all the coefficients are integer, mostly in {-1,0,1}. Maybe the objective coeff could be discretized.
I heard that for certain matrices there are approaches that can beat the standard MI solver, and I wonder if some can be relevant to my problem. Some related buzz words:

*

*symplectic matrix

*unimodular matrix

*Smith/Hermite normal form

*diophantine equations

It's something in the spirit of if my problem is a diophantine system, then a solution can be found by constructing the Smith normal form, which might be faster than that standard MI.
I'm trying to look into it, and I thought perhaps someone has tips on the subject. For example:

*

*Don't expect much, the algorithm for constructing the Smith normal form is usually slower than the standard MI solver. Some MI solvers (e.g. gurobi/mosek) already leverage this.

*You can test your system matrix for these certain conditions. If they apply, then you are in luck.

*This reference may interest you.


One tip from David from gurobi:

If your matrix is totally unimodular you should be able to relax
integrality restrictions (binary variables are just continuous between
0 and 1) and still have an integer solution.

https://support.gurobi.com/hc/en-us/community/posts/8084931991185-Methods-for-solving-binary-LP

Duplicate questions:
https://or.stackexchange.com/questions/8822/methods-for-binary-linear-programming
https://scicomp.stackexchange.com/questions/41747/methods-for-binary-linear-programming

Erwin in the comments below suggests to look at the SAT-based solver in OR-TOOLS, which requires int cost coeff.

Using a graph
Is there an effective algorithm to solve this binary integer linear programming?
 A: Totally unimodular matrices are matrices whose square sub-matrices (including the matrix itself, if it is square) all have a determinant equal to -1, 0 or 1. This notably implies that all the matrix coefficients are -1, 0 or 1, but this is not a sufficient condition.
Totally unimodular matrices have a nice property when being the matrix of a LP (linear programming) problem: the solution contains only integers.
This means that if you have a LP problem, plus some constraints that some variables are integers (which makes that a MIP - Mixed Integer Problem), you can abandon the integer constraints, the LP solution will be integers only, so it will also be the solution of the MIP.
The consequence is that simple, efficient methods such as the simplex or an interior point method, can be used in place of methods for MIP - which for example relax the problem into a linear one, solve the linear problem, then add some cuts (additional linear constraints) to suppress the non-integer solution found, and repeat until convergence. Here you will not have to repeat: the solution of the relaxed problem is the solution of the problem.

Note that if you plan to use a solver such as Gurobi or CPlex, you do not have to worry much about the method used by the solver. Plus, all basic tricks to simplify the problem are already implemented in the solver, so it is often not productive to try to simplify the problem by oneself. Still you can try finding a formulation that has the least number of integer variables, and where the constraints are as tight as possible (the ideal case is when the constraints by themselves impose an integer solution, i.e. the integer solution is on a face of the constraints polytope).
