In recent years there has been growing interest in generating valid inequalities for mixed-integer programs using sets with 2 or more constraints. In particular, Andersen et.al (2007) and Borozan and Cornuéjols (2007) study sets de ned by equations that contain exactly one integer variable per row. The integer variables are not restricted in sign. Cutting planes based on this approach have already been used by Espinoza [12] for general mixed-integer problems and there is also ongoing computational research in this area.
In this paper, we restrict the model studied in the earlier papers and require the integer variables to be non-negative. We extend the results in Andersen et.al (2007) and Borozan and Cornuéjols (2007) to our case and show that cuts generated by their approach can be strengthened by using the non-negativity of the integer variables. In particular, it is possible to obtain cuts which have negative coecients for some variables.
By: Ricardo Fukasawa, Oktay Günlük
Published in: RC24798 in 2009
LIMITED DISTRIBUTION NOTICE:
This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.
Questions about this service can be mailed to reports@us.ibm.com .