Dual formulations and subgradient optimization strategies for linear programming relaxations of mixed-integer programs (Q1110459)

This is mainly an algorithmic paper concerned with the solution of mixed integer linear programs, with special reference to zero-one mixed integer linear programs. The method involves adding additional redundant constraints to the programming problem in order to tighten the linear programming relaxation of the Lagrangian dual. Several such duals are investigated computationally. Test problems of the following form are considered. \[ \text{Minimize }cx+dy\quad s.t.\quad Ax+Bx\geq b,\quad x\in X,\quad y\in Y,\quad y\text{ integer} \] where \(X=\{x\in R^ n:\) \(x\geq 0\), \(\sum x_ i\leq \alpha \}\), and \(Y=\{y\in R^ m:\) \(Ey\geq f\), \(0\leq y\leq 1\}\), where \(Ey\geq f\) are set covering constraints with f and 1 being appropriate vectors of ones, and with the zero-one matrix E having at least two ones in each row. The constraint \(\sum x_ i\leq \alpha\) is assumed to be redundant for LP, and its principal function is to ensure a dual feasible solution. One of the Lagrangian duals derived by studying the constraints \(Ax+By\geq b\), \(Ey\geq f\) is of the form: maximize \(\{\phi(u,v): (u,v)\in W\}\) where \(\phi(u,v)= ub+vf+\min\{(c-uA)x:\) \(x\in X\}+\min \{(d-uB-vE)y:\) \(0\leq y\leq 1\{\), and \(W=\{(u,v):\) \(u\geq 0\), \(v\geq 0\}\). Algorithms for solution are described and computational experience on small and large problems for several types of dual formulation are given.