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

On the facet pivot simplex method for linear programming II: a linear iteration bound

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Yang, Yaguang US DOC 305 Deer Meadow Lane Rockville20850 United States

The Hirsch Conjecture stated that any d-dimensional polytope with n facets has a diameter at most equal to n − d. This conjecture was disproved by Santos (A counterexample to the Hirsch Conjecture, Annals of Mathematics, 172(1) 383-412, 2012). The implication of Santos' work is that all vertex pivot algorithms cannot solve the linear programming problem in the worst case in n − d vertex pivot iterations. In the first part of this series of papers, we proposed a facet pivot method. In this paper, we show that the proposed facet pivot method can solve the canonical linear programming problem in the worst case in at most n − d facet pivot iterations. This work was inspired by Smale's Problem 9 (Mathematical problems for the next century, In Arnold, V. I.;Atiyah, M.;Lax, P.;Mazur, B. Mathematics: frontiers and perspectives, American Mathematical Society, 271-294, 1999). © 2022, CC BY.

关键词： linear programming

Contract Composition for Dynamical Control Systems: Definition and Verification using linear programming

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Sharf, Miel Besselink, Bart Johansson, Karl Henrik Division of Decision and Control Systems Kth Royal Institute of Technology Digital Futures Stockholm10044 Sweden Bernoulli Institute for Mathematics Computer Science and Artificial Intelligence University of Groningen Groningen9700 AK Netherlands

Designing large-scale control systems to satisfy complex specifications is hard in practice, as most formal methods are limited to systems of modest size. Contract theory has been proposed as a modular alternative to formal methods in control, in which specifications are defined by assumptions on the input to a component and guarantees on its output. However, current contract-based methods for control systems either prescribe guarantees on the state of the system, going against the spirit of contract theory, or can only support rudimentary compositions. In this paper, we present a contract-based modular framework for discrete-time dynamical control systems. We extend the definition of contracts by allowing the assumption on the input at a time k to depend on outputs up to time k -1, which is essential when considering the feedback connection of an unregulated dynamical system and a controller. We also define contract composition for arbitrary interconnection topologies, under the pretence of well-posedness, and prove that this notion supports modular design, analysis and verification. This is done using graph theory methods, and specifically using the notions of topological ordering and backward-reachable nodes. Lastly, we use k-induction to present an algorithm for verifying vertical contracts, which are claims of the form "the conjugation of given component-level contracts is a stronger specification than a given contract on the integrated system". These algorithms are based on linear programming, and scale linearly with the number of components in the interconnected network. A numerical example is provided to demonstrate the scalability of the presented approach, as well as the modularity achieved by using it. Copyright © 2022, The Authors. All rights reserved.

关键词： linear programming

Optimization and Time Management of Weekly Class Schedule with Activity Constraints for College Students using linear programming

学校读者我要写书评

暂无评论

Optimization and Time Management of Weekly Class Schedule wi...

International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM)

作者： Lathaniel Xavier Joseph Ablan Nilo T. Bugtai Robert Kerwin C. Billones Department of Manufacturing Engineering and Management De La Salle University Manila Philippines

College students face a multitude of academic responsibilities over the course of their undergraduate studies. It is important for them to manage their time accordingly to accomplish their necessary academic tasks and preserve their personal growth. This paper aims to optimize the amount of time spent on curricular tasks within a week while accounting for the unit load for the term, lecture duration, personal time duration, and sleep duration of the student using linear programming. The methodology aims to minimize and maximize the designed objective function to acquire the maximum number of academic working hours of students within a 5-day academic week. The constraints of the model are based on survey results from students and the academic policies of the connected university. The model for both optimization cases is processed using MATLAB software equipped with an optimization toolkit. The results of the program presented an optimal solution of 76 and 119 hours for the minimization and maximization cases, respectively. Overall, the former acquired 44 hours while the latter only gained 1 hour for the maximum number of working hours in a week.

关键词： Productivity Schedules linear programming Minimization Mathematical models Software Task analysis

Ingredient Inventory and Revenue Optimization of Restaurant Food Sales using Integer linear programming

学校读者我要写书评

暂无评论

Ingredient Inventory and Revenue Optimization of Restaurant ...

International Conference on Humanoid, Nanotechnology, Information Technology, Communication and Control, Environment and Management (HNICEM)

作者： Jerahmeel K. Coching Adrian Jenssen L. Pe Seth Gabriel D. Yeung Wynnezel Wayne Naoto Akeboshi Robert Kerwin C. Billones Elmer P. Dadios Department of Manufacturing Engineering and Management Intelligent Systems Laboratory Center for Engineering and Sustainable Development Research De La Salle University Manila Philippines

Restaurant businesses require significant revenue generation to finance their operational costs. Without revenue, restaurants will operate under deficits, thus making operations unsustainable. This leads to increased risks of business closure and the inability to service any form of customer demand sustainably. Factors that affect revenue generation for restaurants include but are not limited to the following: capital, the availability and limit of stored ingredients, ingredient costs, customer demand, and food sales. This study used Integer linear programming (ILP) to model a simulated restaurant’s monthly revenue sales. Optimal maximization of revenue served as the objective function of the ILP model. On the other hand, considerations in formulating the model’s constraint equations include ingredient usage for each menu item, budget for ingredient purchase, and the monthly sales demand distribution of menu items. The MATLAB software was used to simulate the ILP model. The simulation results provided the optimal ingredient inventory configuration and the required number of sales for each menu item.

