This study develops a data-driven approach to solve constrained optimization problems in which the decision maker does not have an analytic form for the objective function but knows what decision variables affect the function. The approach makes direct use of the available data, rather than first using the data to estimate the objective function and then solving the problem as a traditional optimization problem. The difficulty in first estimating the unknown objective function is that the decision maker needs to have sufficient knowledge of its properties that are necessary to guide the estimation process. Thus, our approach is appropriate for situations where such structural knowledge is absent, either because the domain is very complex or because the knowledge is deliberately hidden by a partner firm that has a vested interest in the outcome of the decision. Our approach comes with a worst-case performance guarantee that improves with the characteristics (size, pervasiveness) of the available data. We illustrate our technique on a traffic-stream mixing problem encountered by a supply side Internet advertising network that wishes to optimize the click revenue earned from ads. A head-to-head comparison (with the existing method used) on real data shows a significant increase (≥10%, on average) in the revenue. We also demonstrate the value of our approach under more general conditions. The online supplement is available at https://doi.org/10.1287/ijoc.2018.0818 .

Access control mechanisms in software systems administer user privileges by granting users permission to perform certain operations while denying unauthorized access to others. Such mechanisms are essential to ensure that important business functions in an organization are conducted securely and smoothly. Currently, the dominant access control approach in most major software systems is role-based access control. In this approach, permissions are first assigned to roles, and users acquire permissions by becoming members of certain roles. However, given the dynamic nature of organizations, a fixed set of roles usually cannot meet the demands that users (existing or new) have to conduct business. The typical response to this problem is to myopically create new roles to meet immediate demand that cannot be satisfied by an existing set of roles. This ad hoc creation of roles invariably leads to a proliferation in the number of roles with the accompanying administrative overhead. Based on discussions with practitioners, we propose a role refinement scheme that reconstructs a system of roles to reduce the cost of role management. We first show that the role-refinement problem is strongly NP-hard and then provide two polynomial-time approximation algorithms (a greedy algorithm and a randomized rounding algorithm) and establish their performance guarantees. Finally, numerical experiments—based on a real data set from a firm's enterprise resource planning system—are conducted to demonstrate the applicability and performance of our refinement scheme.

The explosive growth in the variety and size of social networks has focused attention on searching these networks for useful structures. Like the Internet or the telephone network, the ability to efficiently search large social networks will play an important role in the extent of their use by individuals and organizations alike. However, unlike these domains, search on social networks is likely to involve measures that require a set of individuals to collectively satisfy some skill requirement or be tightly related to each other via some underlying social property of interest. The aim of this paper is to highlight—and demonstrate via specific examples—the need for algorithmic results for some fundamental set-based notions on which search in social networks is expected to be prevalent. To this end, we argue that the concepts of an influential set and a central set that highlight, respectively, the specific role and the specific location of a set are likely to be useful in practice. We formulate two specific search problems: the elite group problem (EGP) and the portal problem (PP), that represent these two concepts and provide a variety of algorithmic results. We first demonstrate the relevance of EGP and PP across a variety of social networks reported in the literature. For simple networks (e.g., structured trees and bipartite graphs, cycles, paths), we show that an optimal solution to both EGP and PP is easy to obtain. Next, we show that EGP is polynomially solvable on a general graph, whereas PP is strongly NP-hard. Motivated by practical considerations, we also discuss (i) a size-constrained variant of EGP together with its penalty-based relaxation and (ii) the solution of PP on balanced and full d-trees and general trees.

