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

A novel reformulation for the single-sink fixed-charge transportation problem

MATHEMATICAL programming 2023年第1-2期202卷 169-198页

作者： Legault, Robin Cote, Jean-Francois Gendron, Bernard Laval Univ Dept Operat & Decis Syst Quebec City PQ Canada CIRRELT Quebec City PQ Canada Univ Montreal Dept Comp Sci & Operat Res Montreal PQ Canada CIRRELT Montreal PQ Canada

The single-sink fixed-charge transportation problem is known to have many applications in the area of manufacturing and transportation as well as being an important subproblem of the fixed-charge transportation problem. However, even the best algorithms from the literature do not fully leverage the structure of this problem, to the point of being surpassed by modern general-purpose mixed-integer programming solvers for large instances. We introduce a novel reformulation of the problem and study its theoretical properties. This reformulation leads to a range of new upper and lower bounds, dominance relations, linear relaxations, and filtering procedures. The resulting algorithm includes a heuristic phase and an exact phase, the main step of which is to solve a very small number of knapsack subproblems. Computational experiments are presented for existing and new types of instances. These tests indicate that the new algorithm systematically reduces the resolution time of the state-of-the-art exact methods by several orders of magnitude.

关键词： mixed-integer programming Fixed-charge transportation problem Lagrangian relaxation Knapsack problem

来源：评论

学校读者我要写书评

暂无评论

Optimal multivariate decision trees

引用

CONSTRAINTS 2023年第4期28卷 549-577页

作者： Boutilier, Justin Michini, Carla Zhou, Zachary Univ Wisconsin Madison Dept Ind & Syst Engn Madison WI 53706 USA

Recently, mixed-integer programming (MIP) techniques have been applied to learn optimal decision trees. Empirical research has shown that optimal trees typically have better out-of-sample performance than heuristic approaches such as CART. However, the underlying MIP formulations often suffer from weak linear programming (LP) relaxations. Many existing MIP approaches employ big-M constraints to ensure observations are routed throughout the tree in a feasible manner. This paper introduces new MIP formulations for learning optimal decision trees with multivariate branching rules and no assumptions on the feature types. We first propose a strong baseline MIP formulation that still uses big-M constraints, but yields a stronger LP relaxation than its counterparts in the literature. We then introduce a problem-specific class of valid inequalities called shattering inequalities. Each inequality encodes an inclusion-minimal set of points that cannot be shattered by a multivariate split, and in the context of a MIP formulation, the inequalities are sparse, involving at most the number of features plus two variables. We propose a separation procedure that attempts to find a violated inequality given a (possibly fractional) solution to the LP relaxation;in the case where the solution is integer, the separation is exact. Numerical experiments show that our MIP approach outperforms two other MIP formulations in terms of solution time and relative gap, and is able to improve solution time while remaining competitive with regards to out-of-sample accuracy in comparison to a wider range of approaches from the literature.

关键词： Decision trees mixed-integer programming Machine learning

来源：评论

学校读者我要写书评

暂无评论

On the Multistage Shortest Path Problem Under Distributional Uncertainty

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 2023年第1期197卷 277-308页

作者： Ketkov, Sergey S. HSE Univ Lab Algorithms & Technol Networks Anal Rodionova St 136 Nizhnii Novgorod 603093 Russia

In this paper, we consider an ambiguity-averse multistage network game between a user and an attacker. The arc costs are assumed to be random variables that satisfy prescribed first-order moment constraints for some subsets of arcs and individual probability constraints for some particular arcs. The user aims at minimizing its cumulative expected loss by traversing between two fixed nodes in the network, while the attacker's objective is to maximize the user's expected loss by selecting a distribution of arc costs from the family of admissible distributions. In contrast to most of the related studies, both the user and the attacker can dynamically adjust their decisions at particular nodes of the user's path. By observing the user's decisions, the attacker may reveal some additional distributional information associated with the arcs emanated from the current user's position. It is shown that the resulting multistage distributionally robust shortest path problem (DRSPP) admits a linear mixed-integer programming reformulation (MIP). In particular, we distinguish between acyclic and general graphs by introducing different forms of non-anticipativity constraints. Finally, we perform a numerical study, where the quality of adaptive decisions and computational tractability of the proposed MIP reformulation are explored with respect to several classes of synthetic network instances.

关键词： Shortest path problem Distributionally robust optimization Polyhedral uncertainty Piecewise constant decision rules mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

