Bibliografías temáticas / Combinatorial and linear optimization

Índice

Artículos de revistas
Tesis
Libros
Capítulos de libros
Actas de conferencias
Informes

Literatura académica sobre el tema "Combinatorial and linear optimization"

Autor: Grafiati

Publicado: 30 de noviembre de 2024

Crea una cita precisa en los estilos APA, MLA, Chicago, Harvard y otros

Elija tipo de fuente:

Consulte las listas temáticas de artículos, libros, tesis, actas de conferencias y otras fuentes académicas sobre el tema "Combinatorial and linear optimization".

Junto a cada fuente en la lista de referencias hay un botón "Agregar a la bibliografía". Pulsa este botón, y generaremos automáticamente la referencia bibliográfica para la obra elegida en el estilo de cita que necesites: APA, MLA, Harvard, Vancouver, Chicago, etc.

También puede descargar el texto completo de la publicación académica en formato pdf y leer en línea su resumen siempre que esté disponible en los metadatos.

Artículos de revistas sobre el tema "Combinatorial and linear optimization"

Yannakakis, Mihalis. "Expressing combinatorial optimization problems by Linear Programs". Journal of Computer and System Sciences 43, n.º 3 (diciembre de 1991): 441–66. http://dx.doi.org/10.1016/0022-0000(91)90024-y.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Donets, Georgy y Vasyl Biletskyi. "On Some Optimization Problems on Permutations". Cybernetics and Computer Technologies, n.º 1 (30 de junio de 2022): 5–10. http://dx.doi.org/10.34229/2707-451x.22.1.1.

Texto completo

Resumen

Numerous studies consider combinatorial optimization problems and their solution methods, since a large number of practical problems are described by means of combinatorial optimization models. Among these problems, the most prominent ones are function optimization problems on combinatorial configurations. Many of the studies mentioned above propose approaches and describe methods to solve combinatorial optimization problems for linear and fractionally linear functions on combinatorial sets such as permutations and arrangements. This work describes new approaches and methods to solve some maximization problems for linear, fractionally linear and quadratic functions on permutation set. Algorithms for solving these problems are given. For linear function, we provide a considerably easy method to find the permutation on which the function attains its maximum value. We describe the general algorithm to find fractionally linear function maximum. We consider the cases in which variables of numerator and denominator do not intersect, and when the numerator function and the denominator function have one common variable. We also describe the case in which the numerator function and the denominator function in total have incomplete variable list, i.e. when the total quantity of variables is less than the quantity of numbers in the permutation set. As for solving the problem of finding quadratic function maximum on permutation set, it turned out that there is no universal algorithm to solve this problem for any quadratic function. In this paper, we describe a method of finding maximum on permutation set for quadratic function consisting of two items. We provide examples of solving the considered optimization problems. Keywords: function, permutation, set, transposition, coefficients.

Los estilos APA, Harvard, Vancouver, ISO, etc.

DE FARIAS, I. R., E. L. JOHNSON y G. L. NEMHAUSER. "Branch-and-cut for combinatorial optimization problems without auxiliary binary variables". Knowledge Engineering Review 16, n.º 1 (marzo de 2001): 25–39. http://dx.doi.org/10.1017/s0269888901000030.

Texto completo

Resumen

Many optimisation problems involve combinatorial constraints on continuous variables. An example of a combinatorial constraint is that at most one variable in a group of nonnegative variables may be positive. Traditionally, in the mathematical programming community, such problems have been modeled as mixed-integer programs by introducing auxiliary binary variables and additional constraints. Because the number of variables and constraints becomes larger and the combinatorial structure is not used to advantage, these mixed-integer programming models may not be solved satisfactorily, except for small instances. Traditionally, constraint programming approaches to such problems keep and use the combinatorial structure, but do not use linear programming bounds in the search for an optimal solution. Here we present a branch-and-cut approach that considers the combinatorial constraints without the introduction of binary variables. We review the development of this approach and show how strong constraints can be derived using ideas from polyhedral combinatorics. To illustrate the ideas, we present a production scheduling model that arises in the manufacture of fibre optic cables.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Barbolina, Tetiana. "Estimates of objective function minimum for solving linear fractional unconstrained combinatorial optimization problems on arrangements". Physico-mathematical modelling and informational technologies, n.º 32 (6 de julio de 2021): 32–36. http://dx.doi.org/10.15407/fmmit2021.32.055.

Texto completo

Resumen