Cluster tools (also referred to as robotic cells) are extensively used in semiconductor wafer fabrication. We consider the problem of scheduling operations in an m -machine cluster tool that produces identical parts (wafers). Each machine is equipped with a unit-capacity input buffer and a unit-capacity output buffer. The machines and buffers are served by a dual-gripper robot. Each wafer is processed on each of the m machines, and the objective is to find a cyclic sequence of robot moves that minimizes the long-run average time to produce a part or, equivalently, maximizes the throughput. We first obtain a tight upper bound on the optimal throughput and then use this bound to obtain an asymptotically optimal sequence under conditions that are common in practice. Next, we quantify the improvement in productivity that can be realized from the use of unit-capacity input and output buffers at the machines. Finally, we illustrate our analysis on cluster tools with realistic parameters, based on our work with a Dallas-based semiconductor equipment manufacturer.

The nine The ten papers in this special issue focus on three areas: equipment automation, operations automation, and modeling.

We consider the problem of grooming in all-optical networks to maximize traffic. We present an integer-programming formulation while constraining the number of optical transceivers at each node, the link load, and the capacity of each lightpath. Based on the structural properties of the problem, we develop a heuristic based on a column-generation technique. The algorithm is easy to implement, requires a modest amount of CPU time, and provides high-quality solutions. To ascertain the quality of solutions obtained by our algorithm, we present an alternative formulation that allows us to develop an upper bound using a Lagrangian-relaxation technique. An extensive computational study is presented.

We consider the problem of designing quality-of-service (QoS)-constrained routes for a set of multicast groups in an all-optical network. We present an integer goal programming formulation with the objectives of minimizing the cost of the multicast solution and minimizing the maximum link load of the network. Based on the structural properties of the problem, we develop a variable-fixing heuristic which is easy to implement, requires a modest amount of CPU time, and provides high-quality solutions. An extensive computational study is presented to justify our claims

The increasing popularity of the World Wide Web has made it an attractive medium for advertisers. As more advertisers place Internet advertisements (hereafter also called "ads"), it has become important for Web site owners to maximize revenue through the optimal selection and placement of these ads. Unlike most previous research, we consider a hybrid pricing model, where the price advertisers pay is a function of 1) the number of exposures of the ad and 2) the number of clicks on the ad. The problem is finding an ad schedule to maximize the Web site revenue under a hybrid pricing model. We formulate two versions of the problem - static and dynamic - and propose a variety of efficient solution techniques that provide near-optimal solutions. In the dynamic version, the schedule of ads is changed based on individual user click behavior. We show by using a theoretical proof under special circumstances and an experimental demonstration under general conditions that a schedule that adapts to the user click behavior consistently outperforms one that does not. We also demonstrate that to benefit from observing the user click behavior, the associated probability parameter need not be estimated accurately. For both of these versions, we examine the sensitivity of the revenue with respect to the model parameters.

Efficient use of the limited energy available with sensor nodes is an important consideration for routing protocols. In an attempt to improve the lifetime of a sensor network using energy-aware routing, existing protocols might route a packet along a longer path - thus increasing its latency. Many applications of sensor networks, e.g., surveillance and security, require that the maximum latency in routing a packet be bounded. We consider the problem of energy-aware routing with a bound on the maximum number of hops any packet can traverse to reach a base station. We formulate a linear program (LP) to minimize the maximum energy spent by any node in the network subject to a limit on the number of hops any packet may traverse. A solution to the LP yields routing information in terms of the number of packets to be forwarded along each edge; however, non-integral values of the flow variables might require splitting a packet across multiple routes. As packet splitting incurs additional overhead in tracking various fragments, it is desirable to have integral routing information. We, therefore, propose a rounding algorithm based on the minimum cost flow problem and prove that the energy spent by a node in the resulting integral solution is at most a constant more than the optimal LP solution