A case-oriented computational study for sustainable fleet planning in a battery closed-loop supply chain network under uncertainty

引用

ENGINEERING COMPUTATIONS 2023年第7/8期40卷 1947-2008页

作者： Subulan, Kemal Baykasoglu, Adil Dokuz Eylul Univ Dept Ind Engn Izmir Turkiye

Purpose - The purpose of this study is to develop a holistic optimization model for an integrated sustainable fleet planning and closed-loop supply chain (CLSC) network design problem under uncertainty. Design/methodology/approach - A novel mixed-integer programming model that is able to consider interactions between vehicle fleet planning and CLSC network design problems is first developed. Uncertainties of the product demand and return fractions of the end-of-life products are handled by a chance-constrained stochastic program. Several Pareto optimal solutions are generated for the conflicting sustainability objectives via compromise and fuzzy goal programming (FGP) approaches. Findings - The proposed model is tested on a real-life lead/acid battery recovery system. By using the proposed model, sustainable fleet plans that provide a smaller fleet size, fewer empty vehicle repositions, minimal CO2 emissions, maximal vehicle safety ratings and minimal injury/illness incidence rate of transport accidents are generated. Furthermore, an environmentally and socially conscious CLSC network with maximal job creation in the less developed regions, minimal lost days resulting from the work's damages during manufacturing/recycling operations and maximal collection/recovery of end-of-life products is also designed. Originality/value - Unlike the classical network design models, vehicle fleet planning decisions such as fleet sizing/composition, fleet assignment, vehicle inventory control, empty repositioning, etc. are also considered while designing a sustainable CLSC network. In addition to sustainability indicators in the network design, sustainability factors in fleet management are also handled. To the best of the authors' knowledge, there is no similar paper in the literature that proposes such a holistic optimization model for integrated sustainable fleet planning and CLSC network design.

关键词： Sustainability Fleet management Closed-loop supply chain network design mixed-integer programming Multi-objective optimization Chance-constrained stochastic programming

来源：评论

学校读者我要写书评

暂无评论

A Branch-and-Repair Method for Three-Dimensional Bin Selection and Packing in E-Commerce

引用

OPERATIONS RESEARCH 2023年第1期71卷 273-288页

作者： Fontaine, Pirmin Minner, Stefan Catholic Univ Eichstatt Ingolstadt Ingolstadt Sch Management D-85049 Ingolstadt Germany Tech Univ Munich Sch Management Munich Germany Tech Univ Munich Munich Data Sci Inst D-80333 Munich Germany

The number of shipped parcels is continuously growing and e-commerce retailers and logistics service providers are seeking to improve logistics, particularly lastmile delivery. Since unused transportation space is a major problem in parcel distribution, one option is to improve the selection of the right parcel size for an order and the optimal packing pattern, which is known as the three-dimensional bin packing problem (3D-BPP). Further, the available portfolio of parcel types significantly influences the unused space. Therefore, we introduce the three-dimensional bin selection problem (3D-BSP) to find a portfolio of parcel types for a large set of orders. To solve the 3D-BPP with rotation of items, we propose an efficient mixed-integer linear programming formulation and symmetry-breaking constraints that are also used in the 3D-BSP for the subproblem. To solve large instances of the latter, we introduce a branch-and-repair method that improves branch-and-check. We show that our decomposition allows to relax the majority of binary decision variables in the master problem and avoids weak combinatorial cuts without further lifting. Further, we use problem-specific acceleration techniques. The numerical results based on a real-world online retailer data set show that our reformulation reduces the run time compared with existing mixed-integer linear programs for 3D-BPPs by 30% on average. For the 3D-BSP, the branchand-repair method reduces the run time by more than two orders of magnitude compared with the mixed-integer programming formulation and can even solve instances with millions of binary decision variables and constraints efficiently. We analyze the trade-off between the costs of variety (depending on the number of parcel types) and costs for unused space. Increasing the number of parcel types reduces the unused space significantly.

关键词： three-dimensional bin packing three-dimensional bin selection decomposition reformulation mixed-integer programming e-commerce

来源：评论

学校读者我要写书评

暂无评论

Multi-piece mould design based on a mixed-integer programming method

引用

INTERNATIONAL JOURNAL OF COMPUTER INTEGRATED MANUFACTURING 2013年第10期26卷 939-954页

作者： Chen, Yong Stoyan, Stephen Univ So Calif Epstein Dept Ind & Syst Engn Los Angeles CA 90089 USA

