I have worked with LP & IP with solvers like Gurobi and CPLEX. To play around the processes of encoding some practical problem, I am learning how to construct a dual LP from https://en.wikipedia.org/wiki/Dual_linear_program.
However, It seems that this algorithm for LP (continuous variables) does not work for 0-1 integer programming (binary variables).
If the primal 0-1 IP is as follows:
- $n$ binary variables $x_1, \cdots, x_n$
- maximize $c_1 x_1 +\cdots + c_n x_n $, where $c_i$ are all integers.
- $m$ constraints: $a_{j1} x_1 +\cdots + a_{jn} x_n \leq b_j $, or, $a_{j1} x_1 +\cdots + a_{jn} x_n = b_j $, where all coefficients are integers.
How to construct the dual program?