Search

We introduce the problem of selecting patient-donor pairs in a kidney exchange program to undergo a crossmatch test, and we model this selection problem as a two-stage stochastic integer programming problem. The optimal solutions of this new formulation yield a larger expected number of realized transplants than previous approaches based on internal recourse or subset recourse. We settle the computational complexity of the selection problem by showing that it remains NP-hard even for maximum cycle length equal to two. Furthermore, we investigate to what extent different algorithmic approaches, including one based on Benders decomposition, are able to solve instances of the model. We empirically investigate the computational efficiency of this approach by solving randomly generated instances and study the corresponding running times as a function of maximum cycle length, and of the presence of nondirected donors. Summary of Contribution: This paper deals with an important and very complex issue linked to the optimization of transplant matchings in kidney exchange programs, namely, the inherent uncertainty in the assessment of compatibility between donors and recipients of transplants. Although this issue has previously received some attention in the optimization literature, most attempts to date have focused on applying recourse to solutions selected within restricted spaces. The present paper explicitly formulates the maximization of the expected number of transplants as a two-stage stochastic integer programming problem. The formulation turns out to be computationally difficulty, both from a theoretical and from a numerical perspective. Different algorithmic approaches are proposed and tested experimentally for its solution. The quality of the kidney exchanges produced by these algorithms compares favorably with that of earlier models.

In this paper we consider uncertain second-order cone (SOC) and semidefinite programming (SDP) constraints with polyhedral uncertainty, which are in general computationally intractable. We propose to reformulate an uncertain SOC or SDP constraint as a set of adjustable robust linear optimization constraints withan ellipsoidal or semidefinite representable uncertainty set, respectively. The resulting adjustable problem can then (approximately) be solved by using adjustable robust linear optimization techniques. For example, we show that if linear decision rules are used, then the final robust counterpart consists of SOC or SDP constraints, respectively, which have the same computational complexity as the nominal version of the original constraints. We propose an efficient method to obtain good lower bounds. Moreover, we extend our approach to other classes of robust optimization problems, such as nonlinear problems that contain waitand-see variables or linear problems that contain bilinear uncertainty. Numerically, we apply our approach to reformulate the problem on finding the minimum volume circumscribing ellipsoid of a polytope, and solvethe resulting reformulation with linear and quadratic decision rules as well as Fourier-Motzkin elimination. We demonstrate the effectiveness and efficiency of the proposed approach by comparing it with the state-ofthe-art copositive approach. Moreover, we apply the proposed approach to a robust regression problem and a robust sensor network problem, and use linear decision rules to solve the resulting adjustable robust linear optimization problems, which solves the problem to (near) optimality.

In this paper, we focus on a subclass of quadratic optimization problems, that is, disjoint bilinear optimization problems. We first show that disjoint bilinear optimization problems can be cast as two-stage robust linear optimization problems with fixed-recourse and right-hand-side uncertainty, which enables us to apply robust optimization techniques to solve the resulting problems. To this end, a solution scheme based on a blending of three popular robust optimization techniques is proposed. For disjoint bilinear optimization problems with a polyhedral feasible region and a general convex feasible region, we show that, under mild regularity conditions, the convex relaxations of the original bilinear formulation and its two-stage robust reformulation obtained from a reformulation-linearization-based technique and linear decision rules, respectively, are equivalent. For generic bilinear optimization problems, the convex relaxations from the reformulation-linearization-based technique are generally tighter than the one from linear decision rules. Numerical experiments on bimatrix games, synthetic disjoint bilinear problem instances, and convex maximization problems demonstrate the efficiency and effectiveness of the proposed solution scheme.

In this work we consider a seller who sells an item via second-price auctions with a reserve price. By controlling the reserve price, the seller can influence the revenue from the auction, and in this paper, we propose a method for learning optimal reserve prices. We study a limited information setting where the probability distribution of the bids from bidders is unknown and the values of the bids are not revealed to the seller. Furthermore, we do not assume that the seller has access to a historical data set with bids. Our main contribution is a method that incorporates knowledge about the rules of second-price auctions into a multiarmed bandit framework for optimizing reserve prices in our limited information setting. The proposed method can be applied in both stationary and nonstationary environments. Experiments show that the proposed method outperforms state-of-the-art bandit algorithms. In stationary environments, our method outperforms these algorithms when the horizon is short and performs as good as they do for longer horizons. Our method is especially useful if there is a high number of potential reserve prices. In addition, our method adapts quickly to changing environments and outperforms state-of-the-art bandit algorithms designed for nonstationary environments. Summary of Contribution: A key challenge in online advertising is the pricing of advertisements in online auctions. The scope of our study is second-price auctions with a focus on the reserve price optimization problem from a seller’s point of view. This problem is motivated by the real-life practice of small and medium-sized web publishers. However, the proposed solution approach is applicable to any seller who sells an item via second-price auctions and wants to optimize its reserve price during these auctions. Our solution approach is based on techniques from machine learning and operations research, and it would be beneficial especially for sellers who start the selling process without any historical data and can collect the data on the outcomes of the auctions while making reserve price decisions over time. History: Accepted by RamRamesh, Area Editor for Data Science & Machine Learning. Supplemental Material: The supplementary material is available at https://doi.org/10.1287/ijoc.2022.1199 .