Mohit Tawarmalani

Journal Publications

1. Nogaja, A., Tawarmalani, M., & Agrawal, R. (2024, accepted). Cogeneration improves separation efficiency. Industrial and Engineering Chemistry Research.

   Abstract

   For most distillation systems, the heat pump (HP) compressor, upgrading the heat from condenser’s lower temperature to the reboiler’s higher temperature uses electrical energy that is only a fraction of the reboiler heat thereby making such processes highly efficient. However, the electricity utilized to power the heat pump compressor is typically dissipated as waste heat in cooling water. Here we propose a novel strategy termed “Separation Cogeneration” whereby most of the electrical energy supplied to the HP compressor is recovered as steam or process heat at or higher than the reboiler temperature. Through simulations of several industrially relevant distillations, we find that 79% to nearly 90% of the supplied compressor electrical energy can be recovered as usable steam/process heat. This is a remarkably high first-law efficiency of the distillation cogeneration system and is likely to make it the most efficient among the alternative processes for separations where distillation can be used. Furthermore, the availability of alternative HP schemes, leeway in the choice of approach temperature across the reboiler heat exchanger and the distillation column pressure along with the potential use of multi-effect distillation provide a great deal of flexibility in adjusting the temperature at which steam/process heat could be recovered. Through several industrially relevant case studies, we demonstrate that for a given separation and generation of the associated steam, the separation cogeneration requires nearly 40% less electricity when compared to the two-step process using conventional HP distillation and steam generation using electricity. The separation cogeneration strategy holds the promise to further the decarbonization goal of the industrial sector, facilitating the efficient utilization of electricity and reducing greenhouse gas emissions.

2. Kim, J., Richard, J.-P. P., & Tawarmalani, M. (2024, accepted). A reciprocity between tree ensemble optimization and multilinear optimization. Operations Research.

   Abstract

   In this paper, we establish a low-degree polynomially-sized reduction between tree ensemble optimization and optimization of multilinear functions over a Cartesian product of simplices. We use this insight to derive new formulations for tree ensemble optimization problems and to obtain new convex hull results for multilinear polytopes. A computational experiment on multicommodity transportation problems with costs modeled using tree ensembles shows the practical advantage of our formulation relative to existing formulations of tree ensembles and other piecewise-linear modeling techniques.

3. He, T., Liu, S., & Tawarmalani, M. (2024, accepted). Convexification techniques for fractional programs. Mathematical Programming. Read it

   Abstract

   This paper develops a correspondence relating convex hulls of fractional functions with those of polynomial functions over the same domain. Using this result, we develop a number of new reformulations and relaxations for fractional programming problems. First, we relate 0-1 problems involving a ratio of affine functions with the boolean quadric polytope, and use inequalities for the latter to develop tighter formulations for the former. Second, we derive a new formulation to optimize a ratio of quadratic functions over a polytope using copositive programming. Third, we show that univariate fractional functions can be convexified using moment hulls. Fourth, we develop a new hierarchy of relaxations that converges finitely to the simultaneous convex hull of a collection of ratios of affine functions of 0-1 variables. Finally, we demonstrate theoretically and computationally that our techniques close a significant gap relative to state-of-the-art relaxations, require much less computational effort, and can solve larger problem instances.

4. He, T., & Tawarmalani, M. (2024, accepted). MIP relaxations in factorable programming. SIAM Journal on Optimization.

   Abstract

   In this paper, we develop new discrete relaxations for nonlinear expressions in factorable programming. We utilize specialized convexification results as well as composite relaxations to develop mixed-integer programming (MIP) relaxations. Our relaxations rely on ideal formulations of convex hulls of outer-functions over a combinatorial structure that captures local inner-function structure. The resulting relaxations often require fewer variables and are tighter than currently prevalent ones. Finally, we provide computational evidence to demonstrate that our relaxations close approximately 60-70% of the gap relative to McCormick relaxations and significantly improves the relaxations used in a state-of-the-art solver on various instances involving polynomial functions.

5. Kim, J., Richard, J.-P. P., & Tawarmalani, M. (2024, accepted). Piecewise polyhedral relaxations of multilinear optimization. SIAM Journal on Optimization.

   Abstract

   In this paper, we consider piecewise polyhedral relaxations (PPRs) of multilinear optimization problems over axis-parallel hyper-rectangular partitions of their domain. We improve formulations for PPRs by linking components that are commonly modeled independently in the literature. Numerical experiments with ALPINE, an open-source software for global optimization that relies on piecewise approximations of functions, show that the resulting formulations speed-up the solver by an order of magnitude when compared to its default settings. If given the same time, the new formulation can solve more than twice as many instances from our test-set. Most results on piecewise functions in the literature assume that the partition is regular. Regular partitions arise when the domain of each individual input variable is divided into nonoverlapping intervals and when the partition of the overall domain is composed of all Cartesian products of these intervals. We provide the first locally ideal formulation for general (non-regular) hyper-rectangular partitions. We also perform experiments that show that, for a variant of tree ensemble optimization problems, a formulation based on non-regular partitions outperforms that over regular ones by an order of magnitude.

6. Gooty, R. T., Agrawal, R., & Tawarmalani, M. (2024). Advances in MINLP to identify energy-efficient distillation configurations. Operations Research, 72, 639–659.

   Abstract

   In this paper, we describe the first mixed-integer nonlinear programming (MINLP)-based solution approach that successfully identifies the most energy-efficient distillation configuration sequence for a given separation. Current sequence design strategies are largely heuristic. The rigorous approach presented here can help reduce the significant energy consumption and consequent greenhouse gas emissions by separation processes. First, we model discrete choices using a formulation that is provably tighter than previous formulations. Second, we highlight the use of partial fraction decomposition alongside reformulation-linearization technique (RLT). Third, we obtain convex hull results for various special structures. Fourth, we develop new ways to discretize the MINLP. Finally, we provide computational evidence to demonstrate that our approach significantly outperforms the state-of-the-art techniques.

7. Chen, Z., Tawarmalani, M., & Agrawal, R. (2024). Global minimization of power consumptions for multicomponent gas membrane cascades. Computers & Chemical Engineering, 180, 108464.

   Abstract

   As an emerging separation technology, membrane has been applied to many applications, among which many require the separation of a multicomponent feed into desired products. In this work, we developed an MINLP formulation that, for a given multi-component feed, identifies the minimum power consumption and the corresponding optimal membrane cascade configuration. This MINLP formulation can simultaneously guarantee global optimality and accuracy for multicomponent membrane cascades. In this formulation, we introduced a new approximation model for multicomponent membrane module, which is much simpler than the model obtained by conventional collocation method. We also introduce several auxiliary variables which help us solve cascades with 6 components and up to 5 stages. We solved the resulting MINLPs to within 5% of global optimality. Finally we apply the algorithm to a H2 separation case and identified optimal membrane cascade configurations with 2, 3, and 4 compressors.

8. Mathew, T. J., Narayanan, S., Jalan, A., Matthews, L. R., Gupta, H., Billimoria, R., Pereira, C. S., Goheen, C., Tawarmalani, M., & Agrawal, R. (2024). Optimization of distillation configurations for multicomponent-product distillations. Computers & Chemical Engineering, 108628.

   Abstract

   Several optimization formulations exist in the literature for optimizing distillation configurations for unicomponent-product distillations (UPD), i.e., distillations where each product consists of only a single component. However, many separations either desire product streams composed of multiple components based on their end-use property requirements or tolerate such multicomponent products in exchange for savings in the objective, e.g., reductions in energy consumption. In this work, we propose an easy-to-use transformation that allows any UPD configuration to be used for multicomponent-product distillations (MPD) while controlling the composition of the product. This transformation is used in our optimization model to minimize the heat duty of MPD configurations derived from UPD for zeotropic separations. We apply this formulation to identify and rank energy-efficient configurations for an industrial crude petroleum case study, and show that the ordering of configurations on an energy efficiency basis is quite different using the MPD model compared to the UPD model.