The paper is devoted to the study of one class of Euclidean combinatorial optimization problems — combinatorial optimization problems on the general set of arrangements with linear fractional objective function and without additional (non-combinatorial) constraints. The paper substantiates the improvement of the polynomial algorithm for solving the specified class of problems. This algorithm foresees solving a finite sequence of linear unconstrained problems of combinatorial optimization on arrangements. The modification of the algorithm is based on the use of estimates of the objective function on the feasible set. This allows to exclude some of the problems from consideration and reduce the number of problems to be solved. The numerical experiments confirm the practical efficiency of the proposed approach.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Pichugina, Oksana y Liudmyla Koliechkina. "Linear constrained combinatorial optimization on well-described sets". IOP Conference Series: Materials Science and Engineering 1099, n.º 1 (1 de marzo de 2021): 012064. http://dx.doi.org/10.1088/1757-899x/1099/1/012064.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Donets, G. A. y V. I. Biletskyi. "On the Problem of a Linear Function Localization on Permutations". Cybernetics and Computer Technologies, n.º 2 (24 de julio de 2020): 14–18. http://dx.doi.org/10.34229/2707-451x.20.2.2.

Texto completo

Resumen

Combinatorial optimization problems and methods of their solution have been a subject of numerous studies, since a large number of practical problems are described by combinatorial optimization models. Many studies consider approaches to and describe methods of solution for combinatorial optimization problems with linear or fractionally linear target functions on combinatorial sets such as permutations and arrangements. Studies consider solving combinatorial problems by means of well-known methods, as well as developing new methods and algorithms of searching a solution. We describe a method of solving a problem of a linear target function localization on a permutation set. The task is to find those locally admissible permutations on the permutation set, for which the linear function possesses a given value. In a general case, this problem may have no solutions at all. In the article, we propose a newly developed method that allows us to obtain a solution of such a problem (in the case that such solution exists) by the goal-oriented seeking for locally admissible permutations with a minimal enumeration that is much less than the number of all possible variants. Searching for the solution comes down to generating various permutations and evaluating them. Evaluation of each permutation includes two steps. The first step consists of function decreasing by transposing the numbers in the first n – 3 positions, and the second step is evaluation of the permutations for the remaining three numbers. Then we analyze the correlation (which is called balance) to define whether the considered permutation is the solution or not. In our article, we illustrate the localization method by solving the problem for n = 5. Keywords: localization, linear function, permutation, transposition, balance, position.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Engau, Alexander, Miguel F. Anjos y Anthony Vannelli. "On Interior-Point Warmstarts for Linear and Combinatorial Optimization". SIAM Journal on Optimization 20, n.º 4 (enero de 2010): 1828–61. http://dx.doi.org/10.1137/080742786.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Chung, Sung-Jin, Horst W. Hamacher, Francesco Maffioli y Katta G. Murty. "Note on combinatorial optimization with max-linear objective functions". Discrete Applied Mathematics 42, n.º 2-3 (abril de 1993): 139–45. http://dx.doi.org/10.1016/0166-218x(93)90043-n.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Borissova, Daniela, Ivan Mustakerov y Lyubka Doukovska. "Predictive Maintenance Sensors Placement by Combinatorial Optimization". International Journal of Electronics and Telecommunications 58, n.º 2 (1 de junio de 2012): 153–58. http://dx.doi.org/10.2478/v10177-012-0022-6.

Texto completo

Resumen

Predictive Maintenance Sensors Placement by Combinatorial Optimization The strategy of predictive maintenance monitoring is important for successful system damage detection. Maintenance monitoring utilizes dynamic response information to identify the possibility of damage. The basic factors of faults detection analysis are related to properties of the structure under inspection, collect the signals and appropriate signals processing. In vibration control, structures response sensing is limited by the number of sensors or the number of input channels of the data acquisition system. An essential problem in predictive maintenance monitoring is the optimal sensor placement. The paper addresses that problem by using mixed integer linear programming tasks solving. The proposed optimal sensors location approach is based on the difference between sensor information if sensor is present and information calculated by linear interpolation if sensor is not present. The tasks results define the optimal sensors locations for a given number of sensors. The results of chosen sensors locations give as close as possible repeating the curve of structure dynamic response function. The proposed approach is implemented in an algorithm for predictive maintenance and the numerical results indicate that together with intelligent signal processing it could be suitable for practical application.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Mandi, Jayanta, Emir Demirovi?, Peter J. Stuckey y Tias Guns. "Smart Predict-and-Optimize for Hard Combinatorial Optimization Problems". Proceedings of the AAAI Conference on Artificial Intelligence 34, n.º 02 (3 de abril de 2020): 1603–10. http://dx.doi.org/10.1609/aaai.v34i02.5521.

Texto completo

Resumen

Combinatorial optimization assumes that all parameters of the optimization problem, e.g. the weights in the objective function, are fixed. Often, these weights are mere estimates and increasingly machine learning techniques are used to for their estimation. Recently, Smart Predict and Optimize (SPO) has been proposed for problems with a linear objective function over the predictions, more specifically linear programming problems. It takes the regret of the predictions on the linear problem into account, by repeatedly solving it during learning. We investigate the use of SPO to solve more realistic discrete optimization problems. The main challenge is the repeated solving of the optimization problem. To this end, we investigate ways to relax the problem as well as warm-starting the learning and the solving. Our results show that even for discrete problems it often suffices to train by solving the relaxation in the SPO loss. Furthermore, this approach outperforms the state-of-the-art approach of Wilder, Dilkina, and Tambe. We experiment with weighted knapsack problems as well as complex scheduling problems, and show for the first time that a predict-and-optimize approach can successfully be used on large-scale combinatorial optimization problems.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Más fuentes

