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

Improved integral simplex using decomposition for the set partitioning problem

EURO JOURNAL ON COMPUTATIONAL OPTIMIZATION 2018年第2期6卷 185-206页

作者： Zaghrouti, Abdelouahab El Hallaoui, Issmail Soumis, Francois Polytech Montreal Dept Math & Genie Ind CP 6079 Montreal PQ H3C 3A7 Canada Gerad CP 6079 Montreal PQ H3C 3A7 Canada

Integral simplex using decomposition (ISUD) is a method that efficiently solves set partitioning problems. It is an iterative method that starts from a known integer solution and moves through a sequence of integer solutions, decreasing the cost at each iteration. At each iteration, the method decomposes the original problem into a reduced problem (RP) and a complementary problem (CP). Given an integer solution to RP (that is also solution to the original problem), CP finds a descent direction having the minimum ratio between its cost and the number of its positive variables. We loop on until an optimal or near-optimal solution to the original problem is reached. In this paper, we introduce a modified model for CP. The new model finds a descent direction that minimizes the ratio between the cost of the direction and an overestimation of the number of variables taking one in the next solution. The new CP presents higher chances of finding improved integer solutions without branching. We present results for the same large instances (with up to 570,000 columns) as the ones previously used to test ISUD. For all the instances, optimality is always reached with a speedup factor of at least five.

关键词： Primal algorithms set partitioning problem Integral simplex

来源：评论

学校读者我要写书评

暂无评论

A heuristic scheme for multivariate set partitioning problems with application to classifying heterogeneous populations for multiple binary attributes

引用

IISE TRANSACTIONS 2022年第6期54卷 537-549页

作者： El-Amine, Hadi Aprahamian, Hrayer George Mason Univ Dept Syst Engn & Operat Res Fairfax VA 22030 USA Texas A&M Univ Dept Ind & Syst Engn College Stn TX USA

We provide a novel heuristic approach to solve a class of multivariate set partitioning problems in which each item is characterized by three attribute values. The scheme first identifies a series of orderings of the items and then solves a corresponding sequence of shortest path problems. We provide theoretical findings on the structure of an optimal solution that motivate the design of the proposed heuristic scheme. The proposed algorithm runs in polynomial-time and is independent of the number of groups in the partition, making it more efficient than existing algorithms. To measure the performance of our solutions, we construct bounds for special instances which allow us to provide optimality gaps. We conduct an extensive numerical experiment in which we solve a large number of problem instances and show that our proposed approach converges to the global optimal solution in the vast majority of cases and in the case it does not, it yields very low optimality gaps. We demonstrate our findings with an application in the context of classifying a large heterogeneous population as positive or negative for multiple binary attributes as efficiently as possible. We conduct a case study on the screening of three of the most prevalent sexually transmitted diseases in the United States. The resulting solutions are shown to be within 2.6% of optimality and lead to a 26% cost saving over current screening practices.

关键词： set partitioning problem combinatorial optimization polynomial-time algorithm constrained shortest path group testing

来源：评论

学校读者我要写书评

暂无评论

Integral Simplex Using Decomposition for the set partitioning problem

引用

OPERATIONS RESEARCH 2014年第2期62卷 435-449页

作者： Zaghrouti, Abdelouahab Soumis, Francois El Hallaoui, Issmail Gerad Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada Polytech Montreal Montreal PQ H3C 3A7 Canada

Since the 1970s, several authors have studied the structure of the set partitioning polytope and proposed adaptations of the simplex algorithm that find an optimal solution via a sequence of basic integer solutions. Balas and Padberg in 1972 proved the existence of such a sequence with nonincreasing costs, but degeneracy makes it difficult to find the terms of the sequence. This paper uses ideas from the improved primal simplex to deal efficiently with degeneracy and find subsequent terms in the sequence. When there is no entering variable that leads to a better integer solution, the algorithm referred to as the integral simplex using decomposition algorithm uses a subproblem to find a group of variables to enter into the basis in order to obtain such a solution. We improve the Balas and Padberg results by introducing a constructive method that finds this sequence by only using normal pivots on positive coefficients. We present results for large-scale problems (with up to 500,000 variables) for which optimal integer solutions are often obtained without any branching.

