3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ You also may want to look at the SAT-based solver in OR-TOOLS. Very different approach, so it may have the possibility to do better than MIP. Would need integer cost coefficients. $\endgroup$ Commented Aug 4, 2022 at 10:18
  • $\begingroup$ Cross Posted on OR.SE: Methods for binary linear programming $\endgroup$ Commented Aug 25, 2022 at 16:34

2 Answers 2

Reset to default
2
$\begingroup$

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).

$\endgroup$
6
  • $\begingroup$ Thanks for the effort. However, David's answer about total unimodularity was enough for me, and I know exactly what to do with it. I'm looking for other similar tips (besides total unimodularity). $\endgroup$ Commented Aug 3, 2022 at 11:58
  • 1
    $\begingroup$ @ZoharLevi OK. I am afraid I have nothing to say about the other points you mention :-) So let's try a different kind of tip: you could post this question on the Operations Research stackexchange site. I did not find it there. or.stackexchange.com $\endgroup$ Commented Aug 3, 2022 at 12:27
  • $\begingroup$ Posted: or.stackexchange.com/questions/8822/… $\endgroup$ Commented Aug 3, 2022 at 21:59
  • $\begingroup$ @ZoharLevi I'm afraid the posting on Operations Research stackexchange backfired, because people dit not like the fact that you linked the question, instead of copying it fully... Oh well... To be honest, although I work in the OR field, I am not familiar with the OR stackexchange site. It's just that it sounds logical to post such a question there. $\endgroup$ Commented Aug 4, 2022 at 7:51
  • 1
    $\begingroup$ OR SE is a valid location for the question. Just dropping a link to this one is insufficient for a couple of reasons. The lesser one (IMO) is that it adds to the workload of anyone trying to answer. The bigger one is that questions are sometimes removed from SE sites, and if this one is removed the question on OR SE (with a dead link) becomes more or less indecipherable. $\endgroup$ Commented Aug 4, 2022 at 21:08
0
$\begingroup$

What I wanted and more, in chapters 5 and 19 in

Schrijver 1998, "Theory of linear and integer programming"

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.