9. Mathew, T. J., Tawarmalani, M., & Agrawal, R. (2023). Relaxing the constant molar overflow assumption in distillation optimization. AIChE Journal, 69(9), e18125.

   Abstract

   The constant molar overflow (CMO) framework, while useful for shortcut distillation models, assumes that all components have the same latent heats of vaporization. A simple transformation, from molar flows to latent-heat flows, allows shortcut models to retain the mathematical simplicity of the CMO framework while accounting for different latent heats, resulting in the constant heat transport (CHT) framework for adiabatic distillation columns. Although several past works have already proposed this transformation in the literature, it has not been well utilized in recent times. In this article, we show the utility of this transformation in upgrading various applications such as identifying energy-efficient multicomponent distillation configurations based on heat duty rather than surrogate vapor flow. The method transforms the Vmin diagram to a Qmin diagram. Furthermore, we derive new and insightful analytical results in distillation, such as cumulative latent-heat stage fractions having monotonic profiles within a distillation column under the CHT framework.

10. Gooty, R. T., Mathew, T. J., Tawarmalani, M., & Agrawal, R. (2023). An MINLP formulation to identify thermodynamically-efficient distillation configurations. Computers & Chemical Engineering, 178, 108369.

    Abstract

    Designing configurations for separation of multicomponent mixtures by distillation is challenging because of (i) combinatorial explosion of the choice set, and (ii) nonconvex nature of the governing equations. This work proposes a novel Mixed Integer Nonlinear Program (MINLP) that is formulated to identify configurations that minimize the total exergy loss/maximize thermodynamic efficiency of the separation process. The formulation in its default form has several nonlinear nonconvex equations. We propose a model reformulation via a simple variable elimination technique to reduce the system of nonlinear equations to a single equation, which we refer to as the exergy constraint. We describe the properties of exergy constraints and exploit them in deriving additional valid cuts for the problem. Finally, we use the model for a case study concerning the recovery of Natural Gas Liquids (NGLs) from shale gas.

11. He, T., & Tawarmalani, M. (2022). Tractable relaxations of composite functions. Mathematics of Operations Research, 47(2), 1110–1140.

    Abstract

    In this paper, we introduce new relaxations for the hypograph of composite functions assuming that the outer function is supermodular and concave extendable. Relying on a recently introduced relaxation framework, we devise a separation algorithm for the graph of the outer function over P, where P is a special polytope to capture the structure of each inner function using its finitely many bounded estimators. The separation algorithm takes O(dnlog(d)) time, where d is the number of inner functions and n is the number of estimators for each inner function. Consequently, we derive large classes of inequalities that tighten prevalent factorable programming relaxations. We also generalize a decomposition result and devise techniques to simultaneously separate hypographs of various supermodular, concave-extendable functions using facet-defining inequalities. Assuming that the outer function is convex in each argument, we characterize the limiting relaxation obtained with infinitely many estimators as the solution of an optimal transport problem. When the outer function is also supermodular, we obtain an explicit integral formula for this relaxation.

12. Kim, J., Tawarmalani, M., & Richard, J.-P. P. (2022). Convexification of permutation-invariant sets and an application to sparse principal component analysis. Mathematics of Operations Research, 47(4), 2547–2584.

    Abstract

    We develop techniques to convexify a set that is invariant under permutation and/or change of sign of variables and discuss applications of these results. First, we convexify the intersection of the unit ball of a permutation and sign-invariant norm with a cardinality constraint. This gives a nonlinear formulation for the feasible set of sparse principal component analysis (PCA) and an alternative proof of the K-support norm. Second, we characterize the convex hull of sets of matrices defined by constraining their singular values. As a consequence, we generalize an earlier result that characterizes the convex hull of rank-constrained matrices whose spectral norm is below a given threshold. Third, we derive convex and concave envelopes of various permutation-invariant nonlinear functions and their level sets over hypercubes, with congruent bounds on all variables. Finally, we develop new relaxations for the exterior product of sparse vectors. Using these relaxations for sparse PCA, we show that our relaxation closes 98% of the gap left by a classical semidefinite programming relaxation for instances where the covariance matrices are of dimension up to 50x50.

13. Chandra, A., & Tawarmalani, M. (2022). Probability estimation via policy restrictions, convexification, and approximate sampling. Mathematical Programming, 196(1), 309–345.

    Abstract

    This paper develops various optimization techniques to estimate probability of events where the optimal value of a convex program, satisfying certain structural assumptions, exceeds a given threshold. First, we relate the search of affine/polynomial policies for the robust counterpart to existing relaxation hierarchies in MINLP. Second, we leverage recent advances in Dworkin et al., Gawrychowski et al., and Rizzi and Tomescu to develop techniques to approximately compute the probability binary random variables from Bernoulli distributions belong to a specially-structured union of sets. Third, we use convexification, robust counterpart, and chance-constrained optimization techniques to cover the event set of interest with such set unions. Fourth, we apply our techniques to the network reliability problem, which quantifies the probability of failure scenarios that cause network utilization to exceed one. Finally, we provide preliminary computational evaluation of our techniques on test instances for network reliability.

14. Chavez Velasco, J. A., Tawarmalani, M., & Agrawal, R. (2022). Which separation scenarios are advantageous for membranes or distillations? AIChE Journal, 68(11), e17839.

    Abstract

    We systematically analyze power requirements of membrane and distillation processes for binary mixtures where the desired product component is more permeable and also more volatile. We first derive a shortcut method to compare the efficiency of heat pump and steam-driven distillations. Then, power requirements of heat pump distillation and membrane separation are discussed. Distillation generally requires lower power when either high component recoveries are needed (at all tested product purities), or high purity product streams with modest recoveries are needed. For high purity products at modest recoveries, membranes have a potential to provide energy benefits for highly enriched feeds, especially those composed of close boiling components. Additionally, when feed concentration is moderate to high and product recovery and purity are modest, membranes are likely to show efficiency gain. For the advantageous distillation scenarios studied, the power was generally lower than the membranes by a factor of two to seven.

15. Nogaja, A. S., Mathew, T. J., Tawarmalani, M., & Agrawal, R. (2022). Identifying heat-integrated energy-efficient multicomponent distillation configurations. Industrial & Engineering Chemistry Research, 61(37), 13984–13995.

    Abstract

    We present a tractable nonlinear programming (NLP) formulation that models a given multi-component distillation configuration and searches for its global minimum heat duty. The novelty in the current model is that it can explore feasible heat integrations with a pre-specified desired minimum approach temperature between various condensers and reboilers while simultaneously optimizing the operating conditions within the configuration. We do not use cumbersome thermodynamic models for the equilibrium temperature calculation of a saturated multicomponent mixture. Instead, we propose a modified version of the well-known Antoine equation that reduces the calculation of the temperature at a given pressure to a simple function of component mole fractions and relative volatilities while retaining the fidelity of more complex models. We explore possible heat integrations by creating a heat exchange network between column condensers, reboilers, and side draw product locations. Considering these integrations along with the heat duty minimization is essential because it is often possible to alter the operating conditions of the columns and reduce energy consumption by admitting more heat integration possibilities. Finally, we demonstrate the power of our framework in identifying optimal configurations that yield large energy savings for several four- and five-component zeotropic distillation systems.

16. Jiang, Z., Tawarmalani, M., & Agrawal, R. (2022). Minimum reflux calculation for multicomponent distillation in multi-feed, multi-product columns: Mathematical model. AIChE Journal, 68(12), e17929.

    Abstract

    Multi-feed, multi-product distillation columns are ubiquitous in multicomponent distillation systems. The minimum reflux ratio of a distillation column is directly related to its energy consumption and capital cost. Thus, it is a key parameter for distillation systems design, operation, and comparison. In this series, we present the first accurate shortcut based algorithmic method to determine the minimum reflux condition for any general multi-feed, multi-product (MFMP) distillation column separating any ideal multicomponent mixture. The classic McCabe-Thiele or Underwood method is a special case of this general approach. Compared with existing techniques, this method does not involve any rigorous tray-by-tray calculation, nor does it require guessing of key components. In this first part of the series, we present the mathematical model for a general MFMP column, derive constraints for feasible separation and minimum reflux condition, discuss their geometric interpretations, and present an illustrative example to demonstrate the effectiveness of our approach.