Tesis sobre el tema "Combinatorial and linear optimization"

Salazar-Neumann, Martha. "Advances in robust combinatorial optimization and linear programming". Doctoral thesis, Universite Libre de Bruxelles, 2010. http://hdl.handle.net/2013/ULB-DIPOT:oai:dipot.ulb.ac.be:2013/210192.

Texto completo

Resumen

La construction de modèles qui protègent contre les incertitudes dans les données, telles que la variabilité de l'information et l'imprécision est une des principales préoccupations en optimisation sous incertitude. L'incertitude peut affecter différentes domaines, comme le transport, les télécommunications, la finance, etc. ainsi que les différentes parts d'un problème d'optimisation, comme les coefficients de la fonction objectif et /ou les contraintes. De plus, l'ensemble des données incertaines peut être modélisé de différentes façons, comme sous ensembles compactes et convexes de l´espace réel de dimension n, polytopes, produits Cartésiens des intervalles, ellipsoïdes, etc.

Une des approches possibles pour résoudre des tels problèmes est de considérer les versions minimax regret, pour lesquelles résoudre un problème sous incertitude revient à trouver une solution qui s'écarte le moins possible de la valeur solution optimale dans tout les cas.

Dans le cas des incertitudes définies par intervalles, les versions minimax regret de nombreux problèmes combinatoires polynomiaux sont NP-difficiles, d'ou l'importance d'essayer de réduire l'espace des solutions. Dans ce contexte, savoir quand un élément du problème, représenté par une variable, fait toujours ou jamais partie d'une solution optimal pour toute réalisation des données (variables 1-persistentes et 0-persistentes respectivement), constitue une manière de réduire la taille du problème. Un des principaux objectifs de cette thèse est d'étudier ces questions pour quelques problèmes d'optimisation combinatoire sous incertitude.

Nous étudions les versions minimax regret du problème du choix de p éléments parmi m, de l'arbre couvrant minimum et des deux problèmes de plus court chemin. Pour de tels problèmes, dans le cas des incertitudes définis par intervalles, nous étudions le problème de trouver les variables 1- et 0-persistentes. Nous présentons une procédure de pre-traitement du problème, lequel réduit grandement la taille des formulations des versions de minimax regret.

Nous nous intéressons aussi à la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont incertains et l'ensemble des données incertaines est polyédral. Dans le cas où l'ensemble des incertitudes est défini par des intervalles, le problème de trouver le regret maximum est NP-difficile. Nous présentons des cas spéciaux ou les problèmes de maximum regret et de minimax regret sont polynomiaux. Dans le cas où l´ensemble des incertitudes est défini par un polytope, nous présentons un algorithme pour trouver une solution exacte au problème de minimax regret et nous discutons les résultats numériques obtenus dans un grand nombre d´instances générées aléatoirement.

Nous étudions les relations entre le problème de 1-centre continu et la version minimax regret du problème de programmation linéaire dans le cas où les coefficients de la fonction objectif sont évalués à l´aide des intervalles. En particulier, nous décrivons la géométrie de ce dernier problème, nous généralisons quelques résultats en théorie de localisation et nous donnons des conditions sous lesquelles certaines variables peuvet être éliminées du problème. Finalement, nous testons ces conditions dans un nombre d´instances générées aléatoirement et nous donnons les conclusions.
Doctorat en sciences, Orientation recherche opérationnelle
info:eu-repo/semantics/nonPublished

Los estilos APA, Harvard, Vancouver, ISO, etc.

Iemets, O. O. y T. M. Barbolina. "Linear-fractional combinatorial optimization problems: model and solving". Thesis, Sumy State University, 2016. http://essuir.sumdu.edu.ua/handle/123456789/46962.

Texto completo

Resumen

Euclidean problems of linear-fractional combinatorial optimization on arrangements are discussed. Authors propose the model of practical problem. Also the polynomial algorithm for solving linear-fractional combinatorial optimization problems on arrangements is discussed.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Cheng, Jianqiang. "Stochastic Combinatorial Optimization". Thesis, Paris 11, 2013. http://www.theses.fr/2013PA112261.

Texto completo

Resumen

