1,540 results
Search Results
2. A NOTE ABOUT KANTOROVICH'S PAPER "MATHEMATICAL METHODS OF ORGANIZING AND PLANNING PRODUCTION"
- Author
-
Koopmans, Tjalling C.
- Subjects
MANAGEMENT science research ,ECONOMICS ,LINEAR programming ,MANAGERIAL economics ,INDUSTRIAL productivity ,COMMERCIAL products ,MATHEMATICAL programming ,INDUSTRIAL management ,SOVIET economy - Abstract
The article discusses points contained in the research papers of mathematician L.V. Kantorovich. There is little in either the Soviet or the Western literature in management, planning, or economics available in 1939 that could have served as a source for the ideas in this paper, in the concrete form in which they were presented. From its own internal evidence, the paper stands as a highly original contribution of the mathematical mind to problems which few at that time would have perceived as mathematical in nature-on a par with the earlier work of von Neumann on proportional economic growth in a competitive market economy, and the later work of Dantzig well known to readers of Management Science. Recently Kantorovich has published a book, "Economic Calculation of the Best Utilization of Resources," in which it is proposed that linear programming methods be applied in nationwide planning for the Soviet economy. This has already given rise to a lively debate in Russian economic and planning periodicals.
- Published
- 1960
- Full Text
- View/download PDF
3. A Vibration Damping Optimization Algorithm to Solve Flexible Job Shop Scheduling Problems with Reverse Flows.
- Author
-
Mehdizadeh, Esmaeil and Soleimaninia, Fatemeh
- Subjects
VIBRATION (Aeronautics) ,INDUSTRIAL efficiency ,MIXED integer linear programming ,LINEAR programming ,MATHEMATICAL programming - Abstract
The Flexible Job shop Scheduling Problem (FJSP), as a Production Scheduling Problem (PSP), is generally an extension of the Job shop Scheduling Problem (JSP). In this paper, the FJSP with reverse flow consisting of two flows of jobs (direct and reverse) at each stage is studied; the first flow initiates in Stage 1 and goes to Stage C (the last stage), and the second flow starts with Stage c and ends up in Stage 1. The aim is to minimize the makespan of the jobs (the maximum completion time). A Mixed Integer Programming (MIP) is presented to model the problem and the Branch and Bound (B&B) method is used to solve the problem. A numerical small-size problem is presented to demonstrate the applicability, for which the Lingo16 software is employed for a solution. Due to the NPhardness of the problem, a meta-heuristic, namely the Vibration Damping Optimization (VDO) algorithm with tuned parameters using the Taguchi method, is utilized to solve large-scale problems. To validate the results obtained using the proposed solution algorithm in terms of the solution quality and the required computational time, they are compared with those obtained by the Lingo 16 software for small-size problems. Finally, the performance of the proposed algorithm is compared with a Genetic Algorithm (GA) by solving some randomly generated larger-size test problems, based on which the results are analyzed statistically. Computational results confirm the efficiency and effectiveness of the proposed algorithm and show that the VDO algorithm performs well. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
4. George B. Dantzig: Operations Research Icon
- Author
-
Cottle, Richard W.
- Published
- 2005
- Full Text
- View/download PDF
5. A Simulation-Based Optimisation for the Stochastic Green Capacitated p-Median Problem.
- Author
-
Imran, Arif, Eko Wahyu Utomo, Ramadhan, Fadillah, Desrianty, Arie, Helianty, Yanti, and Mustofa, Fifi Herni
- Subjects
MONTE Carlo method ,MATHEMATICAL optimization ,VEHICLE routing problem ,MATHEMATICAL programming ,LINEAR programming ,CARBON emissions - Abstract
Purpose: This paper aims to propose a new model called the stochastic green capacitated p-median problem with a simulation-based optimisation approach. An integer linear programming mathematical model is built considering the total emission produced by vehicles and the uncertain parameters including the travel cost for a vehicle to travel from a particular facility to a customer and the amount of CO2 emissions produced. We also develop a simulation-based optimisation algorithm for solving the problem. Design/methodology/approach: The authors proposed new algorithms to solve the problem. The proposed algorithm is a hybridisation of Monte Carlo simulation and a Variable Neighbourhood Search matheuristic. The proposed model and method are evaluated using instances that are available in the literature. Findings: Based on the results produced by the computational experiments, the developed approach can obtain interesting results. The obtained results display that the proposed method can solve the problems within a short computational time and the solutions produced have good quality (small deviations). Originality/value: To the best of our knowledge, there is no paper in the previous literature investigating the simulation-based optimisation for the stochastic green capacitated p-median problem. There are two main contributions in this paper. First, to build a new model for the capacitated p-median problem taking into account the environmental impact. Second, to design a simulation-based optimisation approach to solve the stochastic green capacitated p-median problem incorporating VNS-based matheuristic and Monte Carlo simulation. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
6. Process integration for emerging challenges: optimal allocation of antivirals under resource constraints
- Author
-
Rochelle Irene G. Lucas, Aristotle T. Ubando, Raymond R. Tan, Anthony S.F. Chiu, Christina D. Cayamanda, Luis F. Razon, John Frederick D. Tapia, Charlle L. Sy, Ador R. Torneo, Michael Angelo B. Promentilla, Kathleen B. Aviso, and Derrick Ethelbhert C. Yu
- Subjects
Decision support system ,Economics and Econometrics ,Environmental Engineering ,Linear programming ,Computer science ,020209 energy ,Sustainable Development Goals ,02 engineering and technology ,010501 environmental sciences ,Management, Monitoring, Policy and Law ,01 natural sciences ,Task (project management) ,Interim ,Process integration ,0202 electrical engineering, electronic engineering, information engineering ,Production (economics) ,Environmental Chemistry ,Resource allocation ,Disease outbreak ,0105 earth and related environmental sciences ,Pace ,Original Paper ,COVID-19 ,Mathematical programming ,General Business, Management and Accounting ,Risk analysis (engineering) ,Pharmaceutical shortage - Abstract
The global scientific community has intensified efforts to develop, test, and commercialize pharmaceutical products to deal with the COVID-19 pandemic. Trials for both antivirals and vaccines are in progress; candidates include existing repurposed drugs that were originally developed for other ailments. Once these are shown to be effective, their production will need to be ramped up rapidly to keep pace with the growing demand as the pandemic progresses. It is highly likely that the drugs will be in short supply in the interim, which leaves policymakers and medical personnel with the difficult task of determining how to allocate them. Under such conditions, mathematical models can provide valuable decision support. In particular, useful models can be derived from process integration techniques that deal with tight resource constraints. In this paper, a linear programming model is developed to determine the optimal allocation of COVID-19 drugs that minimizes patient fatalities, taking into account additional hospital capacity constraints. Two hypothetical case studies are solved to illustrate the computational capability of the model, which can generate an allocation plan with outcomes that are superior to simple ad hoc allocation. Graphic abstract
- Published
- 2020
- Full Text
- View/download PDF
7. Elements of Large Scale Mathematical Programming: Part II: Synthesis of Algorithms and Bibliography
- Author
-
Geoffrion, Arthur M.
- Published
- 1970
8. Exact Matrix Factorization Updates for Nonlinear Programming.
- Author
-
Escobedo, Adolfo R.
- Subjects
- *
MATRIX decomposition , *LINEAR programming , *DATA libraries , *MATHEMATICAL programming , *LINEAR equations , *NONLINEAR programming , *INTEGER programming - Abstract
LU and Cholesky matrix factorization algorithms are core subroutines used to solve systems of linear equations (SLEs) encountered when solving an optimization problem. Standard floating-point algorithms are highly efficient but remain susceptible to the accumulation of round-off errors, which can lead solvers to return feasibility and optimality claims that are actually invalid. This paper introduces a novel direct solution approach for solving sequences of closely related SLEs encountered in nonlinear programming efficiently and without round-off errors. Specifically, it introduces rank-one update algorithms for the round-off error–free factorization framework, a tool set built on integer-preserving arithmetic that has led to the development and implementation of extremely reliable subroutines for solving SLEs occurring in linear programming. The formal guarantees of the presented algorithms are established through the derivation of theoretical insights. Their advantages are supported with computational experiments, which demonstrate upward of 75× improvements over exact factorization runtimes on fully dense matrices with more than one million entries. A significant advantage of the featured integer-preserving framework is that the length of any matrix coefficient produced by its algorithms is bounded polynomially in the size of the inputs without having to resort to greatest common divisor operations, which are required by and thereby hinder an efficient implementation of exact rational arithmetic approaches. History: Accepted by Antonio Frangioni, Area Editor for Design & Analysis of Algorithms–Continuous. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2021.0331) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0331). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/. [ABSTRACT FROM AUTHOR]
- Published
- 2024
- Full Text
- View/download PDF
9. Possible Impact of Risk Management Strategies with Farm Model on a Mixed Farm Type.
- Author
-
Brečko, Jure and Žgajnar, Jaka
- Subjects
FARM management ,GREENHOUSE gases ,LINEAR programming ,FARMS ,PRODUCTION planning - Abstract
Background: Farm-level models have become an important tool for agricultural economists as there is a growing demand for microsimulation and analysis of farms at the individual level. Objectives: In this paper, we present a mathematical model with the main objective of assessing the effectiveness of production and various possible strategies for agricultural holdings by reducing risks. At the same time, we were also interested in the environmental impacts of such strategies. The latter was measured using the indicator of GHG emissions. Methods/Approach: The model applied is based on linear programming and upgraded with QRP for risk analysis. The approach was tested on medium size mixed agricultural holding, which often faces challenges in light of the structural changes taking place in Slovenia. Results: The results suggest that such a farm could improve financial results with a more efficient risk management strategy. With a slightly modified production plan, the expected gross margin (EGM) can be increased by up to 10% at more or less the same risk. However, if the farmer is willing to diversify the production plan and take a higher risk (+23%), the farm's EGM could increase by up to 18%. This kind of change in the production plan would also generate 17% more GHG emissions in total, calculated as kg equivalent of CO2 at the farm level, as both BL and C scenarios have the same relative ratio at 3.12 GHG CO2 eq. /EUR. Conclusions: Through this research, we concluded that diversification has a positive potential on a mixed farm, and the farm could achieve better financial results. With flexibility in management, the farmer could also achieve higher risk management efficiency and better farm results. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
10. AN INTERPRETATION OF FRACTIONAL OBJECTIVES IN GOAL PROGRAMMING AS RELATED TO PAPERS BY AWERBUCH, ET AL., AND HANNAN.
- Author
-
Soyster, A. L. and Lev, B.
- Subjects
MATHEMATICAL programming ,ALGORITHMS ,GOAL Attainment Scaling ,MANAGEMENT ,LINEAR programming ,MATHEMATICS ,MULTIPLE criteria decision making ,MANAGEMENT science ,BUSINESS logistics - Abstract
In this note we consider the validity of substituting a linear goal for a fractional goal in a mathematical program and provide a simple geometric interpretation that contrasts the essential differences between the two programs. [ABSTRACT FROM AUTHOR]
- Published
- 1978
- Full Text
- View/download PDF
11. Mathematical Programming for the Dynamics of Opinion Diffusion.
- Author
-
Ellero, Andrea, Fasano, Giovanni, and Favaretto, Daniela
- Subjects
MATHEMATICAL programming ,CONTINUOUS time models ,LINEAR programming ,DIFFUSION control - Abstract
The focus of this paper is on analyzing the role and the choice of parameters in sociophysics diffusion models by leveraging the potentialities of sociophysics from a mathematical programming perspective. We first present a generalised version of Galam's opinion diffusion model. For a given selection of the coefficients in our model, this proposal yields the original Galam's model. The generalised model suggests guidelines for possible alternative selection of its parameters that allow it to foster diffusion. Examples of the parameters selection process as steered by numerical optimisation, taking into account various objectives, are provided. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
12. DEFINING RISKS ON ROAD SECTIONS 971 DURING THE TRANSPORT OF DANGEROUS GOODS IN THE SERBIAN ARMY USING THE LINEAR MATHEMATICAL PROGRAMMING MODEL.
- Author
-
Planić, Јоvana M.
- Subjects
HAZARDOUS substances ,LINEAR programming ,TRAFFIC safety ,DATA envelopment analysis ,FUZZY systems ,FUZZY logic ,MATHEMATICAL programming - Abstract
Copyright of Military Technical Courier / Vojnotehnicki Glasnik is the property of Military Technical Courier / Vojnotehnicki Glasnik and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
- Published
- 2022
- Full Text
- View/download PDF
13. A COMMENT ON A PAPER OF MAXWELL.
- Author
-
Sidney, Jeffrey B.
- Subjects
JOB shops management ,INTEGER programming ,MATHEMATICAL programming ,PRODUCTION management (Manufacturing) ,ALGORITHMS ,LINEAR programming ,MATHEMATICAL optimization ,MATHEMATICAL models ,MANAGEMENT science research ,OPERATIONS research - Abstract
The article presents comments on the management science paper "On Sequencing n Jobs on One Machine to Minimize the Number of Late Jobs," by William L. Maxwell. The paper focused on an integer programming formulation of a one-machine job shop problem. The author contends that Maxwell made in error in proving the validity of an optimal algorithm by applying cutting plane constraints to the problem. The author explains that the problem cannot be solved through traditional cutting plane procedures. The author provides a mathematical model in an attempt to correct the proof.
- Published
- 1972
- Full Text
- View/download PDF
14. Feeder delivery vehicle scheduling optimization of high-speed railway express based on trunk and branch intermodal transportation.
- Author
-
Cui, Yao and Zhou, Xiaoye
- Subjects
CONTAINERIZATION ,TRAIN schedules ,INTERMODAL freight terminals ,LINEAR programming ,INTEGER programming ,MATHEMATICAL programming ,HEURISTIC algorithms - Abstract
In view of the traditional branch line end express delivery centralized mode cannot adapt to the growing demand of high-speed rail (HSR) express, resulting in poor connection between trunk and branch line, high cost and poor timeliness. In this paper, the problem of scheduling optimization of branch-line flexible distribution vehicles relying on intermodal transportation of trunk and branch lines is proposed. Considering the number of vehicles, vehicle capacity, customer service time window and other constraints, an integer linear programming mathematical model with the minimum total cost of vehicle transportation cost, usage cost and time window penalty cost as the optimization objective is established. A two-level nested heuristic algorithm with two-level coding structure is proposed to solve the problem. Finally, a simulation example is given to verify the effectiveness of the model and the algorithm. The results show that the vehicle scheduling optimization problem studied in this paper can effectively improve the timeliness and accuracy of HSR express delivery, and can significantly reduce the total vehicle delivery cost. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
15. Maximising Distribution Grid Utilisation by Optimising E-Car Charging Using Smart Meter Gateway Data.
- Author
-
Ulrich, André, Baum, Sergej, Stadler, Ingo, Hotz, Christian, and Waffenschmidt, Eberhard
- Subjects
SMART meters ,OPTIMIZATION algorithms ,MATHEMATICAL programming ,ELECTRIC power distribution grids ,ELECTRIC charge - Abstract
The transition towards climate neutrality will result in an increase in electrical vehicles, as well as other electric loads, leading to higher loads on electrical distribution grids. This paper presents an optimisation algorithm that enables the integration of more loads into distribution grid infrastructure using information from smart meters and/or smart meter gateways. To achieve this, a mathematical programming formulation was developed and implemented. The algorithm determines the optimal charging schedule for all electric vehicles connected to the distribution grid, taking into account various criteria to avoid violating physical grid limitations and ensuring non-discriminatory charging of all electric vehicles on the grid while also optimising grid operation. Additionally, the expandability of the infrastructure and fail-safe operation are considered through the decentralisation of all components. Various scenarios are modelled and evaluated in a simulation environment. The results demonstrate that the developed optimisation algorithm allows for higher transformer loads compared to a P(U) control approach, without causing grid overload as observed in scenarios without optimisation or P(U) control. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
16. Residual-Consensus Driven Linear Matching.
- Author
-
Wang, Hao
- Subjects
IMAGE registration ,LINEAR statistical models ,LINEAR programming ,IMAGE retrieval ,ESTIMATION theory - Abstract
Linear matching (LM) is a simple and effective method for solving image matching problems. In many cases, image matching problems are nonlinear due to involvement of the geometric transformations; therefore, an essential step for utilizing linear models for image matching is to linearize the geometric transformation matrices that introduce nonlinear terms into image matching problems. Existing LM methods usually use low-order transformations to artificially initialize a linear model. In this paper, we propose a residual-consensus driven LM algorithm that generalizes existing LM methods by allowing higher order transformations to automatically initialize a linear model. Based on the observation that transformation models generated from inlier subsets exhibit correlated behaviors (termed residual consensus hereafter), we develop a residual-consensus robust estimation algorithm to project the nontrivial linear transformation problem into a much smaller subspace, and thus enable efficient optimizations through linear programming. The experimental results on synthetic and real databases demonstrate the effectiveness and robustness of the proposed algorithm. [ABSTRACT FROM PUBLISHER]
- Published
- 2017
- Full Text
- View/download PDF
17. Solving Multiobjective Linear Programming Problems with Interval Parameters.
- Author
-
Rivaz, S. and Saeidi, Z.
- Subjects
MULTIPLE criteria decision making ,LINEAR programming ,MATHEMATICAL programming ,COEFFICIENTS (Statistics) ,MATHEMATICAL optimization - Abstract
In the present paper, a multiobjective linear programming problem under uncertainty, particularly when parameters are given in interval forms, is investigated. In this case, it is assumed that objective coefficients and constraints parameters have arrived in interval numbers. Considering a suitable order relation for interval numbers, a solution procedure for dealing with such a problem is developed. A numerical example is provided to illustrate the efficiency of the solution procedure. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
18. Total Problem of Constructing Linear Regression Using Matrix Correction Methods with Minimax Criterion.
- Author
-
Gorelik, Victor and Zolotova, Tatiana
- Subjects
LINEAR programming ,MATHEMATICAL programming ,NONLINEAR programming ,CORRECTION factors ,REGRESSION analysis - Abstract
A linear problem of regression analysis is considered under the assumption of the presence of noise in the output and input variables. This approximation problem may be interpreted as an improper interpolation problem, for which it is required to correct optimally the positions of the original points in the data space so that they all lie on the same hyperplane. The use of the quadratic approximation criterion for such a problem led to the appearance of the total least squares method. In this paper, we use the minimax criterion to estimate the measure of correction of the initial data. It leads to a nonlinear mathematical programming problem. It is shown that this problem can be reduced to solving a finite number of linear programming problems. However, this number depends exponentially on the number of parameters. Some methods for overcoming this complexity of the problem are proposed. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
19. A new algorithm for the maximum weighted stable set problem in claw-free graphs
- Author
-
Gianpaolo Oriolo, Ugo Pietropaoli, Gautier Stauffer, Dipartimento di Ingegneria dell'Impresa [Roma], Università degli Studi di Roma Tor Vergata [Roma], Reformulations based algorithms for Combinatorial Optimization (Realopt), Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria), Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1 (UB)-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Institut de Mathématiques de Bordeaux (IMB), Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)-Inria Bordeaux - Sud-Ouest, and Université Bordeaux Segalen - Bordeaux 2-Université Sciences et Technologies - Bordeaux 1-Université de Bordeaux (UB)-Institut Polytechnique de Bordeaux (Bordeaux INP)-Centre National de la Recherche Scientifique (CNRS)
- Subjects
Combinatorial optimization ,Computer science ,0211 other engineering and technologies ,02 engineering and technology ,Polynomials ,01 natural sciences ,Domain decomposition methods ,Scheduling algorithms ,Matching problems ,Chordal graph ,Polynomial-time algorithms ,Longest path ,ComputingMilieux_MISCELLANEOUS ,decomposition theorems ,021103 operations research ,Quasi-line graphs ,Mathematical programming ,Integer programming ,Longest path problem ,Graph ,Modular decomposition ,010201 computation theory & mathematics ,(algorithmic) complexity ,Auxiliary graphs ,Claw-free graphs ,Mathematical transformations ,Set theory ,Settore MAT/09 - Ricerca Operativa ,Algorithm ,Algorithms ,Optimization ,Paper ,Aerospace applications ,Boolean functions ,Combinatorial mathematics ,Curve fitting ,Dynamic programming ,Evolutionary algorithms ,Farm buildings ,Graph theory ,Linear programming ,Nonlinear programming ,Polynomial approximation ,Reduction ,Trees (mathematics) ,General (CO) ,graph reductions ,international conferences ,New algorithm ,Polynomial-time ,Reduction tools ,Running in ,time bound ,0102 computer and information sciences ,Combinatorics ,Indifference graph ,Pathwidth ,Cograph ,[INFO]Computer Science [cs] ,Graph coloring ,Time complexity ,Discrete mathematics ,1-planar graph ,Vertex (geometry) ,Independent set - Abstract
In this paper, we introduce two powerful graph reductions for the maximum weighted stable set (mwss) in general graphs. We show that these reductions allow to reduce the mwss in claw-free graphs to the mwss in a class of quasi-line graphs, that we call bipolar-free. For this latter class, we provide a new algorithmic decomposition theorem running in polynomial time. We then exploit this decomposition result and our reduction tools again to transform the problem to either a single matching problem or a longest path computation in an acyclic auxiliary graph (in this latter part we use some results of Pulleyblank and Shepherd [10]). Putting all the pieces together, the main contribution of this paper is a new polynomial time algorithm for the mwss in claw-free graphs. A rough analysis of the complexity of this algorithm gives a time bound of O(n6), where n is the number of vertices in the graph, and which we hope can be improved by a finer analysis. Incidentally, we prove that the mwss problem can be solved efficiently for any class of graphs that admits a "suitable" decomposition into pieces where the mwss is easy.
- Published
- 2008
20. Solving an airport ground service task assignment problem with an exact algorithm.
- Author
-
Tian, Qiannan, Li, Jie, Huang, Guoxuan, and Yuan, Wei
- Subjects
LINEAR programming ,MATHEMATICAL programming ,INTEGER programming ,COLUMNS ,TASK performance - Abstract
In this paper, an airport ground service task assignment problem is studied. A task represents a service, which must be performed by one or multiple ground crew of a shift with required qualification/proficiency within a prescribed time period. For every assigned task, define "task priority" times "task duration" as the "benefit" generated. The objective is to maximize the summation of "benefit" for all the assigned tasks. The problem is modeled as an integer linear programming problem with mathematical formulation. A branch-and-price algorithm is proposed for solving the problem instances to optimality. To expedite the column generation process, an acceleration strategy is proposed. The computational results show that our proposed branch-and-price algorithm is capable of solving large-sized instances and the acceleration strategy is quite effective in reducing the computational time. Moreover, the impact of changing various characteristics of tasks and shifts on the performance of the algorithm is studied in detail with supporting computational experiments. In particular, the impact of reducing the qualifications is significant with 20.82% improvement in the objective value. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
21. Kernel Search for the Capacitated Vehicle Routing Problem.
- Author
-
Borčinová, Zuzana
- Subjects
VEHICLE routing problem ,MATHEMATICAL programming ,SEARCH algorithms ,LINEAR programming - Abstract
This paper addresses the Capacitated Vehicle Routing Problem (CVRP), which is a widely studied optimization problem due to its relevance to the field of transportation, distribution, and logistics. We present a matheuristic method for CVRP that adopts the main idea of the Kernel Search algorithm (KS) based on decomposing the original problem into sub-problems that are easier to solve. Unlike the original scheme of KS, our approach uses the Clarke–Wright savings algorithm to construct a sequence of smaller sub-problems, which are subsequently solved using mathematical programming strategies. The computational experiments performed on a set of benchmark instances showed that the proposed matheuristics achieves good results in acceptable computational time. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
22. Estimation of Overall Returns to Scale (RTS) of a Frontier Unit Using the Left and Right RTS.
- Author
-
Omidi, Mostafa, Rostamy-Malkhalifeh, Mohsen, Payan, Ali, and Hosseinzadeh Lotfi, Farhad
- Subjects
RETURNS to scale ,DATA envelopment analysis ,MATHEMATICAL programming ,GROUP decision making ,LINEAR programming - Abstract
This paper introduces a proposed method for identifying the left and right Returns to Scales (RTS) and the overall RTS of frontier units based on the theoretical framework of data envelopment analysis (DEA). This paper first proposes an alternative definition for Left RTS (L-RTS) and Right RTS (R-RTS) of frontier units and then by focusing on this definition, provides two new DEA models to present a proposed method for identifying the L-RTS and R-RTS of frontier units. The major advantages of these two models include that they are feasible in all situations. Also, these models are capable to properly and accurately identify frontier units and their type of L-RTS and R-RTS, without any plurality in their judgment. The proposed method is compared -theoretically and experimentally- with other methods presented in the literature. Moreover, the theoretical correlation between the concepts of overall RTS and L&R-RTS of frontier units is analyzed. Then, this analysis is used to propose an alternative method for categorizing overall RTS of frontier units. Experimental application of this method shows that the results of evaluation of overall RTS of frontier units obtained by the proposed method is completely consistent with the results of the method presented by Banker and Thrall (Eur J Oper Res 62(1):74-84, 1992). The proposed methods in this paper can be easily used by the existing codes of DEA. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
23. EQUILIBRIUM IN LINEAR CAPITAL MARKET NETWORKS.
- Author
-
STORØY, SVERRE, THORE, STEN, and BOYER, MARCEL
- Subjects
ECONOMIC equilibrium ,MARKETS ,DECOMPOSITION method ,CAPITAL market ,MATHEMATICAL programming ,LINEAR programming ,MATRICES (Mathematics) ,MATHEMATICAL models ,MATHEMATICAL decomposition ,OPERATIONS research ,SYSTEM analysis - Abstract
The purpose of this paper is to show how certain ideas in the so called decomposition theory of mathematical programming can be exploited for the computation of equilibrium in a system of linear capital markets. The fact that economic decision-making is made in a decentralized, i.e., independent, fashion by economic agents has a long been recognized and led economists to build models which, in one way or another, incorporated this feature. Two main departments of economic theory undertook the study of decentralization: on the one hand, the theory of decentralization of decisions inside the firm and the related decomposition theory of mathematical programming and, on the other hand, the study of general equilibrium systems and the decentralizing properties of competitive prices. The purpose of this paper is to show how certain ideas in the so called decomposition theory of mathematical programming can be exploited for the computation of equilibrium in a system of linear capital markets. The fact that economic decision-making is made in a decentralized, i.e., independent, fashion by economic agents has a long been recognized and led economists to build models which, in one way or another, incorporated this feature. Two main departments of economic theory undertook the study of decentralization: on the one hand, the theory of decentralization of decisions inside the firm and the related decomposition theory of mathematical programming and, on the other hand, the study of general equilibrium systems and the decentralizing properties of competitive prices. [ABSTRACT FROM AUTHOR]
- Published
- 1975
- Full Text
- View/download PDF
24. A PROGRAMMING APPROACH TO CORPORATE FINANCIAL MANAGEMENT.
- Author
-
MYERS, STEWART C. and POGUE, GERALD A.
- Subjects
CORPORATE finance ,LINEAR programming ,MATHEMATICAL programming ,CAPITAL budget ,FINANCE ,CAPITAL investments - Abstract
In this paper we present an outline of LONGER, a financial planning model based on mixed integer linear programming. The model is based on recent advances in capital market theory, but at the same time it recognizes certain additional considerations that are manifestly important to the financial manager. Thus, we believe that the model has good potential for practical application, although in this paper we emphasize LONGER's relationship to finance theory. We will skim over a number of issues that are critical in a practical application; a later paper will discuss these issues and present LONGER at a practical level of detail. Still another paper has worked out implications for decentralized capital budgeting rules. [ABSTRACT FROM AUTHOR]
- Published
- 1974
- Full Text
- View/download PDF
25. A convergence analysis for a convex version of Dikin's algorithm.
- Author
-
Jie Sun
- Subjects
STOCHASTIC convergence ,ALGORITHMS ,CONVEX programming ,LINEAR programming ,MATHEMATICAL programming - Abstract
This paper is concerned with the convergence property of Dikin's algorithm applied to linearly constrained smooth convex programs. We study a version of Dikin's algorithm in which a second-order approximation of the objective function is minimized at each iteration together with an affine transformation of the variables. We prove that the sequence generated by the algorithm globally converges to a limit point at a local linear rate if the objective function satisfies a Hessian similarity condition. The result is of a theoretical nature in the sense that in order to ensure that the limit point is an ε-optimal solution, one may have to restrict the steplength to the order of O(ε). The analysis does not depend on non-degeneracy assumptions. [ABSTRACT FROM AUTHOR]
- Published
- 1996
- Full Text
- View/download PDF
26. ON "AN INTERPRETATION OF FRACTIONAL OBJECTIVES IN GOAL PROGRAMMING AS RELATED TO PAPERS BY AWERBUCH ET AL., AND HANNAN"
- Author
-
Hannan, Edward L.
- Subjects
GOAL (Psychology) ,MOTIVATION (Psychology) ,DECISION making ,CHOICE (Psychology) ,LINEAR programming ,BUSINESS mathematics ,MATHEMATICAL programming ,STRATEGIC planning ,MATHEMATICAL models in business ,MATHEMATICAL models of industrial management ,MANAGEMENT science ,MATHEMATICAL optimization - Abstract
This Note points out a minor error in a technique developed by Soyster and Lev [1] for determining if a linear goal can be substituted for a fractional goal in a goal programming problem. A revised formulation is provided. [ABSTRACT FROM AUTHOR]
- Published
- 1981
- Full Text
- View/download PDF
27. Nonintrusive Load Monitoring Algorithm Using Mixed-Integer Linear Programming.
- Author
-
Wittmann, Fernando Marcos, Lopez, Juan Camilo, and Rider, Marcos J.
- Subjects
ALGORITHMS ,ELECTRIC power systems ,ELECTRIC vehicles ,LINEAR programming ,MATHEMATICAL programming - Abstract
This paper presents a nonintrusive load monitoring (NILM) algorithm based on mixed-integer linear programming. The formulation deals with the problem of multiple switching that arises when disaggregating individual appliance’s consumptions from a compound power measurement. Mixed-integer linear constraints are used to efficiently represent the load signatures of each appliance. Also, a window-based strategy is used to enhance the computational performance of the proposed NILM algorithm. The disaggregation can be made using only active power measurements at a low sampling rate, which is available in most energy meters. Moreover, if available, other signatures can be added to the model to improve its accuracy, such as reactive power signatures or harmonics. The performance of the algorithm is evaluated using three test cases from the almanac of minutely power dataset. The proposed method is also compared with a disaggregation method called aided linear integer programming. Results demonstrate the ability of the proposed method to accurately identify and allocate individual energy signatures in a computationally efficient manner, which makes it suitable for inexpensive home energy management. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
28. Performance Results of the Simplex Algorithm for a Set of Real-World Linear Programming Models.
- Author
-
McCall, Edward H. and Greenberg, Harvey J.
- Subjects
LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,COMPUTER programming ,COMPUTER algorithms ,ALGEBRA - Abstract
This paper provides performance results using the SPERRY UNIVAC 1100 Series linear programming product FMPS to solve a set of 16 real-world linear programming problems. As such, this paper provides a data point for the actual performance of a commercial simplex algorithm on real-world linear programming problems and shows that the simplex algorithm is a linear time algorithm in actual performance. Correlations and performance relationships not previously available are also provided. [ABSTRACT FROM AUTHOR]
- Published
- 1982
- Full Text
- View/download PDF
29. LPDA: A new classification method based on linear programming.
- Author
-
Nueda, María J., Gandía, Carmen, and Molina, Mariola D.
- Subjects
LINEAR programming ,MATHEMATICAL programming ,CENTROID ,HYPERPLANES ,CLASSIFICATION - Abstract
The search of separation hyperplanes is an efficient way to find rules with classification purposes. This paper presents an alternative mathematical programming formulation to existing methods to find a discriminant hyperplane. The hyperplane H is found by minimizing the sum of all the distances to the area assigned to the group each individual belongs to. It results in a convex optimization problem for which we find an equivalent linear programming problem. We demonstrate that H exists when the centroids of the two groups are not equal. The method is effective dealing with low and high dimensional data where reduction of the dimension is proposed to avoid overfitting problems. We show the performance of this approach with different data sets and comparisons with other classifications methods. The method is called LPDA and it is implemented in a R package available in https://github.com/mjnueda/lpda. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
30. An Interval Arithmetic-Based State Estimation Framework for Power Distribution Networks.
- Author
-
Xu, Junjun, Wu, Zaijun, Yu, Xinghuo, Hu, Qinran, and Dou, Xiaobo
- Subjects
POWER distribution networks ,INTERVAL analysis ,BOUND states ,UNITS of measurement ,RENEWABLE energy sources ,INTERVAL measurement ,MATHEMATICAL programming ,LINEAR programming - Abstract
An enormous challenge for state estimation (SE) in power distribution networks with high penetration of photovoltaic generators lies in how to deal with measurement uncertainty. Driven by this motivation, an interval arithmetic (IA) based SE is proposed in this paper, which considers interval modeling for measurement uncertainty. The proposed SE is formulated as two interval optimization models based on the unknown-but-bounded theory, and solution bounds of state variables are obtained using a two-stage linear programming approach. In particular, the proposed SE is extended to realistic power distribution networks with mixed microphasor measurement units (μPMU), voltage magnitude, smart meters and feeder terminal units. Case studies and results are illustrated and discussed to demonstrate the performance of the proposed IA-based SE. It could provide the operators intuitive and effective bounds of system states for advanced power industrial applications under consideration of uncertainty. [ABSTRACT FROM AUTHOR]
- Published
- 2019
- Full Text
- View/download PDF
31. AUTHOR'S REPLY TO VERGIN'S NOTE ON THE PAPER "LOT SIZE SCHEDULING ON A SINGLE MACHINE FOR STOCHASTIC DEMAND"
- Author
-
Goyal, S. K.
- Subjects
PRODUCTION scheduling ,OPERATIONS research ,MATHEMATICAL programming ,PRODUCTION control ,LINEAR programming ,INDUSTRIAL productivity ,LEAD time (Supply chain management) ,MANAGEMENT science ,STOCHASTIC processes - Abstract
This article presents a response to comments made by writer Roger C. Vergin on the author's article "Lot Size Scheduling on a Single Machine for Machine for Stochastic Demand," published in the November 1973 issue. The author points out that the assumptions challenged by Vergin are not important to the overall results of the author's model. Furthermore, he shows that the need for cyclical scheduling process for a multi-product single machine system arises as a result of the interference caused by batches of products because of different time intervals between production runs.
- Published
- 1976
- Full Text
- View/download PDF
32. Managing Advance Admission Requests for Obstetric Care.
- Author
-
Geng, Na and Xie, Xiaolan
- Subjects
- *
MATHEMATICAL programming , *POSTNATAL care , *STOCHASTIC control theory , *PRENATAL care , *OPERATIONS research , *LINEAR programming - Abstract
This paper is devoted to the management of advance admission requests for obstetric care. Pregnant women in China select one hospital and request admission for both antenatal and postnatal care after nine weeks of pregnancy. Schedulers must make the admission decision instantly based on the availability of the most critical resource, that is, hospital beds for postnatal care. The random delay between admission requests and postnatal care has created a distinct advance admission control problem. To address this issue, we propose a basic model that assumes a unit bed requirement for one day. Each admission generates a unit of revenue and each unit of overcapacity use incurs an overcapacity cost. With the objective of maximizing the expected net revenue, we establish an optimal policy for unlimited requests, that is, an expected arrival time quota (EATQ) policy that accepts a fixed quota of advance admission requests with the same expected date of confinement. We then propose an extended model for general capacity requirements. Using the Poisson approximation, we establish the optimality of the EATQ policy, which is shown to be solvable by a simple linear programming model. We compare the numerical results from the different policies and conduct a sensitivity analysis. The EATQ policy is demonstrated to be the best option in all test instances and notably outperforms the current admission rules used in hospitals, which usually accept admission requests according to some empirical monthly quota of the expected delivery month. The Poisson approximation is shown to be effective for determining the optimal EATQ policy for both stationary and nonstationary arrivals. Summary of Contribution: First, this paper investigates the advance admission control problem for obstetric care. Pregnant women in China choose one hospital and request admission for both antenatal and postnatal care after nine weeks of pregnancy but the most critical resource is hospitalization beds needed for postnatal care. The random delay between admission request and postnatal care makes the problem unique and challenging to solve. It belongs to the scope of computing and operations research. Second, this paper formulates a dynamic programming model, analyzes the structural properties of the optimal control policy, and finally proposes a mathematical programming model to determine the optimal quota. Numerical experiments show the validity of the proposed approach. It covers the research contents of theories on dynamic stochastic control, mathematic programming model, and experiments. Moreover, this paper is motivated by the practical problem (advance admission control) in obstetric units of Shanghai. Using these optimality properties, solution approaches, and numerical results, this paper provides guidance on how to manage advance obstetric admission requests. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
33. A linear physical programming model for assembly line balancing problem.
- Author
-
Akpınar, Muhammet Enes
- Subjects
- *
ASSEMBLY line balancing , *LINEAR programming , *MATHEMATICAL programming - Abstract
This paper deals with the mixed-model assembly line balancing problem. This type of line is applied to more than one similar model of a product in an intermixed order. Despite their widespread use, these lines have received little attention in the literature. Metaheuristics, heuristics, and mathematical programming techniques are developed to solve these types of assembly line balancing problems. However, linear physical programming method has never been used. In this paper, a linear physical programming model is proposed for balancing a mixed-model assembly line. The performance of the proposed model is applied to a numerical example to analyze the usage of the methodology. Five objectives are considered in the model, and the outperformance of the methodology is demonstrated by comparing it to a different approach. According to the results, it has been seen that the proposed linear physical programming model is practical and useful approach for mixed-model assembly line balancing problems. [ABSTRACT FROM AUTHOR]
- Published
- 2022
- Full Text
- View/download PDF
34. Generation Investment Equilibria With Strategic Producers—Part I: Formulation.
- Author
-
Kazempour, S. Jalal, Conejo, Antonio J., and Ruiz, Carlos
- Subjects
ELECTRIC industries ,ELECTRICITY ,BILEVEL programming ,MATHEMATICAL optimization ,MATHEMATICAL programming ,MATHEMATICAL models - Abstract
The first of this two-paper series proposes a methodology to characterize generation investment equilibria in a pool-based network-constrained electricity market, where the producers behave strategically. To this end, the investment problem of each strategic producer is represented using a bilevel model, whose upper-level problem determines the optimal investment and the supply offering curves to maximize its profit, and whose several lower-level problems represent different market clearing scenarios. This model is transformed into a mathematical program with equilibrium constraint (MPEC) through replacing the lower-level problems by their optimality conditions. The joint consideration of all producer MPECs, one per producer, constitutes an equilibrium problem with equilibrium constraints (EPEC). To identify the solutions of this EPEC, each MPEC problem is replaced by its Karush-Kuhn-Tucker (KKT) conditions, which are in turn linearized. The resulting mixed-integer linear system of equalities and inequalities allows determining the EPEC equilibria through an auxiliary MILP problem. [ABSTRACT FROM PUBLISHER]
- Published
- 2013
- Full Text
- View/download PDF
35. PARAMETRIC METHODS IN INTEGER LINEAR PROGRAMMING.
- Author
-
Jenkins, Larry
- Subjects
LINEAR programming ,ALGORITHMS ,INTEGER programming ,MATHEMATICAL programming ,OPERATIONS research - Abstract
In contrast to methods of parametric linear programming which were developed soon after the invention of the simplex algorithm and are easily included as an extension of that method, techniques for parametric analysis on integer programs are not well known and require considerable effort to append them to an integer programming solution algorithm. The paper reviews some of the theory employed in parametric integer programming, then discusses algorithmic work in this area over the last 15 years when integer programs are solved by different methods. A summary of applications is included and the article concludes that parametric integer programming is a valuable tool of analysis awaiting further popularization. [ABSTRACT FROM AUTHOR]
- Published
- 1990
- Full Text
- View/download PDF
36. ON NONLINEAR FRACTIONAL PROGRAMMING.
- Author
-
Dinkelbach, Werner
- Subjects
FRACTIONAL integrals ,NONLINEAR programming ,LINEAR programming ,MATHEMATICAL programming ,ALGORITHMS ,PARAMETER estimation ,QUADRATIC programming ,CONCAVE functions ,CONVEX functions ,POLYHEDRAL functions ,NUMERICAL solutions to Lagrange equations - Abstract
The main purpose of this paper is to delineate an algorithm for fractional programming with nonlinear as well as linear terms in the numerator and denominator. The algorithm presented is based on a theorem by Jagannathan [7] concerning the relationship between fractional and parametric programming. This theorem is restated and proved in a somewhat simpler way. Finally, it is shown how the given algorithm can be related to the method of Isbell and Marlow [6] for linear fractional programming and to the quadratic parametric approach by Ritter [10]. The Appendix contains a numerical example. [ABSTRACT FROM AUTHOR]
- Published
- 1967
- Full Text
- View/download PDF
37. A fuzzy optimization model for planning integrated terrestrial carbon management networks.
- Author
-
Belmonte, Beatriz A., Aviso, Kathleen B., Benjamin, Michael Francis D., and Tan, Raymond R.
- Subjects
BIOCHAR ,SOIL amendments ,CARBON sequestration ,LINEAR programming ,MATHEMATICAL programming ,CARBON ,SET theory - Abstract
Biochar application and enhanced weathering are negative emission technologies (NETs) with the potential for large-scale deployment for the removal of CO
2 from the atmosphere. Biochar is a solid product of pyrolysis that can permanently store carbon when applied in soil due to its chemical recalcitrance. Enhanced weathering is based on the acceleration of the natural reaction of moisture, CO2 , and alkaline minerals. Both of these NETs rely on the application of pulverized material to different types of terrestrial sinks, which can include marginal and agricultural land. These two NETs can be used separately or concurrently, depending on local sink conditions. In some cases, simultaneous application of biochar and mineral powder to soil has the advantage of attaining additional beneficial effects of soil amendment. Although recent papers have reported the development of process integration models for optimizing carbon management networks based on either biochar application or enhanced weathering, none have reported models integrating these two NETs in the same system. To address this gap, a fuzzy mixed-integer linear programming model is developed that integrates biochar application and enhanced weathering for large-scale carbon sequestration. Fuzzy set theory provides a well-tested framework for integration of both subjectivity and uncertainty into mathematical programming. The model determines the optimal allocation of biochar and/or alkaline minerals from each source to each sink, while considering the application limits and CO2 sequestration potential. An illustrative case study is solved that clearly demonstrates the application of the model. The case study shows interesting results that can guide how the full sustainable potential of these two technologies can be utilized in a carbon management network. [ABSTRACT FROM AUTHOR]- Published
- 2022
- Full Text
- View/download PDF
38. IMPSO and Linear Programming-Based Energy-Efficient Cell Association Algorithm for Backhaul-Constrained Ultra-Dense Small-Cell Networks.
- Author
-
Jiang, Huilin, Zhu, Wenxiang, Song, Xiang, and Wu, Guilu
- Subjects
MATHEMATICAL programming ,PARTICLE swarm optimization ,LINEAR programming ,ENERGY consumption ,MATHEMATICAL optimization - Abstract
This paper studies the energy efficiency optimization problem for coordinated multipoint (CoMP)-enabled and backhaul-constrained ultra-dense small-cell networks (UDNs). Energy efficiency is an eternal topic for future wireless communication networks; however, taking actual bottleneck of the backhaul link and the coordinated network architecture into consideration, it is difficult to find an effective way to improve the energy efficiency of the network. Aiming at this problem, we propose to combine cell association, subchannel allocation, backhaul resource allocation, and sleep/on of the cells together to develop an optimization algorithm for energy efficiency in UDN and then solve the formulated energy efficiency optimization problem by means of improved modified particle swarm optimization (IMPSO) and linear programming in mathematics. Simulation results indicate that nearly 13 % energy cost saving and 21 % energy efficiency improvement can be obtained by combining IMPSO with linear programming, and the backhaul link data rate can be improved by 30 % as the number of small cells increases. From the results, it can be found that by combining IMPSO with linear programming, the proposed algorithm can improve the network energy efficiency effectively at the expense of limited complexity. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
39. SENSITIVITY ANALYSIS OF WEAK EFFICIENCY IN MULTIPLE OBJECTIVE LINEAR PROGRAMMING.
- Author
-
SITARZ, SEBASTIAN
- Subjects
LINEAR programming ,SENSITIVITY analysis ,SET theory ,CONVEX domains ,MATHEMATICAL programming ,MATHEMATICAL analysis - Abstract
This paper, studies the sensitivity analysis of weakly efficient extreme solutions in multiple objective linear programming (MOLP). The aim of the paper is to compute the set of the parameters (corresponding to one coefficient) for which a given extreme point is a weakly efficient solution. We also focus on the properties of the parameters set by proving convexity and closeness of this set. Moreover, we compare the results of the sensitivity analysis of efficiency and of weak efficiency in MOLP. [ABSTRACT FROM AUTHOR]
- Published
- 2011
- Full Text
- View/download PDF
40. All Colors Shortest Path problem on trees.
- Author
-
Akçay, Mehmet Berkehan, Akcan, Hüseyin, and Evrendilek, Cem
- Subjects
LINEAR programming ,MATHEMATICAL optimization ,MATHEMATICAL programming ,GENETIC algorithms ,HEURISTIC programming - Abstract
Given an edge weighted tree T(V, E), rooted at a designated base vertex r∈V
, and a color from a set of colors C={1,…,k} assigned to every vertex v∈V , All Colors Shortest Path problem on trees (ACSP-t) seeks the shortest, possibly non-simple, path starting from r in T such that at least one node from every distinct color in C is visited. We show that ACSP-t is NP-hard, and also prove that it does not have a constant factor approximation. We give an integer linear programming formulation of ACSP-t. Based on a linear programming relaxation of this formulation, an iterative rounding heuristic is proposed. The paper also explores genetic algorithm and tabu search to develop alternative heuristic solutions for ACSP-t. The performance of all the proposed heuristics are evaluated experimentally for a wide range of trees that are generated parametrically. [ABSTRACT FROM AUTHOR] - Published
- 2018
- Full Text
- View/download PDF
41. Encoding Large Asynchronous Controllers With ILP Techniques.
- Author
-
Carmona, Josep and Cortadella, Jordi
- Subjects
GRAPH theory ,MATHEMATICAL programming ,MATHEMATICAL optimization ,BOOLEAN algebra ,SYMBOLISM in communication ,SYNTAX (Grammar) ,LINEAR programming ,PERFORMANCE evaluation ,LINEAR algebra - Abstract
State encoding is one of the most difficult problems in the synthesis of asynchronous controllers. This paper presents a method that can solve the problem of large controllers specified with signal transition graphs. The method is based on the structural theory of Petri nets and uses integer-linear programming to insert state signals in locations that guarantee the consistency and absence of critical races. The structural nature of the proposed method makes it conservative, i.e., a solution cannot be guaranteed, even if it exists. Nevertheless, the experiments show that this limitation did not preclude finding a solution for all the examples presented in this paper. The method can be customized for area or delay optimization. The experimental results confirm the quality of the circuits, as compared with state-based methods. They also show the significant benefits that could be obtained if logic synthesis would be incorporated in synthesis frameworks that generate controllers by syntax-directed translation. [ABSTRACT FROM AUTHOR]
- Published
- 2008
- Full Text
- View/download PDF
42. Market- Clearing With Stochastic Security Part I: Formulation.
- Author
-
Bouffard, François, Galiana, Francisco D., and Conejo, Antonio J.
- Subjects
STOCHASTIC analysis ,ELECTRIC industries ,OVERHEAD costs ,DYNAMIC programming ,LINEAR programming ,MATHEMATICAL programming - Abstract
The first of this two-paper series formulates a stochastic security-constrained multi-period electricity market clearing problem with unit commitment. The stochastic security criterion accounts for a pre-selected set of random generator and line outages with known historical failure rates and involuntary load shedding as optimization variables. Unlike the classical deterministic reserve-constrained unit commitment, here the reserve services are determined by economically penalizing the operation of the market by the expected load not served. The proposed formulation is a stochastic programming problem that optimizes, concurrently with the pre-contingency social welfare, the expected operating costs associated with the deployment of the reserves following the contingencies. This stochastic programming formulation is solved in the second companion paper using mixedinteger linear programming methods. Two cases are presented: a small transmission-constrained three-bus network scheduled over a horizon of four hours and the IEEE Reliability Test System scheduled over 24 h. The impact on the resulting generation and reserve schedules of transmission constraints and generation ramp limits, of demand-side reserve, of the value of load not served, and of the constitution of the pre-selected set of contingencies are assessed. [ABSTRACT FROM AUTHOR]
- Published
- 2005
- Full Text
- View/download PDF
43. کمینهسازی هزینۀ انرژی در ماشینهای موازی با درنظرگرفتن زمان آمادهسازی.
- Author
-
هیمن صنعتی, قاسم مصلحی, and محمد رئیسی نافچی
- Subjects
- *
JOB shops , *SETUP time , *HEURISTIC algorithms , *HEURISTIC programming , *MATHEMATICAL programming , *LINEAR programming - Abstract
Purpose: In recent years, significant energy consumption and facing global warming have led to concern worldwide. Therefore, governments have turned to deterrent actions such as imposing daily tariffs in different intervals to tackle energy consumption. This article addresses unrelated parallel machine energy-efficient scheduling problems by considering sequence-independent setup times and energy consumption tariffs. The objective function is that jobs should be assigned to machines and processed in different intervals so that the cost of consumed energy becomes as less as possible. It should be noted that the assumed sequence-independent setup times are addressed in two different modes, setup times jointed to processing time and setup times disjointed from processing time. Design/methodology/approach: To optimize the total energy consumption cost in unrelated parallel machine scheduling problems with sequence-independent setup times jointed to processing time and disjointed from processing time, mixed-integer linear programming (MILP) models have been proposed from two different points of view. The first model has been formulated according to the predecessor jobs of a special job, while the second model has been conducted based on the immediate predecessor job. Also, a fix and relax heuristic (FRH) algorithm has been conducted to solve large-scale instances. All mathematical models and the heuristic algorithm have been coded in the Visual C# 2017 environment and implemented using the CPLEX 12.8 Concert Technology on a PC with 32GB RAM and Intel Corei7 4.0 GHz CPU (4 cores). Also, a sizeable number of instances have been solved to evaluate the efficiency of mathematical models and the heuristic algorithm and to ensure their accuracy. Findings: According to numerical analysis, both mathematical models solved the instances of up to 20 jobs and 80 machines optimally for sequence-independent setup-times jointed to processing time, and sequence-independent disjointed from processing time problems. However, generally speaking, the mathematical model based on predecessor jobs was more efficient than another mathematical model, especially in terms of run time. Moreover, the proposed fix and relax-based heuristic algorithm solved instances of up to 20 machines and 190 jobs for the disjointed setup times problem, and up to 20 and 220 instances for the jointed setup times problem. It should be noted that all instances were generated analogously to the literature. Research limitations/implications: A vast number of exogenous factors contributed to the scheduling problems in the real world, which can disturb the scheduling process easily, frequent power outages, machine breakdown, and operator absence. Besides, considering all the real world's possibilities raises extreme complexity in problems. Therefore, similar to other studies, some assumptions were considered as follows: - machines are always available at all times; - idle is allowable for machines; - the energy consumption rate of various machines is different for each job; - each machine's energy consumption rate during processing and setups is different for each job, it is assumed as constant; - preemption is not allowed in the job's processing and setups; - all jobs are available at the beginning of the planning horizon; and - each machine can process or do the setup for only one job at a time. Practical implications Given that unrelated parallel machines are one of the most practical scheduling environments, this article can be effective in production sites and operation lines that contain such a kind of machine. Besides, unrelated parallel machines cover identical and related parallel machines. Consequently, this paper is the building blocks of cost-effective and environmentally friendly scheduling programs. Also, the application of unrelated parallel machines is not merely restricted to production problems. In other words, unrelated parallel machine scheduling problems can be used in other real-world cases, such as airplane scheduling and elevator scheduling. Originality/value - In this paper, unrelated parallel machine energy-efficient scheduling has been addressed considering sequence-independent setup times. Since it was a common belief that sequence-independent setup times could be included in processing times, sequence-independent setup times have been neglected so far. However, in this innovative study for the first time, an unrelated parallel machine energy efficient problem was investigated with sequence-independent setup times. Mathematical programming models and a heuristic algorithm were proposed for such a practical problem. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
44. A NOTE ON LINEAR PROGRAMMING AND CAPITAL BUDGETING.
- Author
-
MYERS, STEWART C.
- Subjects
CAPITAL budget ,LINEAR programming ,MATHEMATICAL models of capital ,RATIONING ,MATHEMATICAL models of finance ,MATHEMATICAL programming - Abstract
This paper is the latest chapter in the controversy begun by William H. Bautool and Richard E. Quandt in their criticism of Weingartner's work on capital budgeting under capital rationing. A thorough review and partial resolution of the matter has been offered in recent articles by Willard T. Carleton and Edwin J. Elton. My purpose here is to try to complete the job. [ABSTRACT FROM AUTHOR]
- Published
- 1972
- Full Text
- View/download PDF
45. ABRAHAM CHARNES AND W. W. COOPER (ET AL.): A BRIEF HISTORY OF A LONG COLLABORATION IN DEVELOPING INDUSTRIAL USES OF LINEAR PROGRAMMING.
- Author
-
Cooper, W. W.
- Subjects
LINEAR programming ,MANAGEMENT science ,MATHEMATICAL programming ,OPERATIONS research ,INDUSTRIAL engineering - Abstract
This paper describes a research strategy and its results, which guided a 40+ year collaboration between Abraham Charnes and William W. Cooper, which was initiated in a research center established at the (then) new Graduate School of Industrial Administration at Carnegie Institute of Technology (now Carnegie Mellon University). Initiated in collaboration with Bob Mellon of Gulf Oil Company, this strategy involved on-site collaborations with company personnel in more than 100 different companies and government agencies. An appendix to this paper describes the efforts of another team working from the same research center. This team, consisting of Charles Holt, Franco Modigliani, John Muth, and Herbert A. Simon, used a different research strategy with an accompanying application that also had important impacts on operations research/management science and other disciplines. [ABSTRACT FROM AUTHOR]
- Published
- 2002
- Full Text
- View/download PDF
46. Linear Integer Programming Model as Mathematical Ware for an Optimal Flow Production Planning System at Operational Scheduling Stage.
- Author
-
Kibzun, A. I. and Rasskazova, V. A.
- Subjects
LINEAR programming ,PRODUCTION planning ,MATHEMATICAL programming ,MATHEMATICAL models ,IRON metallurgy ,INTEGER programming ,INTEGERS - Abstract
The problem of optimal flow production planning at the operational scheduling stage is being studied, using the example of the out-of-furnace department of a converter-based steel-making production in the iron metallurgy industry. To solve this problem, a linear integer programming model is proposed, which fully describes the specifics of the investigated technological processes. A major advantage of this approach is its scalability for solving related optimization problems in the industry of plant logistics, as well as flexibility in adapting to changes and fine-tuning the system of constraints and objective function. The software implementation of the developed model forms the basis of the operational scheduling module of the optimal flow production planning system, which is used for a large-scale computational experiment on real-world data. [ABSTRACT FROM AUTHOR]
- Published
- 2023
- Full Text
- View/download PDF
47. Optimization of Earthmoving Operations Planning: A Novel Approach Considering Interferences.
- Author
-
de Lima, Roberto X., Nobre Júnior, Ernesto F., and Fernandes, Pedro G. P. S.
- Subjects
LINEAR programming ,COST control ,MATHEMATICAL optimization ,DISTRIBUTION planning ,BUDGET cuts ,CONSTRUCTION project management ,RIVER conservation - Abstract
The purpose of this paper is to present an optimization model for planning the distribution of materials in earthmoving operations, considering possible interferences between cut-and-fill sections such as rivers, vegetation, topographical features, or expropriations. The earth allocation problem incorporating interferences was modeled as a linear programming problem, aiming to minimize the total earthmoving cost while considering the constraints related to volume balance, construction project duration, and time for the release of traffic. The proposed linear programming model was run by an integrated system, using Excel for data analysis and IBM CPLEX as the optimizer. The mathematical model was evaluated by a sensitivity analysis and validated by a real-world project of a dam access road in the state of Ceará, Brazil. The unit costs and productivity rates used in the fictional example and in the real-world application followed the referential cost system created by Ceará's Secretariat of Infrastructure (SEINFRA-CE). The proposed optimization model achieved reasonable processing times for all tested applications, presenting itself as a viable and efficient option for planning earthmoving operations. Furthermore, the linear programming approach provided a 2.12% cost reduction for the real-world case study, when comparing the optimized solution and original budget. This study explored the problem of earth allocation with interferences using a linear programming approach, while avoiding complex modeling issues found in recent literature. As a result, this paper proposes a user-friendly optimization system that can be easily utilized by construction companies and departments. [ABSTRACT FROM AUTHOR]
- Published
- 2021
- Full Text
- View/download PDF
48. Generation Capacity Expansion Planning Under Hydro Uncertainty Using Stochastic Mixed Integer Programming and Scenario Reduction.
- Author
-
Gil, Esteban, Aravena, Ignacio, and Cardenas, Raul
- Subjects
MATHEMATICAL programming ,STOCHASTIC analysis ,MATHEMATICAL optimization ,INDUSTRIAL costs ,UNCERTAINTY - Abstract
Generation capacity expansion planning (GCEP) is the process of deciding on a set of optimal new investments in generation capacity to adequately supply future loads, while satisfying technical and reliability constraints. This paper shows the application of stochastic mixed-integer programming (SMIP) to account for hydrological uncertainty in GCEP for the Chilean Central Interconnected System, using a two-stage SMIP multi-period model with investments and optimal power flow (OPF). The substantial computational challenges posed by GCEP imply compromising between the detail of the stochastic hydrological variables and the detail of the OPF. We selected a subset of hydrological scenarios to represent the historical hydro variability using moment-based scenario reduction techniques. The tradeoff between modeling accuracy and computational complexity was explored both regarding the simplification of the MIP problem and the differences in the variables of interest. Using a simplified OPF model, we found the difference of using a subset of hydro scenarios to be small when compared with using a full representation of the stochastic variable. Overall, SMIP with scenario reduction provided optimal capacity expansion plans whose investment plus expected operational costs were between 1.3% and 1.9% cheaper than using a deterministic approach and proved to be more robust to hydro variability. [ABSTRACT FROM PUBLISHER]
- Published
- 2015
- Full Text
- View/download PDF
49. A novel model for the integrated planning of part quality inspection and preventive maintenance in a linear-deteriorating serial multi-stage manufacturing system.
- Author
-
Rezaei-Malek, M., Tavakkoli-Moghaddam, R., Siadat, A., and Dantan, J.-Y.
- Subjects
MIXED integer linear programming ,MATHEMATICAL programming ,MAINTENANCE ,INSPECTION & review ,LINEAR programming - Abstract
This paper presents a mixed-integer linear mathematical programming model for the integrated planning problem of the part quality inspection and preventive maintenance activities in serial multi-stage manufacturing system. The model concurrently determines the right time and place for performing the above-mentioned activities while the production stages are linearly deteriorating. These two decisions are made while the model is to minimize the total cost including the production, maintenance, inspection, scrap, replacement, and the penalty of shipped defective items to customer(s). A numerical example and a real case study are investigated to validate and verify the proposed model. The results show that the determination of inspection locations along a manufacturing line in different periods of time regarding the impact of preventive maintenance activities on defective production probability results in a more efficient manufacturing system. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF
50. Index tracking with controlled number of assets using a hybrid heuristic combining genetic algorithm and non-linear programming.
- Author
-
Sant'Anna, Leonardo, Filomena, Tiago, Guedes, Pablo, and Borenstein, Denis
- Subjects
TRACKING algorithms ,INDEXES ,LINEAR programming ,MATHEMATICAL programming ,GENETIC algorithms - Abstract
In this paper, we discuss the index tracking strategy using mathematical programming. First, we use a non-linear programming formulation for the index tracking problem, considering a limited number of assets. Since the problem is difficult to be solved in reasonable time by commercial mathematical packages, we apply a hybrid solution approach, combining mathematical programming and genetic algorithm. We show the efficiency of the proposed approach comparing the results with optimal solutions, with previous developed methods, and from real-world market indexes. The computational experiments focus on Ibovespa (the most important Brazilian market index), but we also present results for consolidated markets such as S&P 100 (USA), FTSE 100 (UK) and DAX (Germany). The proposed framework shows its ability to obtain very good results (gaps from the optimal solution smaller than 5 % in 8 min of CPU time) even for a highly volatile index from a developing country. [ABSTRACT FROM AUTHOR]
- Published
- 2017
- Full Text
- View/download PDF
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.