Multi-piece mould design is a moulding technology that involves three-dimensional spatial construction of two or more mould pieces in a manner similar to assembling/dissembling a three-dimensional puzzle to build production parts. Using such a moulding technology, complex parts with intricate geometries can be made for limited run productions. Compared to traditional two-piece moulds and rapid prototyping, the multi-piece mould approach has many advantages with respect to part complexity and production speed, etc.;however, the technology has challenges in designing the actual multi-piece moulds. Previous methodologies address this problem primarily using heuristics. We present a multi-piece mould design (MPMD) framework that is based on a mixed-integer programming approach. The method constructs the MPMD by minimising the number of mould pieces that is required for a given Computer-Aided Design (CAD) model. The solution strategy for the formulated linear mixed-integer optimisation problem is presented. The algorithmic strategy for solving the resulting mixed-integer programming problem is also provided with examples that illustrate the effectiveness and efficiency of the approach.

关键词： computer-aided mould design multi-piece moulding rapid tooling mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

A Comparison of Three Methods for ISO Pricing

IEEE TRANSACTIONS ON ENERGY MARKETS POLICY AND REGULATION

引用

IEEE TRANSACTIONS ON ENERGY MARKETS POLICY AND REGULATION 2025年第1期3卷 59-71页

作者： Chen, Yonghong O'Neill, Richard Whitman, Peter NREL Golden CO 80401 USA OnLocation Inc Vienna VA 22180 USA

In the presence of non-convex constraints, RTOs/ISOs need to introduce side payments to ensure non-confiscatory pricing. The side payment is not uniform and is non-transparent. To address this concern, Convex Hull Price (CHP) is developed to minimize uplift. However, the side payment defined in the tariff of RTOs/ISOs usually only covers make-whole-payments (MWP), not consistent with the uplift defined in CHP. This paper introduces a unified solution approach that can achieve uniform prices under different market rules. Previous research has shown that by developing a convex hull and convex envelope formulation for individual resources, a CHP model that minimizes uplift can be solved by linear programming (LP) using relaxation of the binary terms of the security constrained unit commitment (SCUC) problem. This paper proves that by adjusting resource upper bounds based on the SCUC solution, the one-pass LP relaxation of the SCUC problem can also be used to derive average incremental price (AIC), eliminating MWP. Case studies using both small systems and the MISO full day ahead models are presented to compare MWP, uplift and generator profit under LMP, CHP and AIC.

关键词： Cogeneration Costs Pricing Generators Real-time systems MISO communication Production Convex hull pricing average incremental cost pricing mixed-integer programming security-constrained unit commitment uplift payment make whole payment

来源：评论

学校读者我要写书评

暂无评论

Distributionally Robust Optimization Approaches for a Stochastic Mobile Facility Fleet Sizing, Routing, and Scheduling Problem

引用

TRANSPORTATION SCIENCE 2023年第1期57卷 197-229页

作者： Shehadeh, Karmel S. Lehigh Univ Dept Ind & Syst Engn Bethlehem PA 18015 USA

We propose two distributionally robust optimization (DRO) models for a mobile facility (MF) fleet-sizing, routing, and scheduling problem (MFRSP) with time-dependent and randomdemand as well as methodologies for solving these models. Specifically, given a set of MFs, a planning horizon, and a service region, our models aim to find the number of MFs to use (i.e., fleet size) within the planning horizon and a route and time schedule for each MF in the fleet. The objective is to minimize the fixed cost of establishing the MF fleet plus a risk measure (expectation or mean conditional value at risk) of the operational cost over all demand distributions defined by an ambiguity set. In the first model, we use an ambiguity set based on the demand's mean, support, and mean absolute deviation. In the second model, we use an ambiguity set that incorporates all distributions within a 1-Wasserstein distance from a reference distribution. To solve the proposed DRO models, we propose a decomposition-based algorithm. In addition, we derive valid lower bound inequalities that efficiently strengthen the master problem in the decomposition algorithm, thus improving convergence. We also derive two families of symmetry-breaking constraints that improve the solvability of the proposed models. Finally, we present extensive computational experiments comparing the operational and computational performance of the proposed models and a stochastic programming model, demonstrating when significant performance improvements could be gained, and derive insights into the MFRSP.

关键词： facility location mobile facility demand uncertainty scheduling and routing mixed-integer programming distributionally robust optimization

来源：评论

学校读者我要写书评

暂无评论