We consider the problem of link scheduling in a sensor network employing a TDMA MAC protocol. Our link scheduling algorithm involves two phases. In the first phase, we assign a color to each edge in the network such that no two edges incident on the same node are assigned the same color. We propose a distributed edge coloring algorithm that needs at most (/spl delta/+1) colors, where /spl delta/ is the maximum degree of the graph. To the best of our knowledge, this is the first distributed algorithm that can edge color a graph with at most (/spl delta/+1) colors. In the second phase, we map each color to a unique timeslot and attempt to identify a direction of transmission along each edge such that the hidden terminal and the exposed terminal problems are avoided. Next, considering topologies for which a feasible solution does not exist, we obtain a direction of transmission for each edge using additional timeslots, if necessary. Finally, we show that reversing the direction of transmission along every edge leads to another feasible direction of transmission. Using both the transmission assignments we obtain a TDMA MAC schedule, which enables two-way communication between every pair of neighbors. For acyclic topologies, we show that at most 2(/spl delta/+1) timeslots are required. Through simulations we show that for sparse graphs with cycles the number of timeslots assigned is close to 2(/spl delta/+1).

Sensor networks consist of a large number of sensor nodes performing distributed sensing and event detection. As sensor nodes are energy-constrained, energy-efficient routing is essential for increasing the lifetime of a sensor network. In Gandham, SR et al. (2003), we proposed an ILP-based method for routing in sensor networks with multiple mobile base stations. The ILP-based method does not guarantee integral routes and bounds on running time. In this paper, we consider static base stations and propose an algorithmic approach to obtain integral energy-efficient routes. We propose to split the lifetime of a sensor network into equal periods of time referred to as rounds and model the energy constrained routing during a round as polynomial-time solvable flow problems. The flow information from an optimum solution to a flow problem is then used as a basis for an energy-efficient routing protocol. Through simulations, we demonstrate that our routing algorithm performs significantly better than the shortest path based algorithms and consumes less energy than the ILP-based method. In addition, we present an algorithm to determine, a priori, lower bound on the lifetime of the sensor network.

One of the main design issues for a sensor network is conservation of the energy available at each sensor node. We propose to deploy multiple, mobile base stations to prolong the lifetime of the sensor network. We split the lifetime of the sensor network into equal periods of time known as rounds. Base stations are relocated at the start of a round. Our method uses an integer linear program to determine new locations for the base stations and a flow-based routing protocol to ensure energy efficient routing during each round. We propose four metrics and evaluate our solution using these metrics. Based on the simulation results we show that employing multiple, mobile base stations in accordance with the solution given by our schemes would significantly increase the lifetime of the sensor network.

We consider the problem of spare capacity allocation in mesh networks for link restoration. Only single link failures are considered and restored traffic is not split across multiple paths. In our model, links that are not part of the original transport network can also be used for restoration. This model, which is a generalized version, is different from the traditional model studied in literature. We present two heuristics to solve this problem and compare their performance with known lower bounds and the optimal solution. In numerous simulation experiments on randomly generated graphs containing up to 100 nodes, the heuristics often produced solutions within 3% of the lower bound for sparse graphs. The Integer Linear Programming solutions suggest that the heuristic solutions are closer to optimal than indicated by the deviation from the lower bounds. The results are optimal or near optimal (within 0.5% of the optimum values) for small graphs containing up to 8 nodes and 18 edges.

In this article, we consider a class of 0-1 programs that, although innocent looking, is a challenge for existing solution methods. Solving even small instances from this class is extremely difficult for conventional branch-and-bound or branch-and-cut algorithms. We also experimented with basis reduction algorithms and with dynamic programming without much success. The article then examines the performance of two other methods: a group relaxation for 0,1 programs, and a sorting-based procedure following an idea of Wolsey. Although the results with these two methods are somewhat better than with the other four when it comes to checking feasibility, we offer this class of small 0,1 programs as a challenge to the research community.

INTLIB is meant to be a readily available, portable, exhaustively documented interval arithmetic library, written in standard Fortran 77. Its underlying philosophy is to provide a standard for interval operations to aid in efficiently transporting programs involving interval arithmetic. The model is the BLAS package, for basic linear algebra operations. The library is composed of elementary interval arithmetic routines, standard function routines for interval data and values, and utility routines. The library can be used with INTBIS (Algorithm 681), and a Fortran 90 module to use the library to define an interval data type is available from the first author.