17. Mathew, T. J., Narayanan, S., Jalan, A., Matthews, L., Gupta, H., Billimoria, R., Pereira, C. S., Goheen, C., Tawarmalani, M., & Agrawal, R. (2022). Advances in distillation: Significant reductions in energy consumption and carbon dioxide emissions for crude oil separation. Joule, 6(11), 2500–2512.

    Abstract

    Crude distillation, with a long history of research and commercial improvements, is perceived to be a mature separation technology with minimal scope of improvement. By systematically searching alternative configurations, this work, through an end-to-end case study, has identified new distillation configuration options that consume 15% less energy than their conventional industrial counterparts. This accompanies a 16% reduction in carbon dioxide equivalent (CO2e) emissions, which is a significant accomplishment for a mature technology whose flowsheets are among the most complicated in distillation. The algorithms used for this search are the product of a decade of research; they were developed utilizing academic separation data and adapted here to apply to commercial distillation options so that they capture the distillation process physics more accurately. These algorithms are widely applicable and can be used to synthesize and design general non-azeotropic multicomponent distillation configurations for industrial separations.

18. Nguyen, T. T., Richard, J.-P. P., & Tawarmalani, M. (2021). Convexification techniques for linear complementarity constraints. Journal of Global Optimization, 80, 249–286.

    Abstract

    We develop convexification techniques for mathematical programs with complementarity constraints. Specifically, we adapt the reformulation-linearization technique of Sherali and Adams (SIAM J Discrete Math 3, 411–430, 1990) to problems with linear complementarity constraints and discuss how this procedure reduces to its standard specification for binary mixed-integer programs. Then, we consider specially structured complementarity sets that appear in KKT systems with linear constraints. For sets with a single complementarity constraint, we develop a convexification procedure that generates all nontrivial facet-defining inequalities and has an appealing “cancel-and-relax” interpretation. This procedure is used to describe the convex hull of problems with few side constraints in closed-form. As a consequence, we delineate cases when the factorable relaxation techniques yield the convex hull from those for which they do not. We then discuss how these results extend to sets with multiple complementarity constraints. In particular, we show that a suitable sequential application of the cancel-and-relax procedure produces all nontrivial inequalities of their convex hull. We conclude by illustrating, on a set of randomly generated problems, that the relaxations we propose can be significantly stronger than those available in the literature.

19. He, T., & Tawarmalani, M. (2021). A new framework to relax composite functions in nonlinear programs. Mathematical Programming, 190, 427–466.

    Abstract

    In this paper, we devise new relaxations for composite functions, which improve the prevalent factorable relaxations, without introducing additional variables, by exploiting the inner-function structure. We outer-approximate inner-functions using arbitrary under- and over-estimators and then convexify the outer-function over a polytope P, which models the ordering relationships between the inner-functions and their estimators and utilizes bound information on the inner-functions as well as on the estimators. We show that there is a subset Q of P, with significantly simpler combinatorial structure, such that the separation problem of the graph of the outer-function over P is polynomially equivalent, via a fast combinatorial algorithm, to that of its graph over Q. We specialize our study to consider the product of two inner-functions with one non-trivial underestimator for each inner-function. For the corresponding polytope P, we show that there are eight valid inequalities besides the four McCormick inequalities, which improve the factorable relaxation. Finally, we show that our results generalize to simultaneous convexification of a vector of outer-functions.

20. Chavez Velasco, J. A., Tawarmalani, M., & Agrawal, R. (2021). Systematic analysis reveals thermal separations are not necessarily most energy intensive. Joule, 5(2), 330–343.

    Abstract

    At the industrial level, separation of a variety of mixtures is predominantly carried out by thermally driven processes such as distillation. Nevertheless, the current literature seems to suggest that much is to be gained by replacing these processes with alternative non-thermal methods, which will potentially require a fraction of the energy used by distillation. This is primarily due to the widespread perception that thermal separation processes, particularly those that involve vaporization, are highly energy intensive. However, this belief is not well founded, because it is based on extrapolation from comparisons in the literature, many of which make ad-hoc assumptions and result in incorrect conclusions. Our analysis shows that this confusion arises because the processes utilize different types of energy: heat and electricity. Here, we present a consistent framework that enables a fair comparison between different processes that consume different forms of energies. Using this framework, we refute the general perception that thermal separation processes are inherently the most energy intensive and conclusively show through the examples of two challenging mixtures constituting components with low relative volatilities, that distillation processes, when run properly, can consume remarkably lower fuel than non-thermal membrane alternatives, which have often been touted as more energy efficient.

21. Chavez Velasco, J. A., Gooty, R. T., Tawarmalani, M., & Agrawal, R. (2021). Optimal design of membrane cascades for gaseous and liquid mixtures via MINLP. Journal of Membrane Science, 636, 119514.

    Abstract

    Given the growing concern of reducing CO2 emissions, it is desirable to identify, for a given separation carried out through a membrane cascade, the optimum design that yields the lowest power demand. Nevertheless, designing a membrane cascade is challenging since, there are often multiple feasible configurations that differ in their energy consumption and cost. In this work, we develop a Mixed Integer Non-linear Program (MINLP) that, for a given binary separation, which may be either liquid or gaseous, finds the cascade and its operating conditions that minimize power requirement. To model the separation at each membrane in the cascade, we utilize the analytical solution of a system of differential and algebraic equations derived from the crossflow model and the solution–diffusion theory. We provide numerical evidence which shows that our single-stage membrane model accurately predicts experimental data. The resulting membrane model is non-convex and, even state-of-the-art solvers struggle to prove global optimality of the cascades and the operating conditions identified. In this paper, we derive various cuts that help with relaxation quality and, consequently, accelerate convergence of branch-and-bound based solvers. More specifically, we demonstrate, on various examples, that our cuts help branch-and-bound solvers converge within 5% optimality gap in a reasonable amount of time and such a tolerance level was not achieved by a simple formulation of the membrane model. The proposed optimization model is an easy-to-use tool for practitioners and researchers to design energy efficient membrane cascades.

22. Mathew, T. J., Tumbalam Gooty, R., Tawarmalani, M., & Agrawal, R. (2021). A simple criterion for feasibility of heat integration between distillation streams based on relative volatilities. Industrial & Engineering Chemistry Research, 60(28), 10286–10302.

    Abstract

    In a multicomponent distillation configuration, there are numerous sources and sinks of heat, and a potential way to reduce the heat duty requirement is to perform heat integration. Unfortunately, an algorithmic search of the optimal heat integration opportunities is intractable when the required temperatures of intermediate streams are computed via complex models. Instead, in this work, we introduce pressure-scaled pseudo relative volatility, a new metric to compare stream temperatures. We justify the use of pseudo relative volatility by proving that this variable is a monotonically increasing function of the liquid fraction in a saturated mixture stream. Using this metric, we derive a shortcut criterion to check the feasibility of various heat integration opportunities, such as thermal coupling via heat transfer (TCH). The advantage of this approach is that it circumvents the need for explicit temperatures and instead relies on composition, component relative volatilities, and pressure—quantities that are readily available in shortcut models for optimization of distillation configurations. Leveraging this fact, we propose a new optimization framework that identifies feasible TCHs that we consider within the formulation while minimizing the total heat duty of a distillation configuration. We demonstrate, on a few examples, that our formulation can identify heat duty efficient configurations, some of which are multieffect configurations. Using this methodology, we discover configurations that are not only simpler than the fully thermally coupled (FTC) configuration but also have a much lower heat duty.

23. Kim, J., Tawarmalani, M., & Richard, J.-P. P. (2019). On cutting planes for cardinality-constrained linear programs. Mathematical Programming, 178, 417–448.

    Abstract

    We derive cutting planes for cardinality-constrained linear programs. These inequalities can be used to separate any basic feasible solution of an LP relaxation of the problem, assuming that this solution violates the cardinality requirement. To derive them, we first relax the given simplex tableau into a disjunctive set, expressed in the space of nonbasic variables. We establish that coefficients of valid inequalities for the closed convex hull of this set obey ratios that can be computed directly from the simplex tableau. We show that a transportation problem can be used to separate these inequalities. We then give a constructive procedure to generate violated facet-defining inequalities for the closed convex hull of the disjunctive set using a variant of Prim’s algorithm.

