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

Configuring mixed-integer programming Solvers for Large-Scale Instances

Operations Research Forum 2024年第2期5卷 48页

作者： Kemminer, Robin Lange, Jannick Kempkes, Jens Peter Tierney, Kevin Weiß, Dimitri OPTANO GmbH Technologiepark 18 NRW Paderborn 33100 Germany Decision and Operation Technologies Bielefeld University Universitätsstraße 25 NRW Bielefeld 33615 Germany

Algorithm configuration techniques automatically search for parameters of solvers and algorithms that provide minimal runtime or maximal solution quality on specified instance sets. mixed-integer programming (MIP) solvers pose a particular challenge for algorithm configurators due to the difficulty of finding optimal, or even feasible, solutions on the large-scale problems commonly found in practice. We introduce the OPTANO Algorithm Tuner (OAT) to find configurations for MIP solvers and other optimization algorithms. We present and evaluate several critical components of OAT for solving MIPs in particular and show that OAT can find configurations that significantly improve the solution time of MIPs on two different datasets. © The Author(s) 2024.

关键词： Algorithm configuration Large-scale problem instances mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

Extending the Applicability of the mixed-integer programming Technique in Automatic Differential Cryptanalysis 18th

Extending the Applicability of the Mixed-Integer Programming...

引用

18th International Conference on Information Security (ISC)

作者： Sun, Siwei Hu, Lei Wang, Meiqin Yang, Qianqian Qiao, Kexin Ma, Xiaoshuang Song, Ling Shan, Jinyong Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Chinese Acad Sci Data Assurance & Commun Secur Res Ctr Beijing 100093 Peoples R China Shandong Univ Minist Educ Key Lab Cryptol Technol & Informat Secur Jinan 250100 Peoples R China

ISBN: (纸本)9783319233185;9783319233178

We focus on extending the applicability of the mixed-integer programming (MIP) based method in differential cryptanalysis such that more work can be done automatically. Firstly, we show how to use the MIP-based technique to obtain almost all high probability 2-round iterative related-key differential characteristics of PRIDE (a block cipher proposed in CRYPTO 2014) automatically by treating the g(i)((j)) (.) function with a special kind of modulo addition operations in the key schedule algorithm of PRIDE as an 8 x 8 S-box and partially modelling its differential behavior with linear inequalities. Note that some of the characteristics presented in this paper has not been found before, and all the characteristics we found can be used to attack the full-round PRIDE in the related-key model. Secondly, we show how to construct MIP models whose feasible regions are exactly the sets of all possible differential characteristics of SIMON (a family of lightweight block ciphers designed by the U. S. National Security Agency). With this method, there is no need to filter out invalid characteristics due to the dependent inputs of the AND operations. Finally, we present an MIP-based method which can be used to automatically analyze how the differences at the beginning and end of a differential distinguisher propagate upwards and downward. Note that how the differences at the ends of a differential distinguisher propagate, together with the probability of the differential distinguisher, determine how many outer rounds can be added to the distinguisher, which key bits can be recovered without exhaustive search, and how to identify wrong pairs in the filtering process. We think this work serves to further strengthens the position of the MIP as a promising tool in automatic differential cryptanalysis.

关键词： Automatic cryptanalysis Related-key differential attack mixed-integer programming PRIDE

来源：评论

学校读者我要写书评

暂无评论

Data Mining Approach for Feature Based Parameter Tunning for mixed-integer programming Solvers

Data Mining Approach for Feature Based Parameter Tunning for...

引用

International Conference on Computational Science (ICCS)

作者： Vilas Boas, Matheus G. Santos, Haroldo G. Martins, Rafael de S. O. Merschmann, Luiz H. C. Univ Fed Ouro Preto Dept Comp Ouro Preto Brazil Univ Fed Ouro Preto Dept Informat Syst & Comp Joao Monlevade Brazil Univ Fed Lavras Dept Comp Sci Lavras Brazil