Dans cette thèse, nous étudions trois types de problèmes stochastiques : les problèmes avec contraintes probabilistes, les problèmes distributionnellement robustes et les problèmes avec recours. Les difficultés des problèmes stochastiques sont essentiellement liées aux problèmes de convexité du domaine des solutions, et du calcul de l’espérance mathématique ou des probabilités qui nécessitent le calcul complexe d’intégrales multiples. A cause de ces difficultés majeures, nous avons résolu les problèmes étudiées à l’aide d’approximations efficaces.Nous avons étudié deux types de problèmes stochastiques avec des contraintes en probabilités, i.e., les problèmes linéaires avec contraintes en probabilité jointes (LLPC) et les problèmes de maximisation de probabilités (MPP). Dans les deux cas, nous avons supposé que les variables aléatoires sont normalement distribués et les vecteurs lignes des matrices aléatoires sont indépendants. Nous avons résolu LLPC, qui est un problème généralement non convexe, à l’aide de deux approximations basée sur les problèmes coniques de second ordre (SOCP). Sous certaines hypothèses faibles, les solutions optimales des deux SOCP sont respectivement les bornes inférieures et supérieures du problème du départ. En ce qui concerne MPP, nous avons étudié une variante du problème du plus court chemin stochastique contraint (SRCSP) qui consiste à maximiser la probabilité de la contrainte de ressources. Pour résoudre ce problème, nous avons proposé un algorithme de Branch and Bound pour calculer la solution optimale. Comme la relaxation linéaire n’est pas convexe, nous avons proposé une approximation convexe efficace. Nous avons par la suite testé nos algorithmes pour tous les problèmes étudiés sur des instances aléatoires. Pour LLPC, notre approche est plus performante que celles de Bonferroni et de Jaganathan. Pour MPP, nos résultats numériques montrent que notre approche est là encore plus performante que l’approximation des contraintes probabilistes individuellement.La deuxième famille de problèmes étudiés est celle relative aux problèmes distributionnellement robustes où une partie seulement de l’information sur les variables aléatoires est connue à savoir les deux premiers moments. Nous avons montré que le problème de sac à dos stochastique (SKP) est un problème semi-défini positif (SDP) après relaxation SDP des contraintes binaires. Bien que ce résultat ne puisse être étendu au cas du problème multi-sac-à-dos (MKP), nous avons proposé deux approximations qui permettent d’obtenir des bornes de bonne qualité pour la plupart des instances testées. Nos résultats numériques montrent que nos approximations sont là encore plus performantes que celles basées sur les inégalités de Bonferroni et celles plus récentes de Zymler. Ces résultats ont aussi montré la robustesse des solutions obtenues face aux fluctuations des distributions de probabilités. Nous avons aussi étudié une variante du problème du plus court chemin stochastique. Nous avons prouvé que ce problème peut se ramener au problème de plus court chemin déterministe sous certaine hypothèses. Pour résoudre ce problème, nous avons proposé une méthode de B&B où les bornes inférieures sont calculées à l’aide de la méthode du gradient projeté stochastique. Des résultats numériques ont montré l’efficacité de notre approche. Enfin, l’ensemble des méthodes que nous avons proposées dans cette thèse peuvent s’appliquer à une large famille de problèmes d’optimisation stochastique avec variables entières
In this thesis, we studied three types of stochastic problems: chance constrained problems, distributionally robust problems as well as the simple recourse problems. For the stochastic programming problems, there are two main difficulties. One is that feasible sets of stochastic problems is not convex in general. The other main challenge arises from the need to calculate conditional expectation or probability both of which are involving multi-dimensional integrations. Due to the two major difficulties, for all three studied problems, we solved them with approximation approaches.We first study two types of chance constrained problems: linear program with joint chance constraints problem (LPPC) as well as maximum probability problem (MPP). For both problems, we assume that the random matrix is normally distributed and its vector rows are independent. We first dealt with LPPC which is generally not convex. We approximate it with two second-order cone programming (SOCP) problems. Furthermore under mild conditions, the optimal values of the two SOCP problems are a lower and upper bounds of the original problem respectively. For the second problem, we studied a variant of stochastic resource constrained shortest path problem (called SRCSP for short), which is to maximize probability of resource constraints. To solve the problem, we proposed to use a branch-and-bound framework to come up with the optimal solution. As its corresponding linear relaxation is generally not convex, we give a convex approximation. Finally, numerical tests on the random instances were conducted for both problems. With respect to LPPC, the numerical results showed that the approach we proposed outperforms Bonferroni and Jagannathan approximations. While for the MPP, the numerical results on generated instances substantiated that the convex approximation outperforms the individual approximation method.Then we study a distributionally robust stochastic quadratic knapsack problems, where we only know part of information about the random variables, such as its first and second moments. We proved that the single knapsack problem (SKP) is a semedefinite problem (SDP) after applying the SDP relaxation scheme to the binary constraints. Despite the fact that it is not the case for the multidimensional knapsack problem (MKP), two good approximations of the relaxed version of the problem are provided which obtain upper and lower bounds that appear numerically close to each other for a range of problem instances. Our numerical experiments also indicated that our proposed lower bounding approximation outperforms the approximations that are based on Bonferroni's inequality and the work by Zymler et al.. Besides, an extensive set of experiments were conducted to illustrate how the conservativeness of the robust solutions does pay off in terms of ensuring the chance constraint is satisfied (or nearly satisfied) under a wide range of distribution fluctuations. Moreover, our approach can be applied to a large number of stochastic optimization problems with binary variables.Finally, a stochastic version of the shortest path problem is studied. We proved that in some cases the stochastic shortest path problem can be greatly simplified by reformulating it as the classic shortest path problem, which can be solved in polynomial time. To solve the general problem, we proposed to use a branch-and-bound framework to search the set of feasible paths. Lower bounds are obtained by solving the corresponding linear relaxation which in turn is done using a Stochastic Projected Gradient algorithm involving an active set method. Meanwhile, numerical examples were conducted to illustrate the effectiveness of the obtained algorithm. Concerning the resolution of the continuous relaxation, our Stochastic Projected Gradient algorithm clearly outperforms Matlab optimization toolbox on large graphs