关键词： integral simplex set partitioning problem decomposition

来源：评论

学校读者我要写书评

暂无评论

Optimal unlabeled set partitioning with application to risk-based quarantine policies

引用

IISE TRANSACTIONS 2024年第2期56卷 143-155页

作者： Lin, Jiayi Aprahamian, Hrayer El-Amine, Hadi Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA George Mason Univ Dept Syst Engn & Operat Res Fairfax VA USA

We consider the problem of partitioning a set of items into unlabeled subsets so as to optimize an additive objective, i.e., the objective function value of a partition is equal to the sum of the contribution of each subset. Under an arbitrary objective function, this family of problems is known to be an NP-complete combinatorial optimization problem. We study this problem under a broad family of objective functions characterized by elementary symmetric polynomials, which are "building blocks" to symmetric functions. By analyzing a continuous relaxation of the problem, we identify conditions that enable the use of a reformulation technique in which the set partitioning problem is cast as a more tractable network flow problem solvable in polynomial-time. We show that a number of results from the literature arise as special cases of our proposed framework, highlighting its generality. We demonstrate the usefulness of the developed methodology through a novel and timely application of quarantining heterogeneous populations in an optimal manner. Our case study on real COVID-19 data reveals significant benefits over conventional measures in terms of both spread mitigation and economic impact, underscoring the importance of data-driven policies.

关键词： Combinatorial optimization set partitioning problem network flow reformulation risk-based quarantine COVID-19

来源：评论

学校读者我要写书评

暂无评论

Optimal clustering of frequency data with application to disease risk categorization

引用

IISE TRANSACTIONS 2022年第8期54卷 728-740页

作者： Aprahamian, Hrayer El-Amine, Hadi Texas A&M Univ Dept Ind & Syst Engn College Stn TX 77843 USA George Mason Univ Dept Syst Engn & Operat Res Fairfax VA 22030 USA

We provide a clustering procedure for a special type of dataset, known as frequency data, which counts the frequency of a certain binary outcome. An interpretation of the data as a discrete distribution enables us to extract statistical information, which we embed within an optimization-based framework. Our analysis of the resulting combinatorial optimization problem allows us to reformulate it as a more tractable network flow problem. This, in turn, enables the construction of exact algorithms that converge to the optimal solution in quadratic time. In addition, to be able to handle large-scale datasets, we provide two hierarchical heuristic algorithms that run in linearithmic time. Our moment-based method results in clustering solutions that are shown to perform well for a family of applications. We illustrate the benefits of our findings through a case study on HIV risk categorization within the context of large-scale screening through group testing. Our results on CDC data show that the proposed clustering framework consistently outperforms other popular clustering methods.

关键词： Cluster analysis set partitioning problem constrained shortest path hierarchical clustering disease risk categorization

来源：评论

学校读者我要写书评

暂无评论

A scalable learning approach for the capacitated vehicle routing problem

引用

COMPUTERS & OPERATIONS RESEARCH 2024年 171卷

作者： Fitzpatrick, James Ajwani, Deepak Carroll, Paula Univ Coll Dublin Sch Business Dublin D04 V1W8 Ireland Univ Coll Dublin Sch Comp Sci Dublin D04 V1W8 Ireland