24. Wu, J., Tawarmalani, M., & Kannan, K. N. (2019). Cardinality bundling with Spence–Mirrlees reservation prices. Management Science, 65(4), 1891–1908.

    Abstract

    We study the pricing of cardinality bundles, where firms set prices that depend only on the size of the purchased bundle, a practice that is increasingly being adopted by industry. The model we study, where consumer choices are discrete, was originally proposed by Hitt and Chen [Hitt L, Chen P (2005) Bundling with customer self-selection: A simple approach to bundling low-marginal-cost goods. Management Sci. 51(10):1481–1493], and it requires that consumers’ preferences obey the Spence–Mirrlees single-crossing property. We correct prior approaches and develop various structural and managerial insights. We develop a fast combinatorial technique to obtain the optimal prices. We extend our analysis to address a quantity discount problem originally proposed in Spence [Spence M (1980) Multi-product quantity-dependent prices and profitability constraints. Rev. Econom. Stud. 47(5):821–841]. We provide examples that demonstrate that the proposed approach of Spence (1980) only identifies local optima without providing guidance on selecting the globally optimal pricing function. Our insights from the discrete model are extended to this context to develop a scheme that provides solutions within an arbitrary prespecified tolerance. Consequently, we also solve the continuous version of the cardinality bundling problem.

25. Gooty, R. T., Agrawal, R., & Tawarmalani, M. (2019). An MINLP formulation for the optimization of multicomponent distillation configurations. Computers & Chemical Engineering, 125, 13–30.

    Abstract

    Designing configurations for multicomponent distillation, a ubiquitous process in chemical and petrochemical industries, is often challenging. This is because, as the number of components increases, the number of admissible distillation configurations grows rapidly and these configurations vary substantially in their energy needs. Consequently, if a method could identify a few energy-efficient choices from this large set of alternatives, it would be extremely attractive to process designers. This paper develops such a method by solving a Mixed Integer Nonlinear Program (MINLP) that is formulated to pick, among the regular-column configurations of Shah and Agrawal (2010b), those configurations that have a low vapor-duty requirement. To compute the minimum vapor-duty requirement for each column within the configuration, we use techniques that rely on the Underwood’s method. The combined difficulty arising from the nonlinearity of Underwood equations and the combinatorial explosion of the choice-set of alternatives poses unmistakable challenges for the branch-and-bound algorithm, the current method of choice to globally solve MINLPs. To address this difficulty, we exploit the structure of Underwood equations and derive valid cuts that expedite the convergence of branch-and-bound by enabling global solvers, such as BARON, infer tighter bounds on Underwood roots. This provides a quick way to identify a few lucrative alternative configurations for separation of a given non-azeotropic mixture. We illustrate the practicality of our approach on a case-study concerning heavy-crude distillation and on various other examples from the literature.

26. Jiang, Z., Mathew, T. J., Zhang, H., Huff, J., Nallasivam, U., Tawarmalani, M., & Agrawal, R. (2019). Global optimization of multicomponent distillation configurations: Global minimization of total cost for multicomponent mixture separations. Computers & Chemical Engineering, 126, 249–262.

    Abstract

    We introduce a global optimization framework for determining the minimum cost required to distill any ideal or near-ideal multicomponent mixture into its individual constituents using a sequence of columns. This new framework extends the Global Minimization Algorithm (GMA) previously introduced by Nallasivam et al. (2016); and we refer to the new framework as the Global Minimization Algorithm for Cost (GMAC). GMAC guarantees global optimality by formulating a nonlinear program (NLP) for each and every distillation configuration in the search space and solving it using global optimization solvers. The case study presented in this work not only demonstrates the need for developing such an algorithm, but also shows the flexibility and effectiveness of GMAC, which enables process engineers to design and retrofit energy efficient and cost-effective distillation configurations.

27. Jiang, Z., Chen, Z., Huff, J., Shenvi, A. A., Tawarmalani, M., & Agrawal, R. (2019). Global minimization of total exergy loss of multicomponent distillation configurations. AIChE Journal, 65(11), e16737.

    Abstract

    The operating cost of a multicomponent distillation system comprises two major aspects: the overall heat duty requirement and the temperature levels at which the heat duties are generated and rejected. The second aspect, often measured by the thermodynamic efficiency of the distillation system, can be quantified by its total exergy loss. In this article, we introduce a global optimization framework for determining the minimum total exergy loss required to distill any ideal or near-ideal multicomponent mixture using a sequence of columns. Desired configurations identified by this new framework tend to use milder-temperature reboilers and condensers and are thus attractive for applications such as heat pump assisted distillation. Through a case study of shale gas separations, we demonstrate the effectiveness of this framework and present various useful physical insights for designing energy efficient distillation systems.

28. Mathew, T. J., Tumbalam Gooty, R., Tawarmalani, M., & Agrawal, R. (2019). 110th anniversary: Thermal coupling via heat transfer: A potential route to simple distillation configurations with lower heat duty. Industrial & Engineering Chemistry Research, 58(47), 21671–21678.

    Abstract

    Numerous configurations are available for the separation of a multicomponent mixture by distillation; each of which has different energy requirements. We classify heat integration (a valuable method of reducing energy requirements) within distillation into two categories: conventional thermal coupling with mass exchange between columns (TCM) and thermal coupling via heat transfer without mass exchange (TCH). The sharp split distillation configurations, with the lowest number of distillation sections and transfer streams, provide simple distillation configurations but are known to have heat duties that are much higher than the fully thermally coupled (FTC) or Petlyuk configuration. However, for a mixture with four or more components, FTC, having the maximum number of column sections, is a complex configuration to build and operate. Through specific examples of four and five component distillations, we present, for the first time, sharp split configurations, using only one TCH and no TCM, which have a lower heat duty than the corresponding FTC containing only TCM, without requiring substantial pressure changes in the system.

29. Ramapriya, G. M., Tawarmalani, M., & Agrawal, R. (2018). A systematic method to synthesize all dividing wall columns for n-component separation: Part II. AIChE Journal, 64(2), 660–672.

    Abstract

    We present a simple rule that, for the first time, enables exhaustive enumeration of dividing wall columns (DWCs) corresponding to any given thermally coupled distillation column-configuration. With the successive application of our rule, every partition in a DWC can be extended all the way to the top and/or to the bottom of a column without losing thermodynamic equivalence to the original thermally coupled configuration. This leads to easy-to-operate DWCs with possible control/regulation of each and every vapor split by external means. As a result, we conclude that any given DWC can be transformed into a thermodynamically equivalent form that is easy-to-operate, and hence, there always exists at least one easy-to-operate DWC for any given thermally coupled distillation. Our method of enumerating and identifying easy-to-operate DWCs for an attractive thermally coupled configuration will contribute toward process intensification by providing ways to implement efficient and low-cost multicomponent distillations.

30. Nguyen, T. T., Richard, J.-P. P., & Tawarmalani, M. (2018). Deriving convex hulls through lifting and projection. Mathematical Programming, 169, 377–415.

    Abstract

    We consider convex hull descriptions for certain sets described by inequality constraints over a hypercube and propose a lifting-and-projection technique to construct them. The general procedure obtains the convex hulls as an intersection of semi-infinite families of linear inequalities, each derived using lifting techniques that are interpreted using convexification tools. We demonstrate that differentiability and concavity of certain perturbation functions help reduce the number of inequalities needed for this characterization. Each family of inequalities yields a few linear/nonlinear constraints fully characterized in the space of the original problem variables, when the projection problems are amenable to a closed-form solution. In particular, we illustrate the complete procedure by constructing the convex hulls of the subsets of a compact hypercube defined by the constraints x₁^b₁x₂^b₂ ≥ x₃ and x₁x₂^b₂ ≥ x₃, where b₁, b₂ ≥ 1. As a consequence, we obtain a closed-form description of the convex hull of the bilinear equality , in the presence of variable bounds, as an intersection of a few linear and nonlinear inequalities. This explicit characterization, hitherto unknown, can improve relaxation techniques for factorable functions, which utilize this equality to relax products of functions with known relaxations.

