Relevant bibliographies by topics / Combinatorial and linear optimization

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Combinatorial and linear optimization'

Author: Grafiati
Published: 30 November 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'Combinatorial and linear optimization.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "Combinatorial and linear optimization"

1

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
5

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Combinatorial and linear optimization"

1

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.

Full text
Abstract:
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

APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
4

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
6

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.

Full text
Abstract:

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.

APA, Harvard, Vancouver, ISO, and other styles
7

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/.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
8

Weltge, Stefan [Verfasser], and 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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
Abstract:
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
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Combinatorial and linear optimization"

1

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Combinatorial and linear optimization"

1

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Combinatorial and linear optimization"

1

Ma, Hyunjun, and Q.-Han Park. "Constraint-Driven Method for Combinatorial Optimization." In 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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Gadallah, M. H., and H. A. ElMaraghy. "A New Algorithm for Combinatorial Optimization." In 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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Quan, Ning, and Harrison Kim. "A Tight Upper Bound for Grid-Based Wind Farm Layout Optimization." In 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.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Combinatorial and linear optimization"

1

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Combinatorial and linear optimization' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography