检索结果-内蒙古大学图书馆

Inverse optimization of integer programming games for parameter estimation arising from competitive retail location selection

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2024年第3期312卷 938-953页

作者： Croenert, Tobias Martin, Layla Minner, Stefan Tang, Christopher S. Tech Univ Munich Sch Management D-80333 Munich Germany Eindhoven Univ Technol Sch Ind Engn Eindhoven Netherlands Eindhoven Univ Technol Eindhoven AI Syst Inst NL-5600 MB Eindhoven Netherlands Tech Univ Munich Munich Data Sci Inst MDSI Garching Germany Univ Calif Los Angeles Anderson Sch Management Los Angeles CA 90095 USA

When determining store locations, competing retailers must take customers' store choice into consideration. Customers predominantly select which store to visit based on price, accessibility, and convenience. Incumbent retailers can estimate the weight of these factors (customer attraction parameters) using granular historical data. Their location decision under full information and simultaneous competition translates into an integer programming game. Unlike incumbents, new entrants lack this detailed information;however, they can observe the resulting location structure of incumbents. Assuming the observed location structure is (near-)optimal for all incumbent retailers, a new entrant can use these observations to estimate customer attraction parameters. To facilitate this estimation, we propose an "inverse optimization approach" for integer programming games (IPGs), enabling a new entrant to identify parameters that lead to the observed equilibrium solutions. We solve this "inverse IPG" via decomposition by solving a master problem and a subproblem. The master problem identifies parameter combinations for which the observations represent (approximate) Nash equilibria compared with optimal solutions enumerated in the subproblem. This row-generation approach extends prior methods for inverse integer optimization to competitive settings with (approximate) *** compare the decision-making of new entrants selecting locations based on scenarios, or infor-mation about the underlying distribution of customer attraction parameters (expected values), with new entrants using inversely estimated parameters for their location decisions. New entrants who rely on inversely optimized parameters can improve their profits. On average over a large set of synthetic numerical experiments, we observe improvements of 4-11%. This benefit can be realized with as little as one or two observations, yet additional observations help to increase prediction reliability significantly.(c)

关键词： integer programming Choice estimation Retail location Inverse optimization

来源：评论

学校读者我要写书评

暂无评论

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via integer programming

引用

ACM TRANSACTIONS ON QUANTUM COMPUTING 2025年第2期6卷 1-28页

作者： Wagner, Friedrich Nuesslein, Jonas Liers, Frauke Fraunhofer Inst Integrierte Schaltungen IIS Analyt Erlangen Germany Friedrich Alexander Univ Erlangen Nurnberg Data Sci Erlangen Germany

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.

关键词： integer programming combinatorial optimization quantum computation

来源：评论

学校读者我要写书评

暂无评论

The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via integer programming

引用

INFORMS JOURNAL ON COMPUTING 2023年第5期35卷 1143-1160页

作者： Dragotto, Gabriele Scatamacchia, Rosario Princeton Univ Dept Operat Res & Financial Engn Princeton NJ 08544 USA Politecn Torino Dipartimento Ingn Gestionale & Prod I-10129 Turin Italy

Designing efficient algorithms to compute Nash equilibria poses considerable challenges in algorithmic game theory and optimization. In this work, we employ integer programming techniques to compute Nash equilibria in integer programming games, a class of simultaneous and noncooperative games in which each player solves a parameterized integer program. We introduce zero regrets, a general and efficient cutting-plane algorithm to compute, enumerate, and select Nash equilibria. Our framework leverages the concept of equilibrium inequality, an inequality valid for any Nash equilibrium, and the associated equilibrium separation oracle. We evaluate our algorithmic framework on a wide range of practical and methodological problems from the literature, providing a solid benchmark against the existing approaches.

关键词： integer programming games algorithmic game theory Nash equilibrium mathematical programming games integer programming

来源：评论

学校读者我要写书评

暂无评论

Parallel Dual Dynamic integer programming for Large-Scale Hydrothermal Unit-Commitment

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2023年第3期38卷 2926-2938页

作者： Colonetti, Bruno Finardi, Erlon Brito, Samuel Zavala, Victor Univ Fed Santa Catarina Dept Elect & Elect Engn LabPlan BR-88040900 Florianopolis SC Brazil INESC P&D Brasil BR-81105530 Santos SP Brazil Univ Fed Ouro Preto Dept Comp & Syst BR-35931008 Ouro Preto Brazil Univ Wisconsin Dept Chem & Biol Engn Madison WI 53706 USA

Unit commitment has been at the center of power system operations for over 50 years. Yet, this problem cannot be considered solved due to its size and complexity. Today, operators rely on off-the-shelf optimization solvers to tackle it, and often resort to simplifications to make the problem tractable and solvable in reasonable times. Nonetheless, despite the simplifications and advancements in commercial optimization solvers, solving the unit commitment in a timely manner is still a challenge. In this work, we propose a parallel dual dynamic integer programming approach for solving this problem. Different from what can be currently found in the literature, our parallel approach is applied to a deterministic problem and thus requires induced parallelization. Our strategy is assessed on 20 cases of a hydrothermal system with over 7,000 buses and it is able to solve all instances to a 0.1% gap in less than two hours with speed-ups up to 9.2 compared to a sequential strategy. We also apply our strategy to a purely thermal, large-scale academic system with 9,241 buses, 16,049 transmission lines and 1,445 generating units, for which our strategy returns a 0.1% solution in less than 30 min.

关键词： Optimization Dynamic programming integer programming Heuristic algorithms Thermal loading Trajectory Stochastic processes Dual dynamic programming hydrothermal unit commitment integer programming parallelization

来源：评论

学校读者我要写书评

暂无评论

A space-time-energy flow-based integer programming model to design and operate a regional shared automated electric vehicle (SAEV) system and corresponding charging network

引用

TRANSPORTATION RESEARCH PART C-EMERGING TECHNOLOGIES 2023年第1期147卷

作者： Santos, Goncalo Goncalves Duarte Birolini, Sebastian Correia, Goncalo Homem de Almeida Univ Coimbra Dept Civil Engn CITTA Rua Luis Reis Santos P-3030788 Coimbra Portugal Univ Bergamo Dept Management Informat & Prod Engn I-24044 Dalmine BG Italy Delft Univ Technol Dept Transport & Planning Stevinweg 1 NL-2628 CN Delft Netherlands

Shared automated vehicles are expected to be part of the supply of transportation systems in the future. Parallel to this evolution, there is the rapid penetration of battery electric vehicles (BEVs). The limitations in battery capacity and charging speed of BEVs can influence the planning and operation of shared automated electric vehicle (SAEV) systems. The design of such systems needs to include these limitations so that their viability is properly estimated. In this paper, we develop a space-time-energy flow-based integer programming (IP) model in support of the strategic design of a regional SAEV system. The proposed approach optimizes the fleet (size and compo-sition) and charging facilities (number and location), while explicitly accounting for vehicle operations in aggregated terms (including movements with users, relocations, and charging times). The model is used to assess the impact of vehicle range and different types of chargers in the optimal design of an interurban SAEV transport system in the center of Portugal. Results show a reduction in profit as the vehicle range increases. In regards to energy, it is observed that the adoption of long-range vehicles reduces the energy spent in relocations, and increases the amount of energy charged at a lower price. Additionally, it is found that a system with long-range vehicles does not take advantage of having fast chargers. Concerning the chargers' optimal location, systems using short-range vehicles have more chargers close to the main commuter trips attracting cities, while systems with long-range vehicles have the chargers nearby the homes of users.

关键词： integer programming Flow -based model Shared automated electric vehicles Electric charging Mathematical optimization

来源：评论

学校读者我要写书评

暂无评论

Novel integer programming models for the stable kidney exchange problem

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第3期307卷 1391-1407页

作者： Klimentova, Xenia Biro, Peter Viana, Ana Costa, Virginia Pedroso, Joao Pedro Univ Porto INESC TEC Campus Fac Engn Rua Dr Roberto Frias P-4200465 Porto Portugal CERS Inst Econ Toth Kalman U 4 H-1097 Budapest Hungary Corvinus Univ Budapest Fovam Ter 8 H-1093 Budapest Hungary Polytech Porto Sch Engn Rua Dr Antonio Bernardino de Almeida 431 P-4249015 Porto Portugal Univ Porto Fac Sci Rua Campo Alegre P-4169007 Porto Portugal