Los estilos APA, Harvard, Vancouver, ISO, etc.

Burer, Samuel A. "New algorithmic approaches for semidefinite programming with applications to combinatorial optimization". Diss., Georgia Institute of Technology, 2001. http://hdl.handle.net/1853/30268.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Sidford, Aaron Daniel. "Iterative methods, combinatorial optimization, and linear programming beyond the universal barrier". Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/99848.

Texto completo

Resumen

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, 2015.
Cataloged from PDF version of thesis.
Includes bibliographical references (pages 256-266).
In this thesis we consider fundamental problems in continuous and combinatorial optimization that occur pervasively in practice and show how to improve upon the best known theoretical running times for solving these problems across a broad range of parameters. Using and improving techniques from diverse disciplines including spectral graph theory, numerical analysis, data structures, and convex optimization we provide the first theoretical improvements in decades for multiple classic problems ranging from linear programming to linear system solving to maximum flow. Key results in this thesis include the following: -- Linear Programming: We provide the first general improvement to both the running time and convergence rate of polynomial time algorithms for solving linear programs in over 15 years. For a linear program with constraint matrix A, with z nonzero entries, and bit complexity L our algorithm runs in time [mathematical formula] -- Directed Maximum Flow: We provide an [mathematical formula] time algorithm for solving the-maximum flow problem on directed graphs with m edges, n vertices, and capacity ratio U improving upon the running time of [mathematical formula] achieved over 15 years ago by Goldberg and Rao. -- Undirected Approximate Flow: We provide one of the first almost linear time algorithms for approximately solving undirected maximum flow improving upon the previous fastest running time by a factor of [mathematical formula] for graphs with n vertices. -- Laplacian System Solvers: We improve upon the previous best known algorithms for solving Laplacian systems in standard unit cost RAM model, achieving a running time of [mathematical formula] for solving a Laplacian system of equations. -- Linear System Solvers: We obtain a faster asymptotic running time than conjugate gradient for solving a broad class of symmetric positive definite systems of equations. * More: We improve the running time for multiple problems including regression, generalized lossy flow, multicommodity flow, and more.
by Aaron Sidford.
Ph. D.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Björklund, Henrik. "Combinatorial Optimization for Infinite Games on Graphs". Doctoral thesis, Uppsala University, Department of Information Technology, 2005. http://urn.kb.se/resolve?urn=urn:nbn:se:uu:diva-4751.

Texto completo

Resumen

Games on graphs have become an indispensable tool in modern computer science. They provide powerful and expressive models for numerous phenomena and are extensively used in computer- aided verification, automata theory, logic, complexity theory, computational biology, etc.

The infinite games on finite graphs we study in this thesis have their primary applications in verification, but are also of fundamental importance from the complexity-theoretic point of view. They include parity, mean payoff, and simple stochastic games.

We focus on solving graph games by using iterative strategy improvement and methods from linear programming and combinatorial optimization. To this end we consider old strategy evaluation functions, construct new ones, and show how all of them, due to their structural similarities, fit into a unifying combinatorial framework. This allows us to employ randomized optimization methods from combinatorial linear programming to solve the games in expected subexponential time.

We introduce and study the concept of a controlled optimization problem, capturing the essential features of many graph games, and provide sufficent conditions for solvability of such problems in expected subexponential time.

The discrete strategy evaluation function for mean payoff games we derive from the new controlled longest-shortest path problem, leads to improvement algorithms that are considerably more efficient than the previously known ones, and also improves the efficiency of algorithms for parity games.

We also define the controlled linear programming problem, and show how the games are translated into this setting. Subclasses of the problem, more general than the games considered, are shown to belong to NP intersection coNP, or even to be solvable by subexponential algorithms.