Incorporating Sparse and Quantized Carbohydrates Suggestions in Model Predictive Control for Artificial Pancreas in Type 1 Diabetes

引用

IEEE TRANSACTIONS ON CONTROL SYSTEMS TECHNOLOGY 2023年第2期31卷 570-586页

作者： Pavan, Jacopo Salvagnin, Domenico Facchinetti, Andrea Sparacino, Giovanni Del Favero, Simone Univ Padua Dept Informat Engn I-35131 Padua Italy

People with type 1 diabetes (T1D) face the challenge of administering exogenous insulin to maintain blood glucose (BG) levels in a safe physiological range, so as to avoid (possibly severe) complications. By automatizing insulin infusion, the artificial pancreas (AP) assists patients in this challenge. While insulin can decrease BG, having another input inducing glucose increase could further improve BG control. Here, we develop a model predictive control (MPC) algorithm that, in addition to insulin infusion, also provides suggestions of carbohydrates (CHOs) as a second, glucose-increasing, control input. Since CHO consumption has to be manually actuated, great care is paid in limiting the extra burden that may be caused to patients. By resorting to a mixed logical-dynamical MPC formulation, CHO intake is designed to be sparse in time and quantized. The algorithm is validated on the UVa/Padua T1D simulator, a well-established large-scale model of T1D metabolism, accepted by Food and Drug Administration (FDA). Compared with an insulin-only MPC, the new algorithm ensures increased time spent in the safe physiological range in 75% of patients. The improvement is limited for those already well controlled by the state-of-art strategy but relevant for the others: the 25th percentile of this metric is increased from 74.75% to 79.06% in the population. This is achieved while simultaneously decreasing time spent in hypoglycemia (from 0.5% to 0.12% in median) and with limited manual interventions (2.86 per day in median).

关键词： Insulin Glucose Biochemistry Pancreas Diabetes Control systems Cognition Artificial pancreas (AP) carbohydrates (CHOs) suggestion diabetes mixed-integer programming model predictive control (MPC)

来源：评论

学校读者我要写书评

暂无评论

Security-Constrained Unit Commitment for Electricity Market: Modeling, Solution Methods, and Future Challenges

引用

IEEE TRANSACTIONS ON POWER SYSTEMS 2023年第5期38卷 4668-4681页

作者： Chen, Yonghong Pan, Feng Qiu, Feng Xavier, Alinson S. Zheng, Tongxin Marwali, Muhammad Knueven, Bernard Guan, Yongpei Luh, Peter B. Wu, Lei Yan, Bing Bragin, Mikhail A. Zhong, Haiwang Giacomoni, Anthony Baldick, Ross Gisin, Boris Gu, Qun Philbrick, Russ Li, Fangxing Midcontinent Independent Syst Operator Inc Carmel IN 46032 USA Pacific Northwest Natl Lab Elect Infrastruct Richland WA 99532 USA Argonne Natl Lab Lemont IL 60439 USA ISO New England Holyoke MA 01040 USA NYISO Rensselaer NY 12144 USA Natl Renewable Energy Lab Computat Sci Ctr Golden CO 80401 USA Univ Florida Ind & Syst Engn Gainesville FL 32611 USA Univ Conneticut Comp Engn Storrs CT 06269 USA Stevens Inst Technol Hoboken NJ 07030 USA Rochester Inst Technol Elect & Microelect Engn Rochester NY 14623 USA Univ Connecticut Elect & Comp Engn Storrs CT 06269 USA Tsinghua Univ Elect Engn Beijing 100084 Peoples R China PJM Audubon PA 19403 USA Univ Texas Austin Elect & Comp Engn Austin TX 78712 USA PowerGEM LLC Co Clifton Pk NY 12065 USA Polaris Syst Optimizat Shoreline WA 98177 USA Univ Tennessee EECS Knoxville TN 37996 USA

This paper summarizes the technical activities of the IEEE Task Force on Solving Large Scale Optimization Problems in Electricity Market and Power System Applications. This Task Force was established by the IEEE Technology and Innovation Subcommittee to first review the state-of-the-art of the security-constrained unit commitment (SCUC) business model, its mathematical formulation, and solution techniques in solving electricity market clearing problems. The Task Force then investigated the emerging challenges of future market clearing problems and presented efforts in building benchmark mathematical and business models.

关键词： Combined cycle decomposition distributed energy resource electricity market mixed-integer programming network security analysis relaxation security-constrained unit commitment storage virtual transaction

来源：评论

学校读者我要写书评

暂无评论

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：