Search

Abstract. We present a new heuristic algorithm to approximately generate the nondominated frontier of bi-objective pure integer linear programs. The proposed algorithm employs a customized version of several existing algorithms [...]

We present a new criterion space search algorithm, the balanced box method, for finding all nondominated points of a biobjective integer program. The method extends the box algorithm, is easy [...]

We present the first criterion space search algorithm, the triangle splitting method, for finding all nondominated points of a biobjective mixed integer program. The algorithm is relatively easy to implement [...]

Isolation valves are critical for the reliable functioning of water distribution networks (WDNs). However, it is challenging for utilities to prioritize valve rehabilitation and replacement given it is often unclear if certain valves are operable in a given WDN. This study uses the Gomory–Hu tree of the segment-valve representation (or dual representation) of WDNs to obtain the logical implications of inoperable valves (i.e., which segments should be isolated and merged unnecessarily due to valve inoperability). Multi-objective optimization is then used to identify the critical valves based on selected attributes (e.g., social vulnerability, flow volume) of segments that would be unnecessarily isolated as a result. This study developed three multi-objective formulations: first, deterministic; second, accounting for uncertainty; and third, accounting for both uncertainty and the likelihood of failure of pipes within segments. Identified critical valves are compared between the three developed formulations and a method considering only a single objective. Results demonstrated that multi-objective optimization provided additional information which can be used to discern valve importance for utilities in comparison with using a single objective. Further, though there was overlap between the results from the three formulations, the third formulation provided the most insight without overwhelming decision-makers with a large number of identified valves. [ABSTRACT FROM AUTHOR]

This study introduces a branch-and-bound algorithm to solve mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). This class of optimization problems arises in many applications, such as finding a Nash bargaining solution (Nash social welfare optimization), capacity allocation markets, reliability optimization, etc. The proposed algorithm applies multiobjective optimization principles to solve MIBL-MMPs exploiting a special characteristic in these problems. That is, taking each multiplicative term in the objective function as a dummy objective function, the projection of an optimal solution of MIBL-MMPs is a nondominated point in the space of dummy objectives. Moreover, several enhancements are applied and adjusted to tighten the bounds and improve the performance of the algorithm. The performance of the algorithm is investigated by 400 randomly generated sample instances of MIBL-MMPs. The obtained result is compared against the outputs of the mixed-integer second order cone programming (SOCP) solver in CPLEX and a state-of-the-art algorithm in the literature for this problem. Our analysis on this comparison shows that the proposed algorithm outperforms the fastest existing method, that is, the SOCP solver, by a factor of 6.54 on average. Summary of Contribution: The scope of this paper is defined over a class of mixed-integer programs, the so-called mixed-integer bilinear maximum multiplicative programs (MIBL-MMPs). The importance of MIBL-MMPs is highlighted by the fact that they are encountered in applications, such as Nash bargaining, capacity allocation markets, reliability optimization, etc. The mission of the paper is to introduce a novel and effective criterion space branch-and-cut algorithm to solve MIBL-MMPs by solving a finite number of single-objective mixed-integer linear programs. Starting with an initial set of primal and dual bounds, our proposed approach explores the efficient set of the multiobjective problem counterpart of the MIBL-MMP through a criterion space–based branch-and-cut paradigm and iteratively improves the bounds using a branch-and-bound scheme. The bounds are obtained using novel operations developed based on Chebyshev distance and piecewise McCormick envelopes. An extensive computational study demonstrates the efficacy of the proposed algorithm. [ABSTRACT FROM AUTHOR]

We study a class of mixed integer optimization problems with linear constraints and a multilinear objective function, the so‐called mixed integer linear maximum multiplicative programs (MIL‐MMPs). Such a problem can be transformed into a second‐order cone program (SOCP) and can be solved effectively by a commercial solver such as CPLEX. However, MIL‐MMPs can also be viewed as special cases of the problem of optimization over the set of efficient solutions in multiobjective optimization. Using this observation, we develop a criterion space search algorithm for solving any MIL‐MMP. An extensive computational study on around 2000 instances illustrates that the proposed algorithm significantly outperforms not only the CPLEX mixed integer SOCP solver but also a state‐of‐the‐art algorithm that is capable of solving special cases of MIL‐MMPs. Moreover, the computational study illustrates that even if we linearize the objective function and solve the linearized problem by CPLEX, the proposed algorithm still performs significantly better. [ABSTRACT FROM AUTHOR]

