Define input as an ILP?

[danyaljj]

A small question: can I use your library as ILP solver? in other words, can I use, say your BP, in order to solver an ILP?

[analog-cbarber]

In general, no.

BP will only give you an approximate answer if your graph is not singly connected. However, if your graph uses only discrete variables and is singly connected (or is small enough to be made singly connected using the JunctionTree algorithm) then you can solve some ILP problems using BP.

[danyaljj]

There is no question that the solution will be approximate. Let's say I have a well-defined problem with discrete values and singly connected graph. The main question I have is the format in which we define an input problem. Here is an example code I found for Dimple:

Now the question is, let's say I have a problem in the following format:

How would you go for coding such problem in Dimple? Is there any intermediate representation based on ILP in your system?

[analog-cbarber]

First, this is only going to work if you are working with a relatively small bounded subset of Z, as is the case with the parity check example.

There is no pre-canned code for converting the standard ILP formulation into a graphical model in dimple, but here is how I think you would go about it:

• Create a DiscreteDomain for your variables
• Add n variables for each element of the vector x
• Add n cost factors attached to each variable whose energy will be equal to cⁱ * xⁱ
• For each row aⁱ of the matrix A, add a factor attached to the corresponding variables with non-zero entries in the row of A and whose evalEnergy function will return zero/infinity depending on whether that row the constraint is satisfied (i.e. <aⁱ, x> <= bⁱ)
• Use the min-sum solver or the JunctionTreeMAPSolver.