Knowledge that Transforms

From Tree Ensemble Models to Decisions

In a dynamic setting, decision makers update their reference point as a function of previous decision and outcomes. In “Failing to Foresee the Updating of the Reference Point Leads to Time-Inconsistent Investment,” Strub and Li investigate the influence of reference point updating on decision making and in particular, address whether a decision maker foresees the updating of the reference point in the context of discrete time portfolio optimization. By deriving and comparing optimal trading strategies under various frameworks and reference point updating rules and then, simulating how typical investment behavior would look like in each setting, they come to the following conclusion: a loss-averse decision maker with a time-varying reference point exhibiting realistic investment behavior fails to foresee the future updating of the reference point, and this failure leads to time-inconsistent investment.

Diffusion and Seeding in Random Networks

This paper studies a novel decomposition scheme, utilizing decision diagrams for modeling elements of a problem where typical linear relaxations fail to provide sufficiently tight bounds. Given a collection of decision diagrams, each representing a portion of the problem, together with linear inequalities modeling other portions of the problem, how can one efficiently optimize over such a representation? In this paper, we model the problem as a consistent path problem, where a path in each diagram has to be identified, all of which agree on the value assignments to variables. We establish complexity results and propose a branch-and-cut framework for solving the decomposition. Through application to binary cubic optimization and a variant of the market split problem, we show that the decomposition approach provides significant improvement gains over standard linear models.

Amazon and Apple, which sell tablet devices, have adopted different implicit information policies and developed distinct “reputations” about their tablets’ sales volume release. With Amazon, “even a number as basic, and presumably impressive, as how many Kindle e-readers the company sells is never released.” With Apple, iPhone and iPad sales numbers are always released, even if they are disappointing. In the paper “Information Disclosure and Pricing Policies for Sales of Network Goods,” the authors study the sales information release policy, disclosure versus nondisclosure, for selling network goods subject to market size uncertainty. They identify two countervailing effects, a prodisclosure “Matthew effect” and an antidisclosure saturation effect, that drive the firms’ sales information disclosure policies. In addition, the authors also study the situation where the firm can decide on an all-or-nothing information disclosure policy together with endogenized prices, including state-independent pricing, contingent preannounced pricing, and contingent pricing without commitment.

In many sequential decision-making settings where there is uncertainty about the reward of each action, frequent selection of specific actions may reduce expected reward while choosing less frequently selected actions could lead to an increase. These effects are commonly observed in settings ranging from personalized healthcare interventions and targeted online advertising. To address this problem, the authors propose a new class of models called ROGUE (reducing or gaining unknown efficacy) multiarmed bandits. In the paper, the authors present a maximum likelihood approach to estimate the parameters of these models, and we show that these estimates can be used to construct upper confidence bound algorithms and epsilon-greedy algorithms for optimizing these models with strong theoretical guarantees. The authors conclude with a simulation study to show that these algorithms perform better than current nonstationary bandit algorithms in terms of both cumulative regret and average reward.

Many methods that have been proposed to solve large-scale MILP problems rely on the use of decomposition strategies. These methods exploit either the primal or dual structures of the problems by applying the Benders decomposition or Lagrangian dual decomposition strategy, respectively. In “The Benders Dual Decomposition Method,” Rahmaniani, Ahmed, Crainic, Gendreau, and Rei propose a new and high-performance approach that combines the complementary advantages of both strategies. The authors show that this method (i) generates stronger feasibility and optimality cuts compared with the classical Benders method, (ii) can converge to the optimal integer solution at the root node of the Benders master problem, and (iii) is capable of generating high-quality incumbent solutions at the early iterations of the algorithm. The developed algorithm obtains encouraging computational results when used to solve various benchmark MILP problems.

Jose L. Walteros and Austin Buchanan

In several scientific and industrial applications, it is desirable to build compact, interpretable learning models where the output depends on a small number of input features. Recent work has shown that such best-subset selection-type problems can be solved with modern mixed integer optimization solvers. Despite their promise, such solvers often come at a steep computational price when compared with open-source, efficient specialized solvers based on convex optimization and greedy heuristics. In “Fast Best-Subset Selection: Coordinate Descent and Local Combinatorial Optimization Algorithms,” Hussein Hazimeh and Rahul Mazumder push the frontiers of computation for best-subset-type problems. Their algorithms deliver near-optimal solutions for problems with up to a million features—in times comparable with the fast convex solvers. Their work suggests that principled optimization methods play a key role in devising tools central to interpretable machine learning, which can help in gaining a deeper understanding of their statistical properties.