Designing efficient heuristics for the different variants of vehicle routing problems and customising the heuristics to various input distributions is a time-consuming and expensive task. In recent years, end-to-end machine learning techniques have been developed because they are easy to modify for different problem variants, thereby saving on the design time to develop new efficient heuristics. These learning techniques, such as the transformer-based constructive methods, struggle to provide high quality solutions on problem instances with hundreds to thousands of customers in a reasonable time. Furthermore, many of the end-to-end heuristics also do not guarantee that solutions obey fleet-size constraints. We propose a heuristic for solving large capacitated vehicle routing problem (CVRP) that carefully integrates a machine learning heuristic with Integer Linear Programming techniques. To address the issue of solutions with poor objective function values generated by end-to-end machine learning approaches on larger instances, we dynamically partition the CVRP problem instance into smaller sub-problems and apply a machine heuristic on the smaller sub-problems. This allows the machine learning heuristic to always operate on smaller problems similar in size to those for which it was trained. The machine learning heuristic generates many solutions for each sub-problem which are then combined using a set partitioning approach based on a ILP formulation. The set partitioning ILP also guarantees that solutions obey fleet-size constraints. We evaluate the performance of our heuristic on a difficult set of benchmark instances with hundreds to thousands of nodes, achieving small gaps (less than 3% on average) with respect to best known solutions, significantly improving upon the solution quality of the existing learning heuristics. Furthermore, we demonstrate that our results generalise well to other vehicle routing problems, such as green vehicle routing problem.

关键词： Capacitated vehicle routing problem Green vehicle routing problem Reinforcement learning set partitioning problem

来源：评论

学校读者我要写书评

暂无评论

A Compressive Sensing CMOS Image Sensor With Partition Sampling Technique

引用

IEEE TRANSACTIONS ON INDUSTRIAL ELECTRONICS 2021年第9期68卷 8874-8884页

作者： Lee, Hyunkeun Kim, Woo-Tae Kim, Jinho Chu, Myonglae Lee, Byung-Geun Korea Inst Ind Technol Innovat Smart Mfg R&D Dept Cheonan 31056 South Korea Gwangju Inst Sci & Technol Sch Elect Engn & Comp Sci Gwangju 61005 South Korea Vieworks Anyang 14055 South Korea Samsung Elect Co Ltd Semicond R&D Ctr Suwon 17113 South Korea

A CMOS image sensor (CIS) that performs compressive sensing (CS) image encoding without compromising the operating speed and hardware complexity is presented in this article. The conversion rate and the frame rate of the sensor are increased by using a high-order sigma-delta (Sigma Delta) analog-to-digital converter (ADC) to obtain linear measurements of selected pixel values for CS encoding. Image distortion caused by the nonconstant weight function of high-order Sigma Delta ADCs is eliminated by using the proposed sampling technique. The sampling technique makes the effective weights of the inputs to the ADC equal by applying a solution for the set partition problem. In addition, unlike the existing block-based CS encoding scheme that requires complicated analog multiplexers, the proposed column-based CS encoding scheme can be implemented in a hardware-efficient column-parallel fashion, as in conventional CISs. The CIS is fabricated in a 0.11-mu m 1P4M CIS process, and the sampling technique and encoding scheme are successfully demonstrated. It achieves a readout noise of 2.63e(rms)(-) and a dynamic range of 67.96 dB with a power consumption of 56.38 mW. The resulting figure of merit is 0.375 e(-).nJ, which is the lowest among those of recently reported state-of-the-art CS-CISs.

关键词： Analog-to-digital converter (ADC) CMOS image sensor (CIS) compressive/compressed sensing high-order sigma-delta (Sigma Delta) modulator image processing set partitioning problem

来源：评论

学校读者我要写书评

暂无评论

The two-echelon vehicle routing problem with time windows, intermediate facilities, and occasional drivers

引用

EXPERT SYSTEMS WITH APPLICATIONS 2023年第1期234卷

作者： Yu, Vincent F. Jodiawan, Panca Schrotenboer, Albert H. Hou, Ming-Lu Natl Taiwan Univ Sci & Technol Dept Ind Management Taipei 10607 Taiwan Natl Taiwan Univ Sci & Technol Ctr Cyber Phys Syst Innovat Taipei 10607 Taiwan Eindhoven Univ Technol Sch Ind Engn Operat Planning Accounting & Control Grp NL-5600 MB Eindhoven Netherlands

