I am currently trying to solve a binary integer programming(maximization) problem, where the first row of the constraint matrix corresponds to the constraints on the total number of 1's in the vector of variables (x). The overall constraint matrix A is not TUM. However, the polyhedron defined by the system $Ax\le b $ is integral for some of the $b$ vectors. Specifically, for some of the values of first element(while keeping the others fixed) of the $b$ vector, which corresponds to the aforementioned constraint, I am getting integer polyhedron integer optimal solution. My question is: is there any way to know beforehand that which values of the first element of $b$ vector (keeping the other co-ordinates fixed) will lead to integral polyhedra or give me integer solution?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ TUM = Totally Unimodular Matrix, I guess $\endgroup$– Moritz FirschingCommented Jul 26, 2017 at 12:25
-
$\begingroup$ Yes,Totally Unimodular Matrix. $\endgroup$– A.2Commented Jul 26, 2017 at 13:04
Add a comment
|