Finally, we take the first steps in investigating the fixed-parameter complexity of parity, Rabin, Streett, and Muller games.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ferroni, Nicola. "Exact Combinatorial Optimization with Graph Convolutional Neural Networks". Master's thesis, Alma Mater Studiorum - Università di Bologna, 2019. http://amslaurea.unibo.it/17502/.

Texto completo

Resumen

Combinatorial optimization problems are typically tackled by the branch-and-bound paradigm. We propose to learn a variable selection policy for branch-and-bound in mixed-integer linear programming, by imitation learning on a diversified variant of the strong branching expert rule. We encode states as bipartite graphs and parameterize the policy as a graph convolutional neural network. Experiments on a series of synthetic problems demonstrate that our approach produces policies that can improve upon expert-designed branching rules on large problems, and generalize to instances significantly larger than seen during training.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Weltge, Stefan [Verfasser] y Volker [Akademischer Betreuer] Kaibel. "Sizes of linear descriptions in combinatorial optimization / Stefan Weltge. Betreuer: Volker Kaibel". Magdeburg : Universitätsbibliothek, 2015. http://d-nb.info/1082625868/34.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Wang, Xia. "Applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems". College Park, Md.: University of Maryland, 2008. http://hdl.handle.net/1903/8778.

Texto completo

Resumen

Thesis (Ph. D.) -- University of Maryland, College Park, 2008.
Thesis research directed by: Applied Mathematics & Statistics, and Scientific Computation Program. Title from t.p. of PDF. Includes bibliographical references. Published by UMI Dissertation Services, Ann Arbor, Mich. Also available in paper.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Chakrabarty, Deeparnab. "Algorithmic aspects of connectivity, allocation and design problems". Diss., Atlanta, Ga. : Georgia Institute of Technology, 2008. http://hdl.handle.net/1853/24659.

Texto completo

Resumen

Thesis (Ph.D.)--Computing, Georgia Institute of Technology, 2008.
Committee Chair: Vazirani, Vijay; Committee Member: Cook, William; Committee Member: Kalai, Adam; Committee Member: Tetali, Prasad; Committee Member: Thomas, Robin

Los estilos APA, Harvard, Vancouver, ISO, etc.

Más fuentes

Libros sobre el tema "Combinatorial and linear optimization"

Pardalos, P. M. Handbook of combinatorial optimization. New York: Springer, 2013.

Buscar texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Dingzhu, Du y Pardalos P. M. 1954-, eds. Handbook of combinatorial optimization. Boston: Kluwer Academic Publishers, 1998.

Buscar texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

MacGregor Smith, J. Combinatorial, Linear, Integer and Nonlinear Optimization Apps. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-75801-1.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Diaby, Moustapha. Advances in combinatorial optimization: Linear programming formulation of the traveling salesman and other hard combinatorial optimization problems. New Jersey: World Scientific, 2015.

Buscar texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Padberg, Manfred. Linear Optimization and Extensions. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999.

Buscar texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Gerhard, Reinelt y SpringerLink (Online service), eds. The Linear Ordering Problem: Exact and Heuristic Methods in Combinatorial Optimization. Berlin, Heidelberg: Springer-Verlag Berlin Heidelberg, 2011.

Buscar texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Strobach, Peter. Linear Prediction Theory: A Mathematical Basis for Adaptive Systems. Berlin, Heidelberg: Springer Berlin Heidelberg, 1990.

Buscar texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Jonas, Mockus, ed. Bayesian heuristic approach to discrete and global optimization: Algorithms, visualization, software, and applications. Dordrecht: Kluwer Academic Publishers, 1997.

Buscar texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Mahjoub, A. Ridha, Vangelis Markakis, Ioannis Milis y Vangelis Th Paschos, eds. Combinatorial Optimization. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-32147-4.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Korte, Bernhard y Jens Vygen. Combinatorial Optimization. Berlin, Heidelberg: Springer Berlin Heidelberg, 2018. http://dx.doi.org/10.1007/978-3-662-56039-6.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Más fuentes

Capítulos de libros sobre el tema "Combinatorial and linear optimization"