31. Ramapriya, G. M., Tawarmalani, M., & Agrawal, R. (2018). A systematic method to synthesize all dividing wall columns for n-component separation—Part I. AIChE Journal, 64(2), 649–659.

    Abstract

    We present an easy-to-use step-wise procedure to synthesize an initial-dividing wall column (i-DWC) from any given n-component basic distillation column sequence or its thermally coupled derivative. The procedure to be used is dependent on the nature of the distillation column sequence that is to be converted into a DWC, and comprises of an intuitive set of steps that we demonstrate through examples. It is noteworthy that, even for a ternary distillation, 15 potentially useful DWCs, some of which had been missing from the literature, have now been identified. This work significantly expands the search space of useful DWCs to separate any given multicomponent mixture.

32. Jiang, Z., Ramapriya, G. M., Tawarmalani, M., & Agrawal, R. (2018). Minimum energy of multicomponent distillation systems using minimum additional heat and mass integration sections. AIChE Journal, 64(9), 3410–3418.

    Abstract

    Heat and mass integration to consolidate distillation columns in a multicomponent distillation configuration can lead to a number of new energy efficient and cost-effective configurations. In this work, a powerful and simple-to-use fact about heat and mass integration is identified. The newly developed heat and mass integrated configurations, which we call as HMP configurations, involve first introducing thermal couplings to all intermediate transfer streams, followed by consolidating columns associated with a lighter pure product reboiler and a heavier pure product condenser. A systematic method of enumerating all HMP configurations is introduced. The energy savings of HMP configurations is compared with the well-known fully thermally coupled (FTC) configurations. HMP configurations can have very similar and sometimes even the same minimum total vapor duty requirement as the FTC configuration is demonstrated, while using far less number of column sections, intermediate transfer streams, and thermal couplings than the FTC configurations.

33. Ramapriya, G. M., Selvarajah, A., Jimenez Cucaita, L. E., Huff, J., Tawarmalani, M., & Agrawal, R. (2018). Short-cut methods versus rigorous methods for performance-evaluation of distillation configurations. Industrial & Engineering Chemistry Research, 57(22), 7726–7731.

    Abstract

    This study demonstrates the efficacy of a short-cut method such as the Global Minimization Algorithm (GMA), (1,2) that uses assumptions of ideal mixtures, constant molar overflow (CMO) and pinched columns, in pruning the search-space of distillation column configurations for zeotropic multicomponent separation, to provide a small subset of attractive configurations with low minimum heat duties. The short-cut method, due to its simplifying assumptions, is computationally efficient, yet reliable in identifying the small subset of useful configurations for further detailed process evaluation. This two-tier approach allows expedient search of the configuration space containing hundreds to thousands of candidate configurations for a given application.

34. Davarnia, D., Richard, J.-P. P., & Tawarmalani, M. (2017). Simultaneous convexification of bilinear functions over polytopes with application to network interdiction. SIAM Journal on Optimization, 27(3), 1801–1833.

    Abstract

    We study the simultaneous convexification of graphs of bilinear functions $g^k(x;y) = y^\intercal A^k x$ over $x \in \Xi = \{x \in [0,1]^n \mid E{x} \geq f \}$ and $y \in \Delta_m = \{ y \in R_+^m \mid 1^\intercal y \leq 1 \}$. We propose a constructive procedure to obtain a linear description of the convex hull of the resulting set. This procedure can be applied to derive convex and concave envelopes of certain bilinear functions, to study unary expansions of integer variables in mixed integer bilinear sets, and to obtain convex hulls of sets with complementarity constraints. Exploiting the structure of $\Xi$, the procedure naturally yields stronger linearizations for bilinear terms in a variety of practical settings. In particular, we demonstrate the effectiveness of the approach by strengthening the traditional dual formulation of network interdiction problems and report encouraging preliminary numerical results.

35. Kannan, K., Rahman, M. S., & Tawarmalani, M. (2016). Economic and policy implications of restricted patch distribution. Management Science, 62(11), 3161–3182.

    Abstract

    In this paper, we study how restricting the availability of patches to legal users impacts the vendor’s profits, market share, software maintenance decisions, and welfare outcomes. Prior work on this topic assumes that the hacker’s effort is independent of the vendor’s decision to release the patch freely or not. Clearly, if the patch is not available to everyone, the hacker finds it easier to exploit the vulnerability in the product and, as a result, is likely to alter his effort. To understand the role of a strategic hacker, we build a game-theoretic model, where the hacker’s decision is endogenous. With this model, we find that the hacker’s effort may, on the one hand, decrease the utility that the vendor can extract from the consumers but, on the other hand, may help differentiate the legal version of the product from the pirated version. A vendor can strategically exploit the hacker’s behavior in its pricing and software maintenance decisions. The endogeneity of the hacker’s actions drives several of our findings that have interesting policy implications. For example, the vendor may increase the price and reduce market share to exploit the differentiation. In such a case, there may be more pirates in the restricted-patch case than when the patch is freely available, a result that runs counter to typical arguments provided for restricting patches.

36. Ramapriya, G. M., Tawarmalani, M., & Agrawal, R. (2016). Thermal coupling links to liquid-only transfer streams: An enumeration method for new FTC dividing wall columns. AIChE Journal, 62(4), 1200–1211.

    Abstract

    Novel dividing wall columns (DWCs) can be obtained by converting thermal couplings to liquid-only transfer streams. Here, we develop a simple four-step method to generate a complete set of DWCs containing n − 2 dividing walls, for a given n-component fully thermally coupled (FTC) distillation. Among the novel DWCs, some easy-to-operate DWCs possess the property that the vapor flow in every section of the DWC can be controlled during operation by means that are external to the column. We develop a simple method to enumerate all such easy-to-operate DWCs. We expect that the easy-to-operate DWCs can be operated close-to-optimality; leading to a successful industrial implementation of the n-component (n ≥ 3) FTC distillation in the form of a DWC. As an illustration, we show figures of all easy-to-operate DWCs with two dividing walls for the four-component FTC distillation.

37. Nallasivam, U., Shah, V. H., Shenvi, A. A., Huff, J., Tawarmalani, M., & Agrawal, R. (2016). Global optimization of multicomponent distillation configurations: 2. Enumeration based global minimization algorithm. AIChE Journal, 62(6), 2071–2086.

    Abstract

    We present a general Global Minimization Algorithm (GMA) to identify basic or thermally coupled distillation configurations that require the least vapor duty under minimum reflux conditions for separating any ideal or near-ideal multicomponent mixture into a desired number of product streams. In this algorithm, global optimality is guaranteed by modeling the system using Underwood equations and reformulating the resulting constraints to bilinear inequalities. The speed of convergence to the globally optimal solution is increased by using appropriate feasibility and optimality based variable-range reduction techniques and by developing valid inequalities. The GMA can be coupled with already developed techniques that enumerate basic and thermally coupled distillation configurations, to provide for the first time, a global optimization based rank-list of distillation configurations.

38. Bao, X., Khajavirad, A., Sahinidis, N. V., & Tawarmalani, M. (2015). Global optimization of nonconvex problems with multilinear intermediates. Mathematical Programming Computation, 7(1), 1–37.

    Abstract

    We consider global optimization of nonconvex problems containing multilinear functions. It is well known that the convex hull of a multilinear function over a box is polyhedral, and the facets of this polyhedron can be obtained by solving a linear optimization problem (LP). When used as cutting planes, these facets can significantly enhance the quality of conventional relaxations in general-purpose global solvers. However, in general, the size of this LP grows exponentially with the number of variables in the multilinear function. To cope with this growth, we propose a graph decomposition scheme that exploits the structure of a multilinear function to decompose it to lower-dimensional components, for which the aforementioned LP can be solved very efficiently by employing a customized simplex algorithm. We embed this cutting plane generation strategy at every node of the branch-and-reduce global solver BARON, and carry out an extensive computational study on quadratically constrained quadratic problems, multilinear problems, and polynomial optimization problems. Results show that the proposed multilinear cuts enable BARON to solve many more problems to global optimality and lead to an average 60% CPU time reduction.