integer programming (IP) is the most successful technique for solving hard combinatorial optimization problems. Modern IP solvers are very complex programs composed of many different procedures whose execution is embedded in the generic Branch & Bound framework. The activation of these procedures as well the definition of exploration strategies for the search tree can be done by setting different parameters. Since the success of these procedures and strategies in improving the performance of IP solvers varies widely depending on the problem being solved, the usual approach for discovering a good set of parameters considering average results is not ideal. In this work we propose a comprehensive approach for the automatic tuning of integer programming solvers where the characteristics of instances are considered. Computational experiments in a diverse set of 308 benchmark instances using the open source COIN-OR CBC solver were performed with different parameter sets and the results were processed by data mining algorithms. The results were encouraging: when trained with a portion of the database the algorithms were able to predict better parameters for the remaining instances in 84% of the cases. The selection of a single best parameter setting would provide an improvement in only 56% of instances, showing that great improvements can be obtained with our approach. (C) 2017 The Authors. Published by Elsevier B.V.

关键词： feature based parameter tunning mixed-integer programming data mining regression algorithms coin-or branch and cut

来源：评论

学校读者我要写书评

暂无评论

Piecewise regression via mixed-integer programming for MPC 6

Piecewise regression via mixed-integer programming for MPC

引用

6th Annual Learning for Dynamics and Control Conference

作者： Teichrib, Dieter Darup, Moritz Schulze TU Dortmund Univ Control & Cyberphys Syst Grp Dortmund Germany

Piecewise regression is a versatile approach used in various disciplines to approximate complex functions from limited, potentially noisy data points. In control, piecewise regression is, e.g., used to approximate the optimal control law of model predictive control (MPC), the optimal value function, or unknown system dynamics. Neural networks are a common choice to solve the piecewise regression problem. However, due to their nonlinear structure, training is often based on gradient-based methods, which may fail to find a global optimum or even a solution that leads to a small approximation error. To overcome this problem and to find a global optimal solution, methods based on mixed-integer programming (MIP) can be used. However, the known MIP-based methods are either limited to a special class of functions, e.g., convex piecewise affine functions, or they lead to complex approximations in terms of the number of regions of the piecewise defined function. Both complicate a usage in the framework of control. We propose a new MIP-based method that is not restricted to a particular class of piecewise defined functions and leads to functions that are fast to evaluate and can be used within an optimization problem, making them well suited for use in control.

关键词： piecewise regression mixed-integer programming model predictive control neural networks

来源：评论

学校读者我要写书评

暂无评论

Quasi-anytime Algorithm for Resolution of Aircraft Trajectory Conflict Using mixed-integer programming 15th

Quasi-anytime Algorithm for Resolution of Aircraft Trajector...

引用

15th APCA International Conference on Automatic Control and Soft Computing (CONTROLO)

作者： da Costa, Thiago Rodrigues Magalhaes Afonso, Rubens Junqueira de Oliveira Moreira, Fernando Jose Inst Tecnol Aeronaut Sao Jose Dos Campos Brazil EMBRAER SA Sao Jose Dos Campos Brazil

ISBN: (纸本)9783031100475;9783031100468

Optimal control formulations enjoy considerable attention nowadays to solve conflicts between aircraft. Mitigating deviation from the original planned routes and minimizing the changes in velocity and acceleration play an important role in deciding which maneuver to employ for deconfliction, usually encoded in a suitable cost function. mixed-integer linear programming (MILP) provides a framework to model and solve the trajectory planning problems (TPP) in a computationally efficient manner. The solution of TPP is nonetheless still challenging for en-route applications in terms of computation time. More recent formulations endowed the MILP encoding with the so-called supervisory constraints, that can be selected by a human expert to influence the outcome of the optimization, enforcing desired behaviors on the solutions. This customization of the conflict resolution entails an even greater computing effort. Inspired by the move blocking concept present in model predictive control applications where the computing time is critical, we propose a reduction in the number of decision variables in the MILP by holding them constant during each block of time samples in order to assure that the MILP will have a feasible solution within the available time. Simulation scenarios were used to validate the proposal and confirm the expected time decrease. In turn, the success of this approach enabled us to propose a quasi-anytime algorithm for deconfliction, starting with larger blocks to obtain a coarse but conflict-free trajectory in short time, and then progressively decreasing the block size to refine the solutions, up until the minimal block size is reached or we run out of time to output a solution. Simulations were used to illustrate the application of the algorithm.