Akgül, Mustafa. "The Linear Assignment Problem". En Combinatorial Optimization, 85–122. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/978-3-642-77489-8_5.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Yang, Kai y Katta G. Murty. "Surrogate Constraint Methods for Linear Inequalities". En Combinatorial Optimization, 19–38. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/978-3-642-77489-8_2.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Dongarra, Jack y Jerzy Waśniewski. "High Performance Linear Algebra Package - LAPACK90". En Combinatorial Optimization, 241–53. Boston, MA: Springer US, 1999. http://dx.doi.org/10.1007/978-1-4613-3282-4_11.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Nemhauser, George y Laurence Wolsey. "Linear Programming". En Integer and Combinatorial Optimization, 27–49. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2014. http://dx.doi.org/10.1002/9781118627372.ch2.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Du, Ding-Zhu, Panos Pardalos, Xiaodong Hu y Weili Wu. "Linear Programming". En Introduction to Combinatorial Optimization, 129–74. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-10596-8_6.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Padberg, Manfred. "Combinatorial Optimization: An Introduction". En Linear Optimization and Extensions, 387–422. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999. http://dx.doi.org/10.1007/978-3-662-12273-0_10.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Alevras, Dimitres y Manfred W.Padberg. "Combinatorial Optimization: An Introduction". En Linear Optimization and Extensions, 323–58. Berlin, Heidelberg: Springer Berlin Heidelberg, 2001. http://dx.doi.org/10.1007/978-3-642-56628-8_10.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Pinar, Mustafa Ç. y Stavros A. Zenios. "Solving Large Scale Multicommodity Networks Using Linear—Quadratic Penalty Functions". En Combinatorial Optimization, 225–30. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/978-3-642-77489-8_12.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Bilbao, Jesús Mario. "Linear optimization methods". En Cooperative Games on Combinatorial Structures, 27–63. Boston, MA: Springer US, 2000. http://dx.doi.org/10.1007/978-1-4615-4393-0_2.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

den Hertog, D., C. Roos y T. Terlaky. "The Linear Complementary Problem, Sufficient Matrices and the Criss-Cross Method". En Combinatorial Optimization, 253–57. Berlin, Heidelberg: Springer Berlin Heidelberg, 1992. http://dx.doi.org/10.1007/978-3-642-77489-8_18.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Actas de conferencias sobre el tema "Combinatorial and linear optimization"

Ma, Hyunjun y Q.-Han Park. "Constraint-Driven Method for Combinatorial Optimization". En 2024 Conference on Lasers and Electro-Optics Pacific Rim (CLEO-PR), 1–2. IEEE, 2024. http://dx.doi.org/10.1109/cleo-pr60912.2024.10676554.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Yannakakis, Mihalis. "Expressing combinatorial optimization problems by linear programs". En the twentieth annual ACM symposium. New York, New York, USA: ACM Press, 1988. http://dx.doi.org/10.1145/62212.62232.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Baioletti, Marco, Alfredo Milani y Valentino Santucci. "Linear Ordering Optimization with a Combinatorial Differential Evolution". En 2015 IEEE International Conference on Systems, Man, and Cybernetics (SMC). IEEE, 2015. http://dx.doi.org/10.1109/smc.2015.373.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Jin, Chen, Qiang Fu, Huahua Wang, Ankit Agrawal, William Hendrix, Wei-keng Liao, Md Mostofa Ali Patwary, Arindam Banerjee y Alok Choudhary. "Solving combinatorial optimization problems using relaxed linear programming". En the 2nd International Workshop. New York, New York, USA: ACM Press, 2013. http://dx.doi.org/10.1145/2501221.2501227.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Louchet, J., R. Mathurin y B. Rottembourg. "Combinatorial optimization and linear prediction approaches to rain cell tracking". En 26th AIPR Workshop: Exploiting New Image Sources and Sensors, editado por J. Michael Selander. SPIE, 1998. http://dx.doi.org/10.1117/12.300045.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Gadallah, M. H. y H. A. ElMaraghy. "A New Algorithm for Combinatorial Optimization". En ASME 1995 Design Engineering Technical Conferences collocated with the ASME 1995 15th International Computers in Engineering Conference and the ASME 1995 9th Annual Engineering Database Symposium. American Society of Mechanical Engineers, 1995. http://dx.doi.org/10.1115/detc1995-0059.

Texto completo

Resumen

Abstract A new algorithm for combinatorial search optimization is developed. This algorithm is based on orthogonal arrays as planning schemes and search graph techniques as representation schemes. Based on the algorithm, a discrete formulation is given to model two search domains. As an application, the algorithm is used to deal with the problem of least cost tolerance allocation with optimum process selection. Studies are performed to compare between different orthogonal array and column assignment and number of design levels with respect to optimum. The proposed algorithm is capable of dealing with continuous, discrete linear and nonlinear functions and is validated by test cases versus other local and global search methods.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Beniwal, Gautam y Mohammad Rizwanullah. "Combinatorial Optimization of Non-linear Multicommodity Network Flow Using Pseudo Quasi-Newton Method". En 2022 International Conference on Computational Modelling, Simulation and Optimization (ICCMSO). IEEE, 2022. http://dx.doi.org/10.1109/iccmso58359.2022.00041.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Drori, Iddo, Anant Kharkar, William R. Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P. Williamson y Madeleine Udell. "Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time". En 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA). IEEE, 2020. http://dx.doi.org/10.1109/icmla51294.2020.00013.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Quan, Ning y Harrison Kim. "A Tight Upper Bound for Grid-Based Wind Farm Layout Optimization". En ASME 2016 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/detc2016-59712.

Texto completo

Resumen