39. Ramapriya, G. M., Shenvi, A. A., Tawarmalani, M., & Agrawal, R. (2015). A new framework for combining a condenser and reboiler in a configuration to consolidate distillation columns. Industrial & Engineering Chemistry Research, 54(42), 10449–10464.

    Abstract

    Heat and mass integration to consolidate distillation columns in a configuration is often characterized by elimination of a reboiler and condenser associated with the same components. Here, we study a new and more general approach to column consolidation, of which the conventional approach is a special case. In the new approach, the reboiler of a column is coupled with the condenser of another, through heat and mass integration in an additional section (HMA-section). The introduction of an HMA-section eliminates multiple connecting streams/valves, reduces the number of reboilers, condensers, and distillation columns by one each, and reduces the heat duty of the configuration. We exhaustively enumerate HMA-sections, and lay out a framework to identify all configurations with HMA-sections. Through examples, we show that both heat integration and mass integration resulting from introducing an HMA-section contribute to reduce the heat duty significantly.

40. Gençer, E., Mallapragada, D. S., Maréchal, F., Tawarmalani, M., & Agrawal, R. (2015). Round-the-clock power supply and a sustainable economy via synergistic integration of solar thermal power and hydrogen processes. Proceedings of the National Academy of Sciences, 112(52), 15821–15826.

    Abstract

    We introduce a paradigm—“hydricity”—that involves the coproduction of hydrogen and electricity from solar thermal energy and their judicious use to enable a sustainable economy. We identify and implement synergistic integrations while improving each of the two individual processes. When the proposed integrated process is operated in a standalone, solely power production mode, the resulting solar water power cycle can generate electricity with unprecedented efficiencies of 40–46%. Similarly, in standalone hydrogen mode, pressurized hydrogen is produced at efficiencies approaching ∼50%. In the coproduction mode, the coproduced hydrogen is stored for uninterrupted solar power production. When sunlight is unavailable, we envision that the stored hydrogen is used in a “turbine”-based hydrogen water power (H2WP) cycle with the calculated hydrogen-to-electricity efficiency of 65–70%, which is comparable to the fuel cell efficiencies. The H2WP cycle uses much of the same equipment as the solar water power cycle, reducing capital outlays. The overall sun-to-electricity efficiency of the hydricity process, averaged over a 24-h cycle, is shown to approach ∼35%, which is nearly the efficiency attained by using the best multijunction photovoltaic cells along with batteries. In comparison, our proposed process has the following advantages: (i) It stores energy thermochemically with a two to three fold higher density, (ii) coproduced hydrogen has alternate uses in transportation, chemical, petrochemical industries, and (iii) unlike batteries, the stored energy does not discharge over time and the storage medium does not degrade with repeated uses.

41. Chung, K., Richard, J.-P. P., & Tawarmalani, M. (2014). Lifted inequalities for 0-1 mixed-integer bilinear covering sets. Mathematical Programming, 145(1), 403–450.

    Abstract

    In this paper, we study 0-1 mixed-integer bilinear covering sets. We derive several families of facet-defining inequalities via sequence-independent lifting techniques. We then show that these sets have a polyhedral structure that is similar to that of a certain fixed-charge single-node flow set. As a result, we also obtain new facet-defining inequalities for the single-node flow set that generalize well-known lifted flow cover inequalities from the integer programming literature.

42. Ramapriya, G. M., Tawarmalani, M., & Agrawal, R. (2014). Modified basic distillation configurations with intermediate sections for energy savings. AIChE Journal, 60(3), 1091–1097.

    Abstract

    Basic distillation configurations have been well studied, comprising of energy efficient (n − 1)-column configurations that can be used to separate an n-component nonazeotropic feed mixture into its components. In this article, we present new (n − 1)-column configurations which differ from the conventional basic configurations due to the introduction of extra intermediate sections and the additional transfer-streams associated with submixtures of these sections. We demonstrate using four-component examples that these small differences lead to some interesting nonintuitive physical effects in the new configurations, resulting in large energy savings compared to the basic configurations. The proposed configurations offer more operable and energy efficient options for onsite implementation than the corresponding optimally operated basic configurations.

43. Mallapragada, D. S., Tawarmalani, M., & Agrawal, R. (2014). Synthesis of augmented biofuel processes using solar energy. AIChE Journal, 60(7), 2533–2545.

    Abstract

    A method for synthesizing augmented biofuel processes, which improve biomass carbon conversion to liquid fuel (eta-carbon) using supplemental solar energy as heat, H2, and electricity is presented. For a target eta-carbon, our method identifies augmented processes requiring the least solar energy input. A nonconvex mixed integer nonlinear programming model allowing for simultaneous mass, heat, and power integration, is built over a process superstructure and solved using global optimization tools. As a case study, biomass thermochemical conversion via gasification and Fischer–Tropsch synthesis or fast-hydropyrolysis and hydrodeoxygenation (HDO) is considered. The optimal process configurations can be categorized either as standalone (eta-carbon <= 54%), augmented using solar heat (54% <= eta-carbon <= 74%), or augmented using solar heat and H2 (74 <= eta-carbon <= 95%). Importantly, the process H2 consumption is found to be close to the derived theoretical minimum values. To accommodate for the intermittency of solar heat/H2, we suggest processes that can operate at low and high eta-carbon.

44. Ramapriya, G. M., Tawarmalani, M., & Agrawal, R. (2014). Thermal coupling links to liquid-only transfer streams: A path for new dividing wall columns. AIChE Journal, 60(8), 2949–2961.

    Abstract

    We propose new dividing wall columns (DWCs) that are equivalent to the fully thermally coupled (FTC) configurations. While our method can draw such configurations for any given n-component mixture (n ≥ 3), we discuss in detail the DWCs for ternary and quaternary feed mixtures. A special feature of all the new DWCs is that during operation, they allow independent control of the vapor flow rate in each partitioned zone of the DWC by means that are external to the column. Because of this feature, we believe that the new arrangements presented in this work will enable the FTC configuration to be successfully implemented and optimally operated as a DWC in an industrial setting for any number of components. Also, interesting column arrangements result when a new DWC drawn for an n-component mixture is adapted for the distillation of a mixture containing more than n components.

45. Tawarmalani, M., Richard, J.-P. P., & Xiong, C. (2013). Explicit convex and concave envelopes through polyhedral subdivisions. Mathematical Programming, 138(1), 531–577.

    Abstract

    In this paper, we derive explicit characterizations of convex and concave envelopes of several nonlinear functions over various subsets of a hyper-rectangle. These envelopes are obtained by identifying polyhedral subdivisions of the hyper-rectangle over which the envelopes can be constructed easily. In particular, we use these techniques to derive, in closed-form, the concave envelopes of concave-extendable supermodular functions and the convex envelopes of disjunctive convex functions.

46. Nallasivam, U., Shah, V. H., Shenvi, A. A., Tawarmalani, M., & Agrawal, R. (2013). Global optimization of multicomponent distillation configurations: 1. Need for a reliable global optimization algorithm. AIChE Journal, 59(3), 971–981.

    Abstract

    Nonazeotropic multicomponent mixtures are often separated into products by distillation configurations containing multiple distillation columns. One method of calculating the minimum vapor duty of a configuration is to sequentially calculate the minimum vapor duty of each mixture as it is split into two streams within a given column starting from the feed column. The other method simultaneously manipulates all the splits to yield the overall minimum vapor duty of the entire configuration. Of these two methods, the sequential minimization is attractive as it can be analytically solved. However, through extensive computations, we find that the sequential minimization method is not a valid substitute for the simultaneous minimization method. As the number of components in the feed increases, the fraction of the basic configurations for which sequential method yields a reasonable estimate decreases rapidly, thereby emphasizing the need for a more robust and reliable global optimization algorithm.