关键词： Quasi-anytime algorithm Trajectory conflict Resolution mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

Optimization of timed automata models using mixed-integer programming

引用

1st International Workshop on Formal Modeling and Analysis of Timed Systems (FORMATS 2003)

作者： Panek, S Stursberg, O Engell, S Univ Dortmund BCI AST Proc Control Lab D-44221 Dortmund Germany

ISBN: (纸本)3540216715

Research on optimization of timed systems, as e.g. for computing optimal schedules of manufacturing processes, has lead to approaches that mainly fall into the following two categories: On one side, mixed integer programming (MIP) techniques have been developed to successfully solve scheduling problems of moderate to medium size. On the other side, reachability algorithms extended by the evaluation of performance criteria have been employed to optimize the behavior of systems modeled as timed automata (TA). While some successful applications to real-world examples have been reported for both approaches, industrial scale problems clearly call for more powerful techniques and tools. The work presented in this paper aims at combining the two types of approaches: The intention is to take advantage of the simplicity of modeling with timed automata (including modularity and synchronization), but also of the relaxation techniques and heuristics that axe known from MIP As a first step in this direction, the paper describes a translation procedure that automatically generates MIP representations of optimization problems formulated initially for TA. As a possible use of this translation, the paper suggests an iterative solution procedure, that combines a tree search for TA with the MIP solution of subproblems. The key idea is to use the relaxations in the MIP step to guide the tree search for TA in a branch-and-bound fashion.

关键词： branch-and-bound techniques discrete optimization mixed-integer programming scheduling timed automata

来源：评论

学校读者我要写书评

暂无评论

Semi-continuous cuts for mixed-integer programming

引用

10th International integer programming and Combinatorial Optimization Conference

作者： de Farias, IR SUNY Buffalo Dept Ind Engn Buffalo NY 14260 USA

ISBN: (纸本)3540221131

We study the convex hull of the feasible set of the semi-continuous knapsack problem, in which the variables belong to the union of two intervals. Besides being important in its own right, the semi-continuous knapsack problem is a relaxation of general mixed-integer programming. We show how strong inequalities that are valid for the semi-continuous knapsack polyhedron can be derived and used as cuts in a branch-and-cut scheme for mixed-integer programming anal problems with semi-continuous variables. We present computational results that demonstrate the effectiveness of these inequalities, which we call collectively semi-continuous cuts. Our computational experience also shows that dealing with semi-continuous constraints directly in the branch-and-cut algorithm through a specialized branching scheme and semi-continuous cuts is considerably more practical than the "textbook" approach of modeling semi-continuous constraints through the introduction of auxiliary binary variables in the model.

关键词： mixed-integer programming semi-continuous variables disjunctive programming polyhedral combinatorics branch-and-cut

来源：评论

学校读者我要写书评

暂无评论

A mixed-integer programming approach for industrial non-intrusive load monitoring

引用

APPLIED ENERGY 2023年第PartA期330卷

作者： Li, Chuyi Zheng, Kedi Guo, Hongye Chen, Qixin Tsinghua Univ Dept Elect Engn State Key Lab Power Syst Beijing 100084 Peoples R China