Energy storage (ES) is acknowledged to play an important role in modern energy technologies due to its potential to reduce operational costs, enhance the resilience, and level energy load for energy systems. Efficient ES management can achieve cost savings, also known as energy arbitrage, by charging at off‐peak prices and discharging at peak prices. This arbitrage can be further boosted by allowing the ES to be shared by multiple users/buildings. However, since energy arbitrage relies on the variation of energy prices, it is hard to achieve this arbitrage if the prices are uncertain. To address this challenge, we present a robust optimization approach to fairly and efficiently operate an ES shared between two users under price uncertainty. This sharing strategy is formulated as a biobjective mixed integer bilinear programming model. To facilitate solution efficiency, we propose a binary formulation for piecewise McCormick relaxations to approximate the bilinear model by a tractable linear model. A computational study demonstrates the effectiveness of our robust sharing strategy for managing ES sharing under price uncertainty. Also, it shows that the proposed binary formulation for piecewise McCormick relaxations reduces the runtime by around 80% compared to the traditional unary formulation. [ABSTRACT FROM AUTHOR]

We explain some key challenges when dealing with a single- or multi-objective optimization problem in practice. To overcome these challenges, we present a mathematical program that optimizes the Nash social welfare function. We refer to this mathematical program as the Nash social welfare program (NSWP). An interesting property of the NSWP is that it can be constructed for any single- or multi-objective optimization problem. We show that solving the NSWP could result in more desirable solutions in practice than its single- or multi-objective counterpart. We also discuss several promising approaches that could be employed to solve the NSWP in practice. [ABSTRACT FROM AUTHOR]

Conservation planning involves identifying and selecting actions to best achieve objectives for managing natural, social and cultural resources. Conservation problems are often high dimensional when specified as combinatorial or portfolio problems and when multiple competing objectives are considered at varying spatial and temporal scales. Although analytical techniques such as modern portfolio theory (MPT) have been developed to address these complex problems, open source computational platforms for executing these approaches are not readily available. We present a user‐friendly R‐package called SiteOpt for optimization of binary decisions while explicitly considering environmental or economic uncertainty and the risk tolerance of decision makers. We illustrate the package with spatially‐explicit site selection problems (i.e. spatial conservation planning), including an option for divestment (i.e. selling assets), when accounting for future uncertainties in designing conservation areas. The tool is applicable to both spatial and non‐spatial problems, such as budget allocation or species selection. Constraints for spatial design and spatial dependencies (e.g. connectivity among sites) can also be specified in SiteOpt. Users can optimize site selection based on two competing objectives by solving for the Nash bargaining solution. Importantly, by quantifying uncertainty and asset spatial correlation, a measure of risk can be included as one such objective to be traded off against portfolio benefits. Thus, SiteOpt can be used to explicitly manage risk in portfolio‐based spatial optimization. This tool facilitates decisions in a variety of problem settings, including reserve selection, invasive species management, allocation of law enforcement activities for conservation, budget allocation and asset selection under uncertainty and risk. [ABSTRACT FROM AUTHOR]

Energy storage (ES) plays a significant role in modern smart grids and energy systems. To facilitate and improve the utilization of ES, appropriate system design and operational strategies should be adopted. The traditional approach of utilizing ES is the individual distributed framework in which an individual ES is installed for each user separately. Due to the cost inefficiency of the individual framework and the difficulty of applying this framework to the grid-scale ES, many studies have suggested the sharing strategy for the utilization of ES to further exploit the potentials of ES. This paper provides a comprehensive review of the papers on shared ES that are published in the last decade. In this review, we characterize the design of the shared ES systems and explain their potential and challenges. We also provide a detailed comparison of the literature on shared ES based on multiple criteria. Finally, we discuss some promising directions for the future study on shared ES. [ABSTRACT FROM AUTHOR]

This study designs a new market for fractional ownership of autonomous vehicles (AVs), in which an AV is co‐leased by a group of individuals. We present a practical iterative auction based on the combinatorial clock auction to match the interested customers together and determine their payments. In designing such an auction, we consider continuous‐time items (time slots) that are defined by bidders and naturally exploit driverless mobility of AVs to form co‐leasing groups. To relieve the computational burdens of both bidders and the auctioneer, we devise user agents who generate packages and bid on behalf of bidders. Through numerical experiments using the California 2010–2012 travel survey, we test the performance of the auction design. We also compare various bidding strategies and study the effect of activity rules on the bidders' payoffs. We find that the designed activity rules successfully remove the strategic behavior of bidders. We also find that core‐selecting payment rule brings the largest revenue to the auctioneer in most cases. [ABSTRACT FROM AUTHOR]

