21 results on '"Menache, Ishai"'
Search Results
2. Large Language Models for Supply Chain Optimization
- Author
-
Li, Beibin, Mellou, Konstantina, Zhang, Bo, Pathuri, Jeevan, and Menache, Ishai
- Subjects
Computer Science - Artificial Intelligence ,Computer Science - Computation and Language ,Computer Science - Discrete Mathematics ,Computer Science - Machine Learning - Abstract
Supply chain operations traditionally involve a variety of complex decision making problems. Over the last few decades, supply chains greatly benefited from advances in computation, which allowed the transition from manual processing to automation and cost-effective optimization. Nonetheless, business operators still need to spend substantial efforts in explaining and interpreting the optimization outcomes to stakeholders. Motivated by the recent advances in Large Language Models (LLMs), we study how this disruptive technology can help bridge the gap between supply chain automation and human comprehension and trust thereof. We design OptiGuide -- a framework that accepts as input queries in plain text, and outputs insights about the underlying optimization outcomes. Our framework does not forgo the state-of-the-art combinatorial optimization technology, but rather leverages it to quantitatively answer what-if scenarios (e.g., how would the cost change if we used supplier B instead of supplier A for a given demand?). Importantly, our design does not require sending proprietary data over to LLMs, which can be a privacy concern in some circumstances. We demonstrate the effectiveness of our framework on a real server placement scenario within Microsoft's cloud supply chain. Along the way, we develop a general evaluation benchmark, which can be used to evaluate the accuracy of the LLM output in other scenarios.
- Published
- 2023
3. A Deep Learning Perspective on Network Routing
- Author
-
Perry, Yarin, Frujeri, Felipe Vieira, Hoch, Chaim, Kandula, Srikanth, Menache, Ishai, Schapira, Michael, and Tamar, Aviv
- Subjects
Computer Science - Networking and Internet Architecture ,Computer Science - Machine Learning - Abstract
Routing is, arguably, the most fundamental task in computer networking, and the most extensively studied one. A key challenge for routing in real-world environments is the need to contend with uncertainty about future traffic demands. We present a new approach to routing under demand uncertainty: tackling this challenge as stochastic optimization, and employing deep learning to learn complex patterns in traffic demands. We show that our method provably converges to the global optimum in well-studied theoretical models of multicommodity flow. We exemplify the practical usefulness of our approach by zooming in on the real-world challenge of traffic engineering (TE) on wide-area networks (WANs). Our extensive empirical evaluation on real-world traffic and network topologies establishes that our approach's TE quality almost matches that of an (infeasible) omniscient oracle, outperforming previously proposed approaches, and also substantially lowers runtimes., Comment: To appear at NSDI 2023
- Published
- 2023
4. Hindsight Learning for MDPs with Exogenous Inputs
- Author
-
Sinclair, Sean R., Frujeri, Felipe, Cheng, Ching-An, Marshall, Luke, Barbalho, Hugo, Li, Jingling, Neville, Jennifer, Menache, Ishai, and Swaminathan, Adith
- Subjects
Computer Science - Machine Learning ,Statistics - Machine Learning ,68Q32 ,I.2.6 - Abstract
Many resource management problems require sequential decision-making under uncertainty, where the only uncertainty affecting the decision outcomes are exogenous variables outside the control of the decision-maker. We model these problems as Exo-MDPs (Markov Decision Processes with Exogenous Inputs) and design a class of data-efficient algorithms for them termed Hindsight Learning (HL). Our HL algorithms achieve data efficiency by leveraging a key insight: having samples of the exogenous variables, past decisions can be revisited in hindsight to infer counterfactual consequences that can accelerate policy improvements. We compare HL against classic baselines in the multi-secretary and airline revenue management problems. We also scale our algorithms to a business-critical cloud resource management problem -- allocating Virtual Machines (VMs) to physical machines, and simulate their performance with real datasets from a large public cloud provider. We find that HL algorithms outperform domain-specific heuristics, as well as state-of-the-art reinforcement learning methods., Comment: 52 pages, 6 figures
- Published
- 2022
5. Truthful Online Scheduling of Cloud Workloads under Uncertainty
- Author
-
Babaioff, Moshe, Lempel, Ronny, Lucier, Brendan, Menache, Ishai, Slivkins, Aleksandrs, and Wong, Sam Chiu-Wai
- Subjects
Computer Science - Computer Science and Game Theory ,Computer Science - Data Structures and Algorithms - Abstract
Cloud computing customers often submit repeating jobs and computation pipelines on \emph{approximately} regular schedules, with arrival and running times that exhibit variance. This pattern, typical of training tasks in machine learning, allows customers to partially predict future job requirements. We develop a model of cloud computing platforms that receive statements of work (SoWs) in an online fashion. The SoWs describe future jobs whose arrival times and durations are probabilistic, and whose utility to the submitting agents declines with completion time. The arrival and duration distributions, as well as the utility functions, are considered private customer information and are reported by strategic agents to a scheduler that is optimizing for social welfare. We design pricing, scheduling, and eviction mechanisms that incentivize truthful reporting of SoWs. An important challenge is maintaining incentives despite the possibility of the platform becoming saturated. We introduce a framework to reduce scheduling under uncertainty to a relaxed scheduling problem without uncertainty. Using this framework, we tackle both adversarial and stochastic submissions of statements of work, and obtain logarithmic and constant competitive mechanisms, respectively., Comment: To appear in TheWebConf 2022
- Published
- 2022
6. Online Virtual Machine Allocation with Predictions
- Author
-
Buchbinder, Niv, Fairstein, Yaron, Mellou, Konstantina, Menache, Ishai, Joseph, and Naor
- Subjects
Computer Science - Data Structures and Algorithms ,F.2.2 - Abstract
The cloud computing industry has grown rapidly over the last decade, and with this growth there is a significant increase in demand for compute resources. Demand is manifested in the form of Virtual Machine (VM) requests, which need to be assigned to physical machines in a way that minimizes resource fragmentation and efficiently utilizes the available machines. This problem can be modeled as a dynamic version of the bin packing problem with the objective of minimizing the total usage time of the bins (physical machines). Earlier works on dynamic bin packing assumed that no knowledge is available to the scheduler and later works studied models in which lifetime/duration of each "item" (VM in our context) is available to the scheduler. This extra information was shown to improve exponentially the achievable competitive ratio. Motivated by advances in Machine Learning that provide good estimates of workload characteristics, this paper studies the effect of having extra information regarding future (total) demand. In the cloud context, since demand is an aggregate over many VM requests, it can be predicted with high accuracy (e.g., using historical data). We show that the competitive factor can be dramatically improved by using this additional information; in some cases, we achieve constant competitiveness, or even a competitive factor that approaches 1. Along the way, we design new offline algorithms with improved approximation ratios for the dynamic bin-packing problem., Comment: 30 pages
- Published
- 2020
7. Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency
- Author
-
Perez-Salazar, Sebastian, Menache, Ishai, Singh, Mohit, and Toriello, Alejandro
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Distributed, Parallel, and Cluster Computing ,Computer Science - Computer Science and Game Theory - Abstract
Cloud computing has motivated renewed interest in resource allocation problems with new consumption models. A common goal is to share a resource, such as CPU or I/O bandwidth, among distinct users with different demand patterns as well as different quality of service requirements. To ensure these service requirements, cloud offerings often come with a service level agreement (SLA) between the provider and the users. An SLA specifies the amount of a resource a user is entitled to utilize. In many cloud settings, providers would like to operate resources at high utilization while simultaneously respecting individual SLAs. There is typically a tradeoff between these two objectives; for example, utilization can be increased by shifting away resources from idle users to "scavenger" workload, but with the risk of the former then becoming active again. We study this fundamental tradeoff by formulating a resource allocation model that captures basic properties of cloud computing systems, including SLAs, highly limited feedback about the state of the system, and variable and unpredictable input sequences. Our main result is a simple and practical algorithm that achieves near-optimal performance on the above two objectives. First, we guarantee nearly optimal utilization of the resource even if compared to the omniscient offline dynamic optimum. Second, we simultaneously satisfy all individual SLAs up to a small error. The main algorithmic tool is a multiplicative weight update algorithm, and a primal-dual argument to obtain its guarantees. We also provide numerical validation on real data to demonstrate the performance of our algorithm in practical applications.
- Published
- 2018
8. ERA: A Framework for Economic Resource Allocation for the Cloud
- Author
-
Babaioff, Moshe, Mansour, Yishay, Nisan, Noam, Noti, Gali, Curino, Carlo, Ganapathy, Nar, Menache, Ishai, Reingold, Omer, Tennenholtz, Moshe, and Timnat, Erez
- Subjects
Computer Science - Computer Science and Game Theory ,Computer Science - Distributed, Parallel, and Cluster Computing - Abstract
Cloud computing has reached significant maturity from a systems perspective, but currently deployed solutions rely on rather basic economics mechanisms that yield suboptimal allocation of the costly hardware resources. In this paper we present Economic Resource Allocation (ERA), a complete framework for scheduling and pricing cloud resources, aimed at increasing the efficiency of cloud resources usage by allocating resources according to economic principles. The ERA architecture carefully abstracts the underlying cloud infrastructure, enabling the development of scheduling and pricing algorithms independently of the concrete lower-level cloud infrastructure and independently of its concerns. Specifically, ERA is designed as a flexible layer that can sit on top of any cloud system and interfaces with both the cloud resource manager and with the users who reserve resources to run their jobs. The jobs are scheduled based on prices that are dynamically calculated according to the predicted demand. Additionally, ERA provides a key internal API to pluggable algorithmic modules that include scheduling, pricing and demand prediction. We provide a proof-of-concept software and demonstrate the effectiveness of the architecture by testing ERA over both public and private cloud systems -- Azure Batch of Microsoft and Hadoop/YARN. A broader intent of our work is to foster collaborations between economics and system communities. To that end, we have developed a simulation platform via which economics and system experts can test their algorithmic implementations.
- Published
- 2017
- Full Text
- View/download PDF
9. Truthful Online Scheduling with Commitments
- Author
-
Azar, Yossi, Kalp-Shaltiel, Inna, Lucier, Brendan, Menache, Ishai, Joseph, Naor, and Yaniv, Jonathan
- Subjects
Computer Science - Data Structures and Algorithms ,Computer Science - Computer Science and Game Theory ,F.2.2 ,K.6.2 - Abstract
We study online mechanisms for preemptive scheduling with deadlines, with the goal of maximizing the total value of completed jobs. This problem is fundamental to deadline-aware cloud scheduling, but there are strong lower bounds even for the algorithmic problem without incentive constraints. However, these lower bounds can be circumvented under the natural assumption of deadline slackness, i.e., that there is a guaranteed lower bound $s > 1$ on the ratio between a job's size and the time window in which it can be executed. In this paper, we construct a truthful scheduling mechanism with a constant competitive ratio, given slackness $s > 1$. Furthermore, we show that if $s$ is large enough then we can construct a mechanism that also satisfies a commitment property: it can be determined whether or not a job will finish, and the requisite payment if so, well in advance of each job's deadline. This is notable because, in practice, users with strict deadlines may find it unacceptable to discover only very close to their deadline that their job has been rejected.
- Published
- 2015
- Full Text
- View/download PDF
10. Flows and Decompositions of Games: Harmonic and Potential Games
- Author
-
Candogan, Ozan, Menache, Ishai, Ozdaglar, Asuman, and Parrilo, Pablo A.
- Subjects
Computer Science - Computer Science and Game Theory ,Mathematics - Optimization and Control - Abstract
In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and study the structural and equilibrium properties of this new class of games. Intuitively, the potential component of a game captures interactions that can equivalently be represented as a common interest game, while the harmonic part represents the conflicts between the interests of the players. We make this intuition precise, by studying the properties of these two classes, and show that indeed they have quite distinct and remarkable characteristics. For instance, while finite potential games always have pure Nash equilibria, harmonic games generically never do. Moreover, we show that the nonstrategic component does not affect the equilibria of a game, but plays a fundamental role in their efficiency properties, thus decoupling the location of equilibria and their payoff-related properties. Exploiting the properties of the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the properties of potential and harmonic games to "nearby" games. We exemplify this point by showing that the set of approximate equilibria of an arbitrary game can be characterized through the equilibria of its projection onto the set of potential games.
- Published
- 2010
- Full Text
- View/download PDF
11. Multi-Itinerary Optimization as Cloud Service.
- Author
-
Cristian, Alexandru, Marshall, Luke, Negrea, Mihai, Stoichescu, Flavius, Cao, Peiwei, and Menache, Ishai
- Subjects
CLOUD computing ,TRAFFIC flow ,ALGORITHMS ,TRAVELING salesman problem ,TRAVEL time (Traffic engineering) - Abstract
In this paper, we describe multi-itinerary optimization (MIO)--a novel Bing Maps service that automates the process of building itineraries for multiple agents while optimizing their routes to minimize travel time or distance. MIO can be used by organizations with a fleet of vehicles and drivers, mobile salesforce, or a team of personnel in the field, to maximize workforce efficiency. It supports a variety of constraints, such as service time windows, duration, priority, pickup and delivery dependencies, and vehicle capacity. MIO also considers traffic conditions between locations, resulting in algorithmic challenges at multiple levels (e.g., calculating time-dependent travel-time distance matrices at scale and scheduling services for multiple agents). To support an end-to-end cloud service with turnaround times of a few seconds, our algorithm design targets a sweet spot between accuracy and performance. Toward that end, we build a scalable approach based on the ALNS metaheuristic. Our experiments show that accounting for traffic significantly improves solution quality: MIO finds efficient routes that avoid late arrivals, whereas traffic-agnostic approaches result in a 15% increase in the combined travel time and the lateness of an arrival. Furthermore, our approach generates itineraries with substantially higher quality than a cutting-edge heuristic (LKH), with faster running times for large instances. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
12. Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency
- Author
-
Perez-Salazar, Sebastian, primary, Menache, Ishai, additional, Singh, Mohit, additional, and Toriello, Alejandro, additional
- Published
- 2022
- Full Text
- View/download PDF
13. Flows and Decompositions of Games: Harmonic and Potential Games
- Author
-
Candogan, Ozan, Menache, Ishai, Ozdaglar, Asuman, and Parrilo, Pablo A.
- Published
- 2011
- Full Text
- View/download PDF
14. Dynamic discrete power control in cellular networks
- Author
-
Altman, Eitan, Avrachenkov, Konstantin, Menache, Ishai, Miller, Gregory, Prabhu, Balakrishna J., and Shwartz, Adam
- Subjects
Algorithm ,Wireless technology ,Algorithms -- Methods ,Mobile communication systems -- Methods ,Wireless communication systems -- Methods ,Digital control systems -- Methods - Published
- 2009
15. Basis Function Adaptation in Temporal Difference Reinforcement Learning
- Author
-
Menache, Ishai, Mannor, Shie, and Shimkin, Nahum
- Published
- 2005
- Full Text
- View/download PDF
16. Dynamic Online-Advertising Auctions as Stochastic Scheduling
- Author
-
Menache, Ishai, Ozdaglar, Asuman E., Srikant, R., Acemoglu, Daron, Massachusetts Institute of Technology. Department of Economics, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Menache, Ishai, Ozdaglar, Asuman E., and Acemoglu, Daron
- Abstract
We study dynamic models of online-advertising auctions in the Internet: advertisers compete for space on a web page over multiple time periods, and the web page displays ads in differentiated slots based on their bids and other considerations. The complex interactions between the advertisers and the website (which owns the web page) is modeled as a dynamic game. Our goal is to derive ad-slot placement and pricing strategies which maximize the expected revenue of the website. We show that the problem can be transformed into a scheduling problem familiar to queueing theorists. When only one advertising slot is available on a webpage, we derive the optimal revenue-maximizing solution by making connections to the familiar cμ rule used in queueing theory. More generally, we show that a cμ-like rule can serve as a good suboptimal solution, while the optimal solution itself may be computed using dynamic programming techniques.
- Published
- 2009
17. Team and noncooperative solutions to access control with priorities
- Author
-
Altman, Eitan, Menache, Ishai, Suarez, Alberto, Altman, Eitan, Menache, Ishai, and Suarez, Alberto
- Subjects
authorisation, game theory - Published
- 2009
18. Socially Optimal Pricing of Cloud Computing Resources
- Author
-
Menache, Ishai, Shimkin, Nahum, Ozdaglar, Asuman E., Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. Laboratory for Information and Decision Systems, and Ozdaglar, Asuman E.
- Abstract
The cloud computing paradigm offers easily accessible computing resources of variable size and capabilities. We consider a cloud-computing facility that provides simultaneous service to a heterogeneous, time-varying population of users, each associated with a distinct job. Both the completion time, as well as the user's utility, may depend on the amount of computing resources applied to the job. In this paper, we focus on the objective of maximizing the long-term social surplus, which comprises of the aggregate utility of executed jobs minus load-dependent operating expenses. Our problem formulation relies on basic notions of welfare economics, augmented by relevant queueing aspects. We first analyze the centralized setting, where an omniscient controller may regulate admission and resource allocation to each arriving job based on its individual type. Under appropriate convexity assumptions on the operating costs and individual utilities, we establish existence and uniqueness of the social optimum. We proceed to show that the social optimum may be induced by a single per-unit price, which charges a fixed amount per unit time and resource from all users.
- Published
- 2011
19. A state action frequency approach to throughput maximization over uncertain wireless channels
- Author
-
Shie Mannor, Ishai Menache, Krishna Jagannathan, Eytan Modiano, Massachusetts Institute of Technology. Department of Aeronautics and Astronautics, Massachusetts Institute of Technology. Laboratory for Information and Decision Systems, Modiano, Eytan H., Jagannathan, Krishna Prasanna, and Menache, Ishai
- Subjects
Mathematical optimization ,Linear programming ,Computer science ,Distributed computing ,Markov process ,Throughput ,02 engineering and technology ,01 natural sciences ,Scheduling (computing) ,symbols.namesake ,010104 statistics & probability ,Computer Science::Networking and Internet Architecture ,0202 electrical engineering, electronic engineering, information engineering ,Wireless ,0101 mathematics ,Queue ,Queue management system ,Markov chain ,business.industry ,Applied Mathematics ,020206 networking & telecommunications ,Computational Mathematics ,Channel state information ,Modeling and Simulation ,symbols ,Markov decision process ,business ,Communication channel - Abstract
We consider scheduling over a wireless system, where the channel state information is not available a priori to the scheduler, but can be inferred from the past. Specifically, the wireless system is modeled as a network of parallel queues. We assume that the channel state of each queue evolves stochastically as an ON/OFF Markov chain. The scheduler, which is aware of the queue lengths but is oblivious of the channel states, has to choose one queue at a time for transmission. The scheduler has no information regarding the current channel states, but can estimate them by using the acknowledgment history. We first characterize the capacity region of the system using tools from Markov Decision Processes (MDP) theory. Specifically, we prove that the capacity region boundary is the uniform limit of a sequence of Linear Programming (LP) solutions. Next, we combine the LP solution with a queue length based scheduling mechanism that operates over long `frames,' to obtain a throughput optimal policy for the system. By incorporating results from MDP theory within the Lyapunov-stability framework, we show that our frame-based policy stabilizes the system for all arrival rates that lie in the interior of the capacity region., National Science Foundation (U.S.) (NSF grants CNS-0626781), National Science Foundation (U.S.) (NSF grant CNS-0915988), United States. Army Research Office (ARO Muri Grant W911NF-08-1-0238), Israel Science Foundation (contract 890015)
- Published
- 2011
20. Flows and Decompositions of Games: Harmonic and Potential Games
- Author
-
Ozan Candogan, Asuman Ozdaglar, Pablo A. Parrilo, Ishai Menache, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. Laboratory for Information and Decision Systems, Ozdaglar, Asuman E., Candogan, Utku Ozan, Menache, Ishai, and Parrilo, Pablo A.
- Subjects
FOS: Computer and information sciences ,0209 industrial biotechnology ,Class (set theory) ,Computer Science::Computer Science and Game Theory ,Computer science ,General Mathematics ,Harmonic (mathematics) ,02 engineering and technology ,Management Science and Operations Research ,Projection (linear algebra) ,symbols.namesake ,020901 industrial engineering & automation ,Computer Science - Computer Science and Game Theory ,Component (UML) ,0502 economics and business ,FOS: Mathematics ,050207 economics ,Representation (mathematics) ,Mathematics - Optimization and Control ,05 social sciences ,ComputingMilieux_PERSONALCOMPUTING ,Computer Science Applications ,Algebra ,Flow (mathematics) ,Optimization and Control (math.OC) ,Nash equilibrium ,symbols ,Computer Science and Game Theory (cs.GT) - Abstract
In this paper we introduce a novel flow representation for finite games in strategic form. This representation allows us to develop a canonical direct sum decomposition of an arbitrary game into three components, which we refer to as the potential, harmonic, and nonstrategic components. We analyze natural classes of games that are induced by this decomposition, and in particular, focus on games with no harmonic component and games with no potential component. We show that the first class corresponds to the well-known potential games. We refer to the second class of games as harmonic games, and demonstrate that this new class has interesting properties which contrast with properties of potential games. Exploiting the decomposition framework, we obtain explicit expressions for the projections of games onto the subspaces of potential and harmonic games. This enables an extension of the equilibrium properties of potential and harmonic games to “nearby” games., National Science Foundation (U.S.). (Grant number DMI- 0545910), National Science Foundation (U.S.). (Grant number ECCS-0621922), United States. Air Force Office of Scientific Research. Multidisciplinary University Research Initiative (Grant number FA9550-06-1-0303), National Science Foundation (U.S.). (Grant number FRG 0757207), United States. Defense Advanced Research Projects Agency. Information Theory for Mobile Ad-Hoc Networks Program, Marie Curie International Fellowship. (7th European Community Framework Programme)
- Published
- 2011
21. Near-Optimal Power Control in Wireless Networks: A Potential Game Approach
- Author
-
Utku Ozan Candogan, Asuman Ozdaglar, Pablo A. Parrilo, Ishai Menache, Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology. Laboratory for Information and Decision Systems, Ozdaglar, Asuman E., Candogan, Utku Ozan, Menache, Ishai, and Parrilo, Pablo A.
- Subjects
Lyapunov function ,Computer Science::Computer Science and Game Theory ,symbols.namesake ,Mathematical optimization ,Computer science ,Wireless network ,Distributed computing ,symbols ,Maximization ,Algorithmic game theory ,Potential game ,Game theory ,Power control - Abstract
We study power control in a multi-cell CDMA wireless system whereby self-interested users share a common spectrum and interfere with each other. Our objective is to design a power control scheme that achieves a (near) optimal power allocation with respect to any predetermined network objective (such as the maximization of sum-rate, or some fairness criterion). To obtain this, we introduce the potential-game approach that relies on approximating the underlying noncooperative game with a "close" potential game, for which prices that induce an optimal power allocation can be derived. We use the proximity of the original game with the approximate game to establish through Lyapunov-based analysis that natural user-update schemes (applied to the original game) converge within a neighborhood of the desired operating point, thereby inducing near-optimal performance in a dynamical sense. Additionally, we demonstrate through simulations that the actual performance can in practice be very close to optimal, even when the approximation is inaccurate. As a concrete example, we focus on the sum-rate objective, and evaluate our approach both theoretically and empirically., National Science Foundation (U.S.) (DMI-05459100), National Science Foundation (U.S.) (DMI-0545910), United States. Defense Advanced Research Projects Agency (ITMANET program), 7th European Community Framework Programme (Marie Curie International Fellowship)
- Published
- 2010
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.