Mixed integer bilinear programming with applications to the pooling problem

Cutting planes;Pooling problem;Sequential knapsack;McCormick envelopes;Integer programming;Bilinear

Gupte, Akshay ; Industrial and Systems Engineering

University:Georgia Institute of Technology

Department:Industrial and Systems Engineering

关键词: Cutting planes;    Pooling problem;    Sequential knapsack;    McCormick envelopes;    Integer programming;    Bilinear;   

Others  :  https://smartech.gatech.edu/bitstream/1853/45761/1/gupte_akshay_s_201212_phd.pdf

美国|英语

来源: SMARTech Repository

【 摘 要 】

Solution methodologies for mixed integer bilinear problems (MIBLP) are studied in this dissertation. This problem class is motivated using the pooling problem, a multicommodity network flow problem that typically arises in chemical engineering applications. Stronger than previously known results are provided to compare the strengths of polyhedral relaxations of the pooling problem. A novel single node flow relaxation, defined by a bilinear equality constraint and flow balance, is proposed for the pooling problem. Linear valid inequalities in the original space of variables are derived using a well-known technique called lifting. Mixed integer linear (MILP) formulations are proposed for generating feasible solutions to the pooling problem. Some of these MILP models arise from variable discretizations while others possess a network flow interpretation. The effectiveness of these MILP models is empirically validated on a library of medium and large-scale instances. General MIBLPs, not necessarily pooling problems, are solved using extended MILP reformulations. The reformulation is obtained by writing binary representation for each general integer variable. Facet-defining inequalities are provided for the reformulation of each bilinear term. New valid inequalities are also proposed for bilinear terms with a nontrivial upper bound. The proposed reformulation and cutting planes are compared against a global solver on five different classes of MIBLPs.