With the development of the smart grid, more load data can be collected and utilized to facilitate bidirectional communications between the supply-side and demand-side. More detailed data can achieve better results in applications, but it is not feasible due to sensor placement and data transmission limitations. Non-intrusive load monitoring (NILM) is an exceptionally low-cost solution for providing appliance-level load information of a building without installing extra sensors. While most current studies focus on NILM in residential buildings, the potential benefit of industrial NILM is preferable due to the grander power consumption scale and more professional management. This paper considers the challenges and strengths of industrial NILM, and a mixed-integer programming NILM approach is proposed for flowline industries. This approach separately models equipment with different load features, resulting in better performance in industrial scenarios containing various loads. Temporal dependencies between equipment are exploited by recognizing the statistical regularity of load fluctuation and are introduced as a novel flowline constraint in the model. A pulse width constraint that restricts the state duration of equipment is also introduced to improve performance. Several cases are designed and tested on two public industrial datasets to evaluate the effectiveness and transferability of the model. The classical factorial hidden Markov model (FHMM), a state-of-the-art matrix factorization method, and a deep learning model are used as benchmarks for comparison.

关键词： Non-intrusive load monitoring Industrial flowline Matrix factorization mixed-integer programming

来源：评论

学校读者我要写书评

暂无评论

Optimized Planning Approach for Multiple Tower Cranes and Material Supply Points Using mixed-integer programming

引用

JOURNAL OF CONSTRUCTION ENGINEERING AND MANAGEMENT 2020年第3期146卷

作者： Ji, Yuanshen Leite, Fernanda Univ Texas Austin Construct Engn & Project Management Program Dept Civil Architectural & Environm Engn 301 E Dean Keeton St C1752 Austin TX 78712 USA

It is common to implement multiple tower cranes on building construction projects. The plan for usage of multiple tower cranes should be optimized for better project performance, such as reduced cost or operation time. Optimization of plans for multiple cranes is complex, especially when considering the supply of transported material (e.g., location, quantity, material type), as well as assigning lift tasks among tower cranes that are in range. This study developed a mathematic formulation that can solve this optimization problem using mixed-integer programming. The formulation introduces several binary variables and restricts the domain of the indices of these variables using an additional set of auxiliary variables. The proposed model contributes to the body of knowledge by showing the feasibility of using mixed-integer-programming techniques to solve the optimization problem of multiple tower cranes and their supply systems. The findings also demonstrate that when a multiple tower crane problem is concerned, optimizing each piece of equipment individually could lead to suboptimal solutions. Specifically, the operation time drops by 6.8% and the operation cost decreases by 3.6% in the two-tower crane case study example. The proposed model can also assist engineers with assessing a large number of alternative plans, which are heavily needed in preconstruction planning, where site layout is preliminary.

关键词： Optimization mixed-integer programming Tower crane plan Branch-and-cut (CBC)

来源：评论

学校读者我要写书评

暂无评论

A mixed-integer programming Model for Assessing Energy-Saving Investments in Domestic Buildings under Uncertainty

引用

ENERGIES 2018年第4期11卷 989页

作者： Kontogiorgos, Panagiotis Chrysanthopoulos, Nikolaos Papavassilopoulos, George P. Natl Tech Univ Athens Sch Elect & Comp Engn 9 Iroon Polytexneiou Str Zografos 15773 Greece

A decision support tool has been developed to evaluate energy-saving intervention investments for domestic buildings. Various potential interventions are considered, each affecting energy consumption and savings, as well as the total financial cost of the investment. The decision problem is formulated as a mixed-integer programming problem. The implemented methodologies increase the efficiency and efficacy of the solution algorithms and can be applied to most realistic cases. The tool allows users to customize the problem based on their own preferences and find the optimal combination of investments. Uncertainty complicating the decision process is addressed by using interval analysis;therefore, the robustness of the optimal decision can be evaluated to facilitate the decision-making process. A domestic building in the Mediterranean area is used as a case study to demonstrate the functionality of this tool and to evaluate the impact of the decision-maker's uncertainty on the optimal decision.

关键词： energy efficiency interval analysis mixed-integer programming decision support systems

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：