The research objective of this award is to create and evaluate new cutting plane methods for mixed integer programming using a new approach here called Complex Integer Rounding. Cutting planes are a crucial part of the algorithms used for solving mixed integer programming problems. Mixed integer programming is an optimization framework with numerous applications in science, engineering, and business. The proposed approach consists of deriving novel forms of three major elements and making innovative use of them: one or multiple facets of base polyhedra and/or one or multiple sub-additive functions are utilized within a relaxation/combination procedure which is applied on the original constraints and a series of intermediate inequalities to eventually obtain a cut generator function. Both single-constraint and multi-constraint cuts will be considered and facet-defining properties of the developed cuts will be investigated. The customization of the cuts to a collection of important special-structure problems will be studied. In order to evaluate performance of the developed cuts, efficient separation methods will be developed and comprehensive computational experiments will be performed.
Mixed integer programming is a powerful and flexible optimization paradigm with ubiquitous applications in science, engineering, and business ranging from flight crew scheduling to molecular biology. Yet solving mixed integer programs is generally very difficult. Through introduction of new strong cutting planes, this research, if successful, will result in faster solution algorithms for mixed integer programming and will increase the size of the problems that we are able to solve. Consequently, it will have a significant impact on all aforementioned areas. Moreover, the methodological developments in this research open doors to several new research avenues regarding cutting plane methods.
This grant was aimed at creating new cutting plane methods for mixed integer programming problems (MIPs) using a new approach called Complex Integer Rounding (CIR). MIPs are mathematical optimization tools that are used to make complicated decisions in business, science, and engineering involving decisions of discrete nature. Application domains of MIP are vast including decision-making problems in manufacturing systems, service systems, data centers, telecommunication, oil industry, pharmaceuticals, transportation, health care, biology, and many more. MIP problems are notoriously hard and time-consuming to solve, even with today’s computational power. Development of effective "cutting plane theories" for MIPs is a major approach in reducing the computational time required to solve them. This grant resulted in several new CIR cutting plane theories for MIPs and proved that application of these theories in solving certain classes of MIPs results in very significant reduction of their computational solution time. This means that by using the theories generated in this grant several sectors of economy can solve their large MIP decision making problems in a shorter amount of time, which immediately translates into achieving better decisions within the same time windows. As a result, the outcomes of this grant have a very broad impact on improving efficiency and reducing cost in a vast array of applications. The research team first developed the CIR cutting plane theory referred to as the mixed n-step MIR cuts by studying a new multi-constraint base polyhedron called the n-mixing set and developing base facets for it. The team demonstrated that these inequalities have strong facet-defining capabilities and also derived the mixed n-step MIR subadditive functions that can be used to generate these inequalities. Through computational experiments it was shown that these cuts can be effective in solving general MIPs and very effective in solving special structured MIPs. A major special structure studied was the multi-module lot-sizing (MML) problem introduced by the research team which has several applications in modular capacity planning where the modules have different sizes. The mixed n-step MIR cuts were very effective in solving MML problems. The team then successfully generalized the mixed n-step MIR cuts to a much larger class of CIR cuts referred to as the n-step cycle inequalities. These inequalities were derived by studying a generalization of the n-mixing set called continuous multi-mixing set and deriving base facets for it. These cuts encompass several families of important cutting planes previously introduce in the literature while introducing many new ones. It was shown that these cuts are facet-defining (and hence strong) in many cases. The team developed an extended formulation for the continuous multi-mixing set using these cuts and also devised an exact separation algorithm for them. The performance of these cuts over MML problems using the exact separation algorithm was studied. It was found out that these cuts are extremely effective in solving MML problems and reduce their solution time by orders of magnitude. By establishing a relationship between the mixed integer knapsack set and the mixed integer polyhedral conic set, the team showed that corresponding to any cut for the mixed integer knapsack set, a cut can be generated for a mixed integer polyhedral conic set. As the literature on generating cuts for mixed integer knapsack set is quite rich, this result translates all that literature into a literature for the mixed integer polyhedral conic set. It was proved that these cuts dominate the conventional method to generate cuts for such sets. Computational experiments showed that this dominance can be quite significant. As a special case the team then introduced a new family of CIR cuts called the n-step conic MIR inequalities for the mixed integer polyhedral conic set and proved their facet-defining properties. In a different direction, it was also shown that the n-step MIR cuts for the mixed integer knapsack set encompass the well-known partition inequalities for the mixed integer knapsack set with divisible constraints and generalize them to the case of non-divisible coefficients. As a result, facet-defining CIR cuts for several mixed integer flow sets were also introduced. The intellectual contributions of this grant also opened doors to several new research avenues in the field. In particular, the results have created an excellent machinery to start research on cutting planes for capacity planning problems with capacity modules of different sizes. This research is being pursued by the team as under a new NSF grant. Two Ph.D. students completed their dissertation research on this grant. The research outcomes were greatly incorporated in two graduate courses. Five publications in high-quality journals, 13 presentations in high-impact conferences such as IPCO, MIP, INFORMS, and CMMI Grantees conference, and a departmental seminar disseminated the results of this research. The publications and finalized data sets are and will be publicly shared on the project website at http://ise.tamu.edu/people/faculty/kianfar/modal/.