关键词： Costs Simulation Integer linear programming linear programming Mathematical models Software Optimization

Solving a multilevel linear programming problems through a new constructive approach

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Kaci, Mustapha Radjef, Sonia Laboratory University of Sciences and Technology of Oran Mohamed Boudiaf USTO-MB El Mnaouar BP 1505 Bir El Djir Oran31000 Algeria

In this paper, an algorithm is developed to solve a multilevel mono-objective linear programming problem (ML(MO)LPP), where the constructive adaptive method of linear programming is nested. This procedures is the modified versions of the SB. Sinha and S. Sinha’s linear programming approach. First, we build a map that reduces the ranges of decision variables that are over control of the previous level’s decision maker, depending on the chosen approach, called the range reduction map. Then, we use it to define a new sub-optimality estimate of the adaptive method for the problem under consideration. All the construction stages are carefully checked and illustrated with a numerical example. © 2022, CC BY-NC-ND.

关键词： linear programming

Tutorial and Practice in linear programming Optimization Problems in Supply Chain and Transport Logistics

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Bridgelall, Raj Department of Transportation Logistics and Finance North Dakota State University United States

This tutorial is an andragogical guide for students and practitioners seeking to understand the fundamentals and practice of linear programming. The exercises demonstrate how to solve classical optimization problems with an emphasis on spatial analysis in supply chain management and transport logistics. All exercises display the Python programs and optimization libraries used to solve them. The first chapter introduces key concepts in linear programming and contributes a new cognitive framework to help students and practitioners set up each optimization problem. The cognitive framework organizes the decision variables, constraints, the objective function, and variable bounds in a format for direct application to optimization software. The second chapter introduces two types of mobility optimization problems (shortest path in a network and minimum cost tour) in the context of delivery and service planning logistics. The third chapter introduces four types of spatial optimization problems (neighborhood coverage, flow capturing, zone heterogeneity, service coverage) and contributes a workflow to visualize the optimized solutions in maps. The workflow creates decision variables from maps by using the free geographic information systems (GIS) programs QGIS and GeoDA. The fourth chapter introduces three types of spatial logistical problems (spatial distribution, flow maximization, warehouse location optimization) and demonstrates how to scale the cognitive framework in software to reach solutions. The final chapter summarizes lessons learned and provides insights about how students and practitioners can modify the Phyton programs and GIS workflows to solve their own optimization problem and visualize the results. Copyright © 2022, The Authors. All rights reserved.

关键词： linear programming

On best uniform approximation of finite sets by linear combinations of real valued functions using linear programming

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Damelin, Steven B. Werman, Michael Department of Mathematics University of Michigan 530 Church Street Ann ArborMI48109 United States Department of Computer Science The Hebrew University Jerusalem91904 Israel

In this paper, we study the problem of best uniform approximation of finite sets by linear combinations of real valued functions using linear programming. Our study concerns the analysis of the best approximation problem: minα∈m max1≤i≤n |yi − Σj=1mαjΓj(xi)|. Here: Γ:= {Γ1, ..., Γm} is a list of functions where for each 1 ≤ j ≤ m, Γj : ∆ → with ∆ a set of evaluation points {x1, ..., xn}. {y1, ..., yn} is a set of real values and α := (α1, ..., αm) with αj ∈ , 1 ≤ j ≤ *** Codes 41, 68, 49 Copyright © 2022, The Authors. All rights reserved.

关键词： linear programming

Fast Verification of Control Barrier Functions via linear programming

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Pond, Ellie Hale, Matthew University of Florida GainesvilleFL32611 United States

Control barrier functions are a popular method of ensuring system safety, and these functions can be used to enforce invariance of a set under the dynamics of a system. A control barrier function must have certain properties, and one must both formulate a candidate control barrier function and verify that it does indeed satisfy the required properties. Targeting the latter problem, this paper presents a method of verifying any finite number of candidate control barrier functions with linear programming. We first apply techniques from real algebraic geometry to formulate verification problem statements that are solvable numerically. Typically, semidefinite programming is used to verify candidate control barrier functions, but this does not always scale well. Therefore, we next apply a method of inner-approximating the set of sums of squares polynomials that significantly reduces the computational complexity of these verification problems by transcribing them to linear programs. We give explicit forms for the resulting linear programs, and simulation results for a satellite inspection problem show that the computation time needed for verification can be reduced by more than 95%. © 2022, CC BY.

关键词： linear programming

A sequential linear programming (SLP) approach for uncertainty analysis-based data-driven computational mechanics

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Huang, Mengcheng Liu, Chang Du, Zongliang Tang, Shan Guo, Xu State Key Laboratory of Structural Analysis for Industrial Equipment Department of Engineering Mechanics International Research Center for Computational Mechanics Dalian University of Technology Dalian116023 China Ningbo Institute of Dalian University of Technology Ningbo315016 China

In this article, an efficient sequential linear programming algorithm (SLP) for uncertainty analysis-based data-driven computational mechanics (UA-DDCM) is presented. By assuming that the uncertain constitutive relationship embedded behind the prescribed data set can be characterized through a convex combination of the local data points, the upper and lower bounds of structural responses pertaining to the given data set, which are more valuable for making decisions in engineering design, can be found by solving a sequential of linear programming problems very efficiently. Numerical examples demonstrate the effectiveness of the proposed approach on sparse data set and its robustness with respect to the existence of noise and outliers in the data set. Copyright © 2022, The Authors. All rights reserved.

关键词： linear programming