The introduction of autonomous vehicles (AVs) to consumer markets will expedite the trend of car sharing and enable co‐owning or co‐leasing a car. In this paper, we consider a combinatorial auction market for fractional ownership of AVs, which is unique in two aspects. First, items are neither predefined nor discrete; rather, items are continuous time slots defined by bidders. Second, the spatial information of bidders should be incorporated within the winner determination problem (WDP) so that sharing a vehicle is indeed a viable plan. The consideration of spatial information increases the computational complexity significantly. We formulate the WDP, which plays a critical role in various auction designs and pricing schemes, for both discrete‐ and continuous‐time settings. In terms of social welfare maximization, we show that the continuous‐time model is superior to the discrete‐time model. We provide a conflict‐based reformulation of the continuous‐time model, for which we develop an effective solution approach based on a heuristic and maximal clique based reformulations. Using samples of the 2010–2012 California Household Travel Survey, we verify that the proposed solution methods provide effective computational tools for the combinatorial auction with bidder‐defined items. [ABSTRACT FROM AUTHOR]

We study the fluency map optimization problem in Intensity Modulated Radiation Therapy from a cooperative game theory point of view. We consider the cancerous and healthy organs in a patient's body as players of a game, where cancerous organs seek to eliminate the cancerous cells and healthy organs seek to receive no harm. The goal is to balance the trade-offs between the utility of players by forming a grand coalition between them. We do so by proposing a methodology that solves a few convex optimization problems in order to transform the fluency map optimization problem into a bargaining game. To solve the bargaining game, we employ the concept of Nash Social Welfare (NSW) optimization due to the desirable efficiency and fairness properties of its outcomes. The proposed NSW optimization is convex and can be solved by powerful commercial solvers such as CPLEX. An additional advantage of the proposed approach is that it has a new control lever for the fluency map optimization, the so-called negotiation powers, which enables practitioners to put more emphasis on an organ by changing its negotiation power. To show the efficacy of our proposed methodology, we apply it to the TG-119 case and a liver case. We compare our proposed approach with a state-of-the-art approach through creating Dose Volume Histograms. [ABSTRACT FROM AUTHOR]

We present OOESAlgorithm.jl, a package for optimizing a linear function over the efficient set of biobjective mixed integer linear programs. The proposed package extends our recent study (see Sierra‐Altamiranda and Charkhgard [INFORMS Journal on Computing, https://doi.org/10.1287/ijoc.2018.0851]) by adding two main features: (a) in addition to CPLEX, the package allows employing any single‐objective solver supported by MathProgBase.jl, for example, GLPK, CPLEX, and SCIP; (b) the package supports execution on multiple processors and is compatible with the JuMP modeling language. An extensive computational study shows the efficacy of the package and its features. [ABSTRACT FROM AUTHOR]

We present the first (criterion space search) algorithm for optimizing a linear function over the set of efficient solutions of biobjective mixed integer linear programs. The proposed algorithm is developed based on the triangle splitting method [Boland N, Charkhgard H, Savelsbergh M (2015) A criterion space search algorithm for biobjective mixed integer programming: The triangle splitting method. INFORMS J. Comput. 27(4):597–618.], which can find a full representation of the nondominated frontier of any biobjective mixed integer linear program. The proposed algorithm is easy to implement and converges quickly to an optimal solution. An extensive computational study shows the efficacy of the algorithm. We numerically show that the proposed algorithm can be used to quickly generate a provably high-quality approximate solution because it maintains a lower and an upper bound on the optimal value of the linear function at any point in time. [ABSTRACT FROM AUTHOR]

We study the problem of choosing the best subset of $p$ features in linear regression, given $n$ observations. This problem naturally contains two objective functions including minimizing the amount of bias and minimizing the number of predictors. The existing approaches transform the problem into a single-objective optimization problem. We explain the main weaknesses of existing approaches and, to overcome their drawbacks, we propose a bi-objective mixed integer linear programming approach. A computational study shows the efficacy of the proposed approach. [ABSTRACT FROM AUTHOR]

In conservation planning, the data related to size, growth and diffusion of populations is sparse, hard to collect and unreliable at best. If and when the data is readily available, it is not of sufficient quantity to construct a probability distribution. In such a scenario, applying deterministic or stochastic approaches to the problems in conservation planning either ignores the uncertainty completely or assumes a distribution that does not accurately describe the nature of uncertainty. To overcome these drawbacks, we propose a robust optimization approach to problems in conservation planning that considers the uncertainty in data without making any assumption about its probability distribution. We explore two of the basic formulations in conservation planning related to reserve selection and invasive species control to show the value of the proposed robust optimization. Several novel techniques are developed to compare the results produced by the proposed robust optimization approach and the existing deterministic approach. For the case when the robust optimization approach fails to find a feasible solution, a novel bi-objective optimization technique is developed to handle infeasibility by modifying the level of uncertainty. Some numerical experiments are conducted to demonstrate the efficacy of our proposed approach in finding more applicable conservation planning strategies. [ABSTRACT FROM AUTHOR]