This research introduces a new variant of two-echelon vehicle routing problems inspired from the city logistics. The problem considers a two-echelon freight distribution network where customers are located at the second echelon while their goods are transported from the source in the first echelon to intermediate facilities, i.e., satellites, parcel lockers, and transshipment nodes. Customers can receive their goods that can be delivered by either city freighters or occasional drivers at their homes or are assigned to perform self-pickup at selected parcel lockers. The objective is to minimize total operational cost. We name the problem the Two-Echelon Vehicle Routing problem with Time Windows, Intermediate Facilities, and Occasional Drivers (2E-VRPTW-IF-OD) and cast the problem as a mixed integer linear programming model and devise a hybrid adaptive large neighborhood search (HALNS) using, amongst others, set-partitioning like neighborhoods to provide solutions for newly generated 2E-VRPTW-IF-OD instances. Extensive experiments show high-quality performance of HALNS for solving two special cases of 2E-VRPTW-IF-OD. We further improve 24 best-known solutions for one of the special cases. Finally, we also derive various interesting managerial insights.

关键词： Parcel lockers Occasional drivers Two-echelon vehicle routing problem Adaptive large neighborhood search set partitioning problem

来源：评论

学校读者我要写书评

暂无评论

Modelling transfer line design problem via a set partitioning problem

引用

OPTIMIZATION LETTERS 2012年第5期6卷 915-926页

作者： Borisovsky, Pavel Dolgui, Alexandre Kovalev, Sergey Ecole Natl Super Mines Ind Engn & Comp Sci Ctr G2I F-42023 St Etienne 2 France Omsk FM Dostoevsky State Univ Inst Math & Informat Technol Omsk 644077 Russia

The design of a transfer line is considered. This line is used for a repetitive execution of a given set of operations to produce identical items. The line is composed of a sequence of workstations equipped with processing modules (blocks). Each block performs specific operations. The machined items move along the workstations in the same direction. There is the same cost associated with each workstation and different costs associated with diverse blocks. The problem is to determine the number of workstations, select a set of blocks and assign the selected blocks to the workstations so that, for each item, each operation is performed exactly once with total line cost to be minimized. The specificity of the problem is that all operations of the same workstation are performed in parallel. There are inclusion, exclusion, and precedence relations that restrict the assignment of blocks and operations to the same workstation and constrain the processing order of the operations on the transfer line. We suggest a reduction of this transfer line design problem to a simple set partitioning problem. This reduction is based on the concept of a locally feasible workstation.

关键词： Transfer line design Line balancing Parallel operations set partitioning problem

来源：评论

学校读者我要写书评

暂无评论

Optimal unlabeled set partitioning with application to risk-based quarantine policies

A I I E Transactions

引用

A I I E Transactions 2024年第2期56卷

作者： Jiayi Lin Hrayer Aprahamian Hadi El-Amine a Department of Industrial and Systems Engineering Texas A&M University College Station TX USA b Department of Systems Engineering and Operations Research George Mason University Fairfax VA USA

We consider the problem of partitioning a set of items into unlabeled subsets so as to optimize an additive objective, i.e., the objective function value of a partition is equal to the sum of the contribution of each subset. Under an arbitrary objective function, this family of problems is known to be anNP-complete combinatorial optimization problem. We study this problem under a broad family of objective functions characterized by elementary symmetric polynomials, which are “building blocks” to symmetric functions. By analyzing a continuous relaxation of the problem, we identify conditions that enable the use of a reformulation technique in which the set partitioning problem is cast as a more tractable network flow problem solvable in polynomial-time. We show that a number of results from the literature arise as special cases of our proposed framework, highlighting its generality. We demonstrate the usefulness of the developed methodology through a novel and timely application of quarantining heterogeneous populations in an optimal manner. Our case study on real COVID-19 data reveals significant benefits over conventional measures in terms of both spread mitigation and economic impact, underscoring the importance of data-driven policies.

关键词： Combinatorial optimization set partitioning problem network flow reformulation risk-based quarantine COVID-19

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：