Search

We study the unequal circle-circle non-overlapping constraints, a form of reverse convex constraints that often arise in optimization models for cutting and packing applications. The feasible region induced by the intersection of circle-circle non-overlapping constraints is highly non-convex, and standard approaches to construct convex relaxations for spatial branch-and-bound global optimization of such models typically yield unsatisfactory loose relaxations. Consequently, solving such non-convex models to guaranteed optimality remains extremely challenging even for the state-of-the-art codes. In this paper, we apply a purpose-built branching scheme on non-overlapping constraints and utilize strengthened intersection cuts and various feasibility-based tightening techniques to further tighten the model relaxation. We embed these techniques into a branch-and-bound code and test them on two variants of circle packing problems. Our computational studies on a suite of 75 benchmark instances yielded, for the first time in the open literature, a total of 54 provably optimal solutions, and it was demonstrated to be competitive over the use of the state-of-the-art general-purpose global optimization solvers. [ABSTRACT FROM AUTHOR]

Abstract: Environmental Protection Agency (EPA) Title 40 Code of Federal Regulations Part 80.45: Complex Emissions Model [40CFR80.45, 2007] codifies a mathematical model of gasoline emissions for reformulated gasoline (RFG) as a function of eleven fuel properties. In this paper we propose an extended pooling problem to maximize the profit of blending reformulated gasoline on a predetermined network structure of feed stocks, intermediate storage tanks, and gasoline products subject to applicable environmental standards. A mixed-integer nonlinear programming (MINLP) model is introduced which is nonconvex due to the presence of bilinear, polynomial, and fractional power terms. A mixed-integer linear programming (MILP) relaxation of the extended pooling problem is proposed and we introduce several test cases from small to medium to large scale and solve them to global optimality. The large-scale test case involves 14 feed stocks, 5 pools, and 10 products and consists of 1104 continuous variables, 150 binary variables, and 640 nonlinear terms. The nonconvexities in the large-scale case study include 410 bilinear terms, 40 polynomial terms, and 10 terms raised to a fractional power. [Copyright &y& Elsevier]