This paper uses the method developed by Billionnet et al. (1999) to obtain tight upper bounds on the optimal values of mixed integer linear programming (MILP) formulations in grid-based wind farm layout optimization. The MILP formulations in grid-based wind farm layout optimization can be seen as linearized versions of the 0-1 quadratic knapsack problem (QKP) in combinatorial optimization. The QKP is NP-hard, which means the MILP formulations remain difficult problems to solve, especially for large problems with grid sizes of more than 500 points. The upper bound method proposed by Billionnet et al. is particularly well-suited for grid-based wind farm layout optimization problems, and was able to provide tight optimality gaps for a range of numerical experiments with up to 1296 grid points. The results of the numerical experiments also suggest that the greedy algorithm is a promising solution method for large MILP formulations in grid-based layout optimization that cannot be solved using standard branch and bound solvers.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Mitra, Mainak, Alparslan Emrah Bayrak, Stefano Zucca y Bogdan I. Epureanu. "A Sensitivity Based Heuristic for Optimal Blade Arrangement in a Linear Mistuned Rotor". En ASME Turbo Expo 2018: Turbomachinery Technical Conference and Exposition. American Society of Mechanical Engineers, 2018. http://dx.doi.org/10.1115/gt2018-75542.

Texto completo

Resumen

This paper investigates methodologies for finding optimal or near-optimal blade arrangements in a bladed disk with inserted blades for minimizing or maximizing blade response amplification due to mistuning in material properties of the blades. The mistuning in the blades is considered to be known, and only their arrangement is modifiable. Hence, this is a problem in discrete optimization, particularly combinatorial optimization where the objective of response amplification is a nonlinear function of the blade arrangement. Previous studies have treated mistuning as a continuous parameter to analyze its effects on the response amplification. Sensitivity metrics have proven to be an important tool in quantifying the effects of mistuning. One such sensitivity metric is used here to formulate an iterative heuristic approach to solve the optimization problem. A component mode mistuning reduced order model is used for fast evaluations of the dynamic responses of a bladed disk with a given blade arrangement. At any iteration the sensitivity of the maximum response of the current rotor design to changes in blade stiffnesses due to changes in the blade arrangement is used to predict the arrangement for the following iteration. In addition to the proposed sensitivity-based approach, we use genetic algorithms to find optimal arrangements and compare results with the heuristic approach.

Los estilos APA, Harvard, Vancouver, ISO, etc.

Informes sobre el tema "Combinatorial and linear optimization"

Bixby, Robert E. Notes on Combinatorial Optimization. Fort Belvoir, VA: Defense Technical Information Center, octubre de 1987. http://dx.doi.org/10.21236/ada455247.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Coffrin, Carleton James. Combinatorial Optimization on D-Wave. Office of Scientific and Technical Information (OSTI), junio de 2018. http://dx.doi.org/10.2172/1454977.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Radzik, Thomas. Newton's Method for Fractional Combinatorial Optimization,. Fort Belvoir, VA: Defense Technical Information Center, enero de 1992. http://dx.doi.org/10.21236/ada323687.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

GEORGE MASON UNIV FAIRFAX VA. Solving Large-Scale Combinatorial Optimization Problems. Fort Belvoir, VA: Defense Technical Information Center, agosto de 1996. http://dx.doi.org/10.21236/ada327597.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Hoffman, Karla L. Solution Procedures for Large-Scale Combinatorial Optimization. Fort Belvoir, VA: Defense Technical Information Center, agosto de 1993. http://dx.doi.org/10.21236/ada278242.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Plotkin, Serge. Research in Graph Algorithms and Combinatorial Optimization. Fort Belvoir, VA: Defense Technical Information Center, marzo de 1995. http://dx.doi.org/10.21236/ada292630.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Wets, Roger D. Parametric and Combinatorial Problems in Constrained Optimization. Fort Belvoir, VA: Defense Technical Information Center, marzo de 1993. http://dx.doi.org/10.21236/ada264229.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Shepherd, Bruce, Peter Winkler y Chandra Chekuri. Fundamentals of Combinatorial Optimization and Algorithm Design. Fort Belvoir, VA: Defense Technical Information Center, mayo de 2004. http://dx.doi.org/10.21236/ada423042.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Parekh, Ojas, Robert D. Carr y David Pritchard. LDRD final report : combinatorial optimization with demands. Office of Scientific and Technical Information (OSTI), septiembre de 2012. http://dx.doi.org/10.2172/1055603.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Jaillet, Patrick. Data-Driven Online and Real-Time Combinatorial Optimization. Fort Belvoir, VA: Defense Technical Information Center, octubre de 2013. http://dx.doi.org/10.21236/ada592939.

Texto completo

Los estilos APA, Harvard, Vancouver, ISO, etc.

Ofrecemos descuentos en todos los planes premium para autores cuyas obras están incluidas en selecciones literarias temáticas. ¡Contáctenos para obtener un código promocional único!