47. Bao, X., Sahinidis, N. V., & Tawarmalani, M. (2011). Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons. Mathematical Programming, 129, 129–157.

    Abstract

    At the intersection of nonlinear and combinatorial optimization, quadratic programming has attracted significant interest over the past several decades. A variety of relaxations for quadratically constrained quadratic programming (QCQP) can be formulated as semidefinite programs (SDPs). The primary purpose of this paper is to present a systematic comparison of SDP relaxations for QCQP. Using theoretical analysis, it is shown that the recently developed doubly nonnegative relaxation is equivalent to the Shor relaxation, when the latter is enhanced with a partial first-order relaxation-linearization technique. These two relaxations are shown to theoretically dominate six other SDP relaxations. A computational comparison reveals that the two dominant relaxations require three orders of magnitude more computational time than the weaker relaxations, while providing relaxation gaps averaging 3% as opposed to gaps of up to 19% for weaker relaxations, on 700 randomly generated problems with up to 60 variables. An SDP relaxation derived from Lagrangian relaxation, after the addition of redundant nonlinear constraints to the primal, achieves gaps averaging 13% in a few CPU seconds.

48. Tawarmalani, M., & Li, Y. (2011). Multi-period maintenance scheduling of tree networks with minimum flow disruption. Naval Research Logistics, 58(5), 507–530.

    Abstract

    We introduce a multi-period tree network maintenance scheduling model and investigate the effect of maintenance capacity restrictions on traffic/information flow interruptions. Network maintenance refers to activities that are performed to keep a network operational. For linear networks with uniform flow between every pair of nodes, we devise a polynomial-time combinatorial algorithm that minimizes flow disruption. The spiral structure of the optimal maintenance schedule sheds insights into general network maintenance scheduling. The maintenance problem on linear networks with a general flow structure is strongly NP-hard. We formulate this problem as a linear integer program, derive strong valid inequalities, and conduct a polyhedral study of the formulation. Polyhedral analysis shows that the relaxation of our linear network formulation is tight when capacities and flows are uniform. The linear network formulation is then extended to an integer program for solving the tree network maintenance scheduling problem. Preliminary computations indicate that the strengthened formulations can solve reasonably sized problems on tree networks and that the intuitions gained from the uniform flow case continue to hold in general settings. Finally, we extend the approach to directed networks and to maintenance of network nodes.

49. Richard, J.-P. P., & Tawarmalani, M. (2010). Lifting inequalities: A framework for generating strong cuts for nonlinear programs. Mathematical Programming, 121, 61–104.

    Abstract

    In this paper, we introduce the first generic lifting techniques for deriving strong globally valid cuts for nonlinear programs. The theory is geometric and provides insights into lifting-based cut generation procedures, yielding short proofs of earlier results in mixed-integer programming. Using convex extensions, we obtain conditions that allow for sequence-independent lifting in nonlinear settings, paving a way for efficient cut-generation procedures for nonlinear programs. This sequence-independent lifting framework also subsumes the superadditive lifting theory that has been used to generate many general-purpose, strong cuts for integer programs. We specialize our lifting results to derive facet-defining inequalities for mixed-integer bilinear knapsack sets. Finally, we demonstrate the strength of nonlinear lifting by showing that these inequalities cannot be obtained using a single round of traditional integer programming cut-generation techniques applied on a tight reformulation of the problem.

50. Tawarmalani, M., Richard, J.-P. P., & Chung, K. (2010). Strong valid inequalities for orthogonal disjunctions and bilinear covering sets. Mathematical Programming, 124(1), 481–512.

    Abstract

    In this paper, we derive a closed-form characterization of the convex hull of a generic nonlinear set, when this convex hull is completely determined by orthogonal restrictions of the original set. Although the tools used in this construction include disjunctive programming and convex extensions, our characterization does not introduce additional variables. We develop and apply a toolbox of results to check the technical assumptions under which this convexification tool can be employed. We demonstrate its applicability in integer programming by providing an alternate derivation of the split cut for mixed-integer polyhedral sets and finding the convex hull of certain mixed/pure-integer bilinear sets. We then extend the utility of the convexification tool to relaxing nonconvex inequalities, which are not naturally disjunctive, by providing sufficient conditions for establishing the convex extension property over the non-negative orthant. We illustrate the utility of this result by deriving the convex hull of a continuous bilinear covering set over the non-negative orthant. Although we illustrate our results primarily on bilinear covering sets, they also apply to more general polynomial covering sets for which they yield new tight relaxations.

51. Bao, X., Sahinidis, N. V., & Tawarmalani, M. (2009). Multiterm polyhedral relaxations for nonconvex, quadratically constrained quadratic programs. Optimization Methods & Software, 24(4-5), 485–504.

    Abstract

    This article addresses the generation of strong polyhedral relaxations for nonconvex, quadratically constrained quadratic programs (QCQPs). Using the convex envelope of multilinear functions as our starting point, we develop a polyhedral relaxation for QCQP, along with a cutting plane algorithm for its implementation. Our relaxations are multiterm, i.e. they are derived from the convex envelope of the sum of multiple bilinear terms of quadratic constraints, thereby providing tighter bounds than the standard termwise relaxation of the bilinear functions. Computational results demonstrate the usefulness of the proposed cutting planes.

52. Tawarmalani, M., Kannan, K., & De, P. (2009). Allocating objects in a network of caches: Centralized and decentralized analyses. Management Science, 55(1), 132–147.

    Abstract

    We analyze the allocation of objects in a network of caches that collaborate to service requests from customers. A thorough analysis of this problem in centralized and decentralized setups, both of which occur in practice, is essential for understanding the benefits of collaboration. A key insight offered by this paper is that an efficient implementation of cooperative cache management is possible because, in the centralized scenario, the object allocation resulting in the best social welfare can be found easily as a solution to a transportation problem. For the decentralized scenario involving selfish caches, it is shown that pure equilibria exist and that the cache network always reaches a pure equilibrium in a finite number of steps, starting from any point in the strategy space. An auction mechanism is developed to derive prices that motivate the caches to hold objects in a manner such that the optimal social welfare is attained. In the special case of symmetric caches, simple algorithms are devised to find the optimal social welfare allocation, the best pure equilibrium, and the prices for sharing objects. The results obtained in this paper should be valuable in developing and evaluating cache-management policies. Resource-sharing problems with a similar cost structure exist in a variety of other domains, and the insights gained here are expected to extend to those scenarios as well.

53. Tawarmalani, M., & Sahinidis, N. V. (2005). A polyhedral branch-and-cut approach to global optimization. Mathematical Programming, 103(2), 225–249.

    Abstract

    A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software. In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedral branch-and-cut approach. Our algorithm exploits convexity, either identified automatically or supplied through a suitable modeling language construct, in order to generate polyhedral cutting planes and relaxations for multivariate nonconvex problems. We prove that, if the convexity of a univariate or multivariate function is apparent by decomposing it into convex subexpressions, our relaxation constructor automatically exploits this convexity in a manner that is much superior to developing polyhedral outer approximators for the original function. The convexity of functional expressions that are composed to form nonconvex expressions is also automatically exploited. Root-node relaxations are computed for 87 problems from globallib and minlplib, and detailed computational results are presented for globally solving 26 of these problems with BARON 7.2, which implements the proposed techniques. The use of cutting planes for these problems reduces root-node relaxation gaps by up to 100% and expedites the solution process, often by several orders of magnitude.

54. Sahinidis, N. V., & Tawarmalani, M. (2005). Accelerating branch-and-bound through a modeling language construct for relaxation-specific constraints. Journal of Global Optimization, 32, 259–280.

    Abstract

    In the tradition of modeling languages for optimization, a single model is passed to a solver for solution. In this paper, we extend BARON’s modeling language in order to facilitate the communication of problem-specific relaxation information from the modeler to the branch-and-bound solver. This effectively results into two models being passed from the modeling language to the solver. Three important application areas are identified and computational experiments are presented. In all cases, nonlinear constraints are provided only to the relaxation constructor in order to strengthen the lower bounding step of the algorithm without complicating the local search process. In the first application area, nonlinear constraints from the reformulation–linearization technique (RLT) are added to strengthen a problem formulation. This approach is illustrated for the pooling problem and computational results show that it results in a scheme that makes global optimization nearly as fast as local optimization for pooling problems from the literature. In the second application area, we communicate with the relaxation constructor the first-order optimality conditions for unconstrained global optimization problems. Computational experiments with polynomial programs demonstrate that this approach leads to a significant reduction of the size of the branch-and-bound search tree. In the third application, problem-specific nonlinear optimality conditions for the satisfiability problem are used to strengthen the lower bounding step and are found to significantly expedite the branch-and-bound algorithm when applied to a nonlinear formulation of this problem.