Kidney exchange programs (KEPs) represent an additional possibility of transplant for patients suffering from end-stage kidney disease. If a patient has a willing living donor with whom the patient is not compatible, the pair recipient-donor can join a pool of incompatible pairs and, if compatibility between recipient and donor in two or more pairs exists, organs can be exchanged between them. The problem can be modelled as an integer program that in general aims at finding the pairs that should be selected for transplant such that maximum number of transplants is performed. In this paper, we consider that for each recipient there may exist a preference order over the organs that he/she can receive, since a recipient may be compatible with several donors but the level of compatibility with the recipient might vary for different donors. Under this setting, the aim is to find the maximum cardinality stable exchange, a solution where no blocking cycle exists, i.e., there is no cycle such that all recipients prefer the donor in that cycle rather than that in the exchange. For this purpose we propose four novel integer programming models based on the well-known edge and cycle formulations, and also on the position-indexed formulation. These formulations are adjusted for both finding stable and strongly stable exchanges under strict preferences and for the case when ties in preferences may exist. Further-more, we study a situation when the stability requirement can be relaxed by addressing the trade-off between maximum cardinality versus number of blocking cycles allowed in a solution. The effectiveness of the proposed models is assessed through extensive computational experiments on a wide set of in-stances. Results show that the cycle-edge and position-indexed formulations outperform the other two formulations. Another important practical outcome is that targeting strongly stable solutions has a much higher negative impact on the number of transplants (with an average r

关键词： OR In health services Stable exchange Kidney exchange programs integer programming k-way exchange

来源：评论

学校读者我要写书评

暂无评论

Constructing extremal triangle-free graphs using integer programming

引用

DISCRETE OPTIMIZATION 2023年第1期50卷

作者： Banak, Ali Erdem Ekim, Tinaz Taskin, Z. Caner Bogazici Univ Dept Ind Engn Istanbul Turkiye

The maximum number of edges in a graph with matching number m and maximum degree d has been determined in [1] and [2], where some extremal graphs have also been provided. Then, a new question has emerged: how the maximum edge count is affected by forbidding some subgraphs occurring in these extremal graphs? In [3], the problem is solved in triangle-free graphs for d >= m, and for dinteger programming formulation for constructing extremal graphs. Since our formulation is highly symmetric, we use our own implementation of Orbital Branching to reduce symmetry. We also implement our integer programming formulation so that the feasible region is restricted iteratively. Using a combination of the two approaches, we expand the solution into d <= 10 instead of d <= 6 for m>d. Our results endorse the formula for the number of edges in all extremal triangle-free graphs conjectured in Ahanjidehet al. (2022).

关键词： Extremal graphs Factor-critical integer programming Orbital branching

来源：评论

学校读者我要写书评

暂无评论

Network-based integer programming models for flexible process planning

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2023年第9期61卷 3087-3101页

作者： Luo, Kaiping Sun, Jianfei Guo, Liuwei Beihang Univ Sch Econ & Management Beijing Peoples R China Beihang Univ Minist Educ Key Lab Complex Syst Anal Management & Decis Beijing Peoples R China Beihang Univ Sch Mech Engn & Automat Beijing 100191 Peoples R China

Flexible process planning (FPP) involves selecting and sequencing the requisite operations according to technological requirements, and meanwhile allocating a right machine, a right tool and a right access direction to each selected operation by a given criterion. In this article, the FPP problem is exactly and concisely formulated as linear integer programming models based on the topology of the AND/OR-network under two criteria: production cost minimisation and completion time minimisation. Distinctively, more flexible manufacturing elements and process plan evaluation criteria are considered;more complicated tool and access direction changeover identifications are linearly expressed without the big-M parameter. Compared with the latest mathematical programming models for process planning, the proposed models have lower complexity and better performance. The results from numerous comparative experiments indicate that (i) the number of decision variables of the proposed models reduces approximately by 68% and the number of constraints of the proposed models dramatically reduces by 99%;(ii) within the same running time, the proposed models can exactly solve more benchmark cases than the latest models;and (iii) the solutions obtained by the proposed models are also better than the best ones founded by some state-of-the-art meta-heuristic algorithms.

关键词： Flexible manufacturing systems computer-aided manufacturing flexible process planning combinatorial optimisation integer programming

来源：评论

学校读者我要写书评

暂无评论

On the optimality of pseudo-polynomial algorithms for integer programming

引用

MATHEMATICAL programming 2023年第1期198卷 561-593页

作者： Fomin, Fedor, V Panolan, Fahad Ramanujan, M. S. Saurabh, Saket Univ Bergen Dept Informat Bergen Norway IIT Hyderabad Dept Comp Sci & Engn Hyderabad India Univ Warwick Coventry W Midlands England HBNI Inst Math Sci Chennai Tamil Nadu India

In the classic integer programming Feasibility (IPF) problem, the objective is to decide whether, for a given m x n matrix A and an m-vector b = (b(1) ..... b(m) ), there is a non-negative integer n-vector x such that Ax = b. Solving (IPF) is an important step in numerous algorithms and it is important to obtain an understanding of the precise complexity of this problem as a function of natural parameters of the input. The classic pseudo-polynomial time algorithm of Papadimitriou [J. ACM 1981] for instances of (IPF) with a constant number of constraints was only recently improved upon by Eisenbrand and Weismantel [SODA 2018] and Jansen and Rohwedder [ITCS 2019]. Jansen and Rohwedder designed an algorithm for (IPF) with running time O(m Delta)(m) log(Delta) log (Delta + parallel to b parallel to(infinity)) + O(mn). Here, Delta is an upper bound on the absolute values of the entries of A. We continue this line of work and show that under the Exponential Time Hypothesis (ETH), the algorithm of Jansen and Rohwedder is nearly optimal, by proving a lower bound of n(O(m/log m)) . parallel to b parallel to(O(m))(infinity). We also prove that assuming ETH, (IPF) cannot be solved in time f (m) . (n . parallel to b parallel to(infinity))(O(m/log m)) for any computable function f. This motivates us to pick up the line of research initiated by Cunningham and Geelen [IPCO 2007] who studied the complexity of solving (IPF) with non-negative matrices in which the number of constraints may be unbounded, but the branch-width of the column-matroid corresponding to the constraint matrix is a constant. We prove a lower bound on the complexity of solving (IPF) for such instances and obtain optimal results with respect to a closely related parameter, path-width. Specifically, we prove matching upper and lower bounds for (IPF) when the path-width of the corresponding column-matroid is a constant.

关键词： integer programming Algorithms and data structures

来源：评论

学校读者我要写书评

暂无评论

Aircraft route recovery based on distributed integer programming method

引用

MATHEMATICAL BIOSCIENCES AND ENGINEERING 2023年第7期20卷 12802-12819页

作者： Yang, Luyao Wang, Zhikang Yu, Haochen Jiang, Baoping Wu, Zhengtian Suzhou Univ Sci & Technol Sch Elect & Informat Engn Suzhou Peoples R China

In order to further promote the application and development of unmanned aviation in the manned field, and reduce the difficulty that airlines cannot avoid due to unexpected factors such as bad weather, aircraft failure, and so on, the problem of restoring aircraft routes has been studied. To reduce the economic losses caused by flight interruption, this paper divides the repair problem of aircraft operation plans into two sub problems, namely, the generation of flight routes and the reallocation of aircraft. Firstly, the existing fixed-point iteration method proposed by Dang is used to solve the feasible route generation model based on integer programming. To calculate quickly and efficiently, a segmentation method that divides the solution space into mutually independent segments is proposed as the premise of distributed computing. The feasible route is then allocated to the available aircraft to repair the flight plan. The experimental results of two examples of aircraft fault grounding and airport closure show that the method proposed in this paper is effective for aircraft route restoration.

关键词： flight interruption fixed-point iteration integer programming distributed computing

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：