8
$\begingroup$

I have a MILP in the following form

maximize $${\bf c}^T{\bf x}$$

subject to

$${\bf Ax}\le {\bf b}$$

Matrix ${\bf A}$ is a binary matrix, and very sparse. It is a larger matrix with 300 rows and 1000 columns. Only 4000 elements are 1s while the remaining entries are 0.

${\bf x}$ is a binary decision variable.

The entries in ${\bf b}$ are all integers.

By relaxing ${\bf x}$, I transform this into an LP.

Luckily, when I solve this problem by making decision variables continuous, I get the optimized variable are already binary! I do not need to round them at all?

Why is this happening? I mean, why do I get a binary solution even when I try to solve an LP problem, not MILP? Of course, I prefer this solution, as my original problem is MILP.

Are any characteristics of matrix ${\bf A}$ helping this to happen, ie., to have a binary solution readily available?.

$\endgroup$

1 Answer 1

14
$\begingroup$

Totally unimodular (see added tag) constraint matrices have this property. One common example is when the constraint matrix corresponds to a network flow problem, with one variable per arc and one constraint per node.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.