55. Tawarmalani, M., & Sahinidis, N. V. (2004). Global optimization of mixed-integer nonlinear programs: A theoretical and computational study. Mathematical Programming, 99(3), 563–591.

    Abstract

    This work addresses the development of an efficient solution strategy for obtaining global optima of continuous, integer, and mixed-integer nonlinear programs. Towards this end, we develop novel relaxation schemes, range reduction tests, and branching strategies which we incorporate into the prototypical branch-and-bound algorithm. In the theoretical/algorithmic part of the paper, we begin by developing novel strategies for constructing linear relaxations of mixed-integer nonlinear programs and prove that these relaxations enjoy quadratic convergence properties. We then use Lagrangian/linear programming duality to develop a unifying theory of domain reduction strategies as a consequence of which we derive many range reduction strategies currently used in nonlinear programming and integer linear programming. This theory leads to new range reduction schemes, including a learning heuristic that improves initial branching decisions by relaying data across siblings in a branch-and-bound tree. Finally, we incorporate these relaxation and reduction strategies in a branch-and-bound algorithm that incorporates branching strategies that guarantee finiteness for certain classes of continuous global optimization problems. In the computational part of the paper, we describe our implementation discussing, wherever appropriate, the use of suitable data structures and associated algorithms. We present computational experience with benchmark separable concave quadratic programs, fractional 0–1 programs, and mixed-integer nonlinear programs from applications in synthesis of chemical processes, engineering design, just-in-time manufacturing, and molecular design.

56. Ahmed, S., Tawarmalani, M., & Sahinidis, N. V. (2004). A finite branch-and-bound algorithm for two-stage stochastic integer programs. Mathematical Programming, 100(2), 355–377.

    Abstract

    This paper addresses a general class of two-stage stochastic programs with integer recourse and discrete distributions. We exploit the structure of the value function of the second-stage integer problem to develop a novel global optimization algorithm. The proposed scheme departs from those in the current literature in that it avoids explicit enumeration of the search space while guaranteeing finite termination. Computational experiments on standard test problems indicate superior performance of the proposed algorithm in comparison to those in the existing literature.

57. Sahinidis, N. V., Tawarmalani, M., & Yu, M. (2003). Design of alternative refrigerants via global optimization. AIChE Journal, 49(7), 1761–1775.

    Abstract

    Accurate and fast enumeration of large, combinatorial search spaces presents a central conceptual challenge in molecular design. To address this challenge, an algorithm is developed that guarantees globally optimal solutions to a mixed-integer nonlinear programming formulation for molecular design. The formulation includes novel structural feasibility constraints, while the algorithm provides all feasible solutions to this formulation through the implicit enumeration of a single branch-and-reduce tree. This algorithm is used to provide the complete solution set to a refrigerant design problem posed elsewhere. In addition to rediscovering CFCs, the proposed methodology identifies a number of novel potential replacements of Freon 12.

58. Tawarmalani, M., & Sahinidis, N. V. (2002). Convex extensions and envelopes of lower semi-continuous functions. Mathematical Programming, 93(2), 247–263.

    Abstract

    We define a convex extension of a lower semi-continuous function to be a convex function that is identical to the given function over a pre-specified subset of its domain. Convex extensions are not necessarily constructible or unique. We identify conditions under which a convex extension can be constructed. When multiple convex extensions exist, we characterize the tightest convex extension in a well-defined sense. Using the notion of a generating set, we establish conditions under which the tightest convex extension is the convex envelope. Then, we employ convex extensions to develop a constructive technique for deriving convex envelopes of nonlinear functions. Finally, using the theory of convex extensions we characterize the precise gaps exhibited by various underestimators of x/y over a rectangle and prove that the extensions theory provides convex relaxations that are much tighter than the relaxation provided by the classical outer-linearization of bilinear terms.

59. Tawarmalani, M., Ahmed, S., & Sahinidis, N. V. (2002). Global optimization of 0-1 hyperbolic programs. Journal of Global Optimization, 24(4), 385–416.

    Abstract

    We develop eight different mixed-integer convex programming reformulations of 0-1 hyperbolic programs. We obtain analytical results on the relative tightness of these formulations and propose a branch and bound algorithm for 0-1 hyperbolic programs. The main feature of the algorithm is that it reformulates the problem at every node of the search tree. We demonstrate that this algorithm has a superior convergence behavior than directly solving the relaxation derived at the root node. The algorithm is used to solve a discrete p-choice facility location problem for locating ten restaurants in the city of Edmonton.

60. Tawarmalani, M., & Sahinidis, N. V. (2001). Semidefinite relaxations of fractional programs via novel convexification techniques. Journal of Global Optimization, 20, 133–154.

    Abstract

    In a recent work, we introduced the concept of convex extensions for lower semi-continuous functions and studied their properties. In this work, we present new techniques for constructing convex and concave envelopes of nonlinear functions using the theory of convex extensions. In particular, we develop the convex envelope and concave envelope of z=x/y over a hypercube. We show that the convex envelope is strictly tighter than previously known convex underestimators of x/y. We then propose a new relaxation technique for fractional programs which includes the derived envelopes. The resulting relaxation is shown to be a semidefinite program. Finally, we derive the convex envelope for a class of functions of the type f(x,y) over a hypercube under the assumption that f is concave in x and convex in y.

61. Tawarmalani, M., Ahmed, S., & Sahinidis, N. V. (2001). Product disaggregation in global optimization and relaxations of rational programs. Optimization and Engineering, 3, 281–303.

    Abstract

    We consider the product of a single continuous variable and the sum of a number of continuous variables. We show that “product disaggregation” (distributing the product over the sum) leads to tighter linear programming relaxations, much like variable disaggregation does in mixed-integer linear programming. We also derive closed-form expressions characterizing the exact region over which these relaxations improve when the bounds of participating variables are reduced. In a concrete application of product disaggregation, we develop and analyze linear programming relaxations of rational programs. In the process of doing so, we prove that the task of bounding general linear fractional functions of 0–1 variables is NP-hard. Finally, we present computational experience to demonstrate that product disaggregation is a useful reformulation technique for global optimization problems.

62. Sahinidis, N. V., & Tawarmalani, M. (2000). Applications of global optimization to process and molecular design. Computers & Chemical Engineering, 24(9-10), 2157–2169.

    Abstract

    The purpose of this paper is to review some recent results that demonstrate the importance of identifying global optima of MINLP formulations. We present two global optimization “success stories” based on the application of global optimization techniques to two design problems. The first application deals with the design of just-in-time flowshops. On a collection of nine problem instances with only four degrees of freedom, global optimization provides solutions that average 17% cost savings compared to designs identified earlier in the literature using local search techniques. The second application deals with design at the molecular level and involves a considerably larger design space for identifying a replacement of Freon. The problem is difficult and has been approached by numerous research groups in the past. Global optimization identifies many novel molecular structures.

63. Adhya, N., Tawarmalani, M., & Sahinidis, N. V. (1999). A lagrangian approach to the pooling problem. Industrial & Engineering Chemistry Research, 38(5), 1956–1972.

    Abstract

    Pooling and blending problems occur frequently in the petrochemical industry where crude oils, procured from various sources, are mixed together to manufacture several end-products. Finding optimal solutions to pooling problems requires the solution of nonlinear optimization problems with multiple local minima. We introduce a new Lagrangian relaxation approach for developing lower bounds for the pooling problem. We prove that, for the multiple-quality case, the Lagrangian approach provides tighter lower bounds than the standard linear-programming relaxations used in global optimization algorithms. We present computational results on a set of 13 problems which includes four particularly difficult problems we constructed.