11 research outputs found
Gomory-chvatal cutting planes and the elementary closure of polyhedra
No full textThe elementary closure P'; of a polyhedrom P is the intersection of P with all its Gomory-Chvátal cutting planes. P'; is a rational polyhedron provided that P is rational. The Chvátal-Gomory procedure is the iterative application of the elementary closure operation to P. The Chvátal rank is the minimal number of iterations needed to obtain P_I. It is always finite, but already in |R² one can construct polytopes of arbitrary large Chvátal rank. We show that the Chvátal rank of polytopes contained in the n-dimensional 0/1 cube is O(n² log n) and prove the lower bound (1+E) n, for some E> 0. We show that the separation problem for the elementary closure of a rational polyhedron is NP-hard. This solves a problem posed by Schrijver. Last we consider the elementary closure in fixed dimension. the known bounds for the number of inequalities defining P'; are exponential, even fixed dimension. We show that the number of inequalities needed to describe the elementary closure of a rational polyhedron is polynomially bounded in fixed dimension. Finally, we present a polynomial algorithm in varying dimension, which computes cutting planes for a simplicial cone from this polynomial description in fixed dimension with a maximal degree of violation in a natural sense.DISOP
Experimental study of the AKS sorting network
No full textSorting networks are usually bound at a depth of O(log^2 n), since a perfect halver is of at least depth O(log n). However, the AKS Sorting Network, by Ajtai, Komlos and Szemeredi, can sort data with depth O(log n) by using so-called ε-halvers, which are of constant depth. Such ε-halvers are allowed to have some errors and will eventually be corrected by sending elements to a level above. In this thesis, a CPU and CUDA version are implemented following a paper by Vasek Chvatal and the original paper by Ajtai et al. Experiments are run on these versions to observe and improve parameters
The Intersection of Knapsack Polyhedra and Extensions
No full textThis paper introduces a scheme of deriving strong cutting planes for a general integer programming problem. The scheme is related to Chvatal-Gomory cutting planes and important special cases such as odd hole and clique inequalities for the stable set polyhedron or families of inequalities for the knapsack polyhedron. We analyze how relations between covering and incomparability numbers associated with the matrix can be used to bound coefficients in these inequalities. For the intersection of several knapsack polyhedra, incomparabilities between the column vectors of the associated matrix will be shown to transfer into inequalities of the associated polyhedron. Our scheme has been incorporated into the mixed integer programming code SIP. About experimental results will be reported
Erdos--Ko--Rado Theorems: New Generalizations, Stability Analysis and Chvatal's Conjecture
No full textabstract: The primary focus of this dissertation lies in extremal combinatorics, in particular intersection theorems in finite set theory. A seminal result in the area is the theorem of Erdos, Ko and Rado which finds the upper bound on the size of an intersecting family of subsets of an n-element set and characterizes the structure of families which attain this upper bound. A major portion of this dissertation focuses on a recent generalization of the Erdos--Ko--Rado theorem which considers intersecting families of independent sets in graphs. An intersection theorem is proved for a large class of graphs, namely chordal graphs which satisfy an additional condition and similar problems are considered for trees, bipartite graphs and other special classes. A similar extension is also formulated for cross-intersecting families and results are proved for chordal graphs and cycles. A well-known generalization of the EKR theorem for k-wise intersecting families due to Frankl is also considered. A stability version of Frankl's theorem is proved, which provides additional structural information about k-wise intersecting families which have size close to the maximum upper bound. A graph-theoretic generalization of Frankl's theorem is also formulated and proved for perfect matching graphs. Finally, a long-standing conjecture of Chvatal regarding structure of maximum intersecting families in hereditary systems is considered. An intersection theorem is proved for hereditary families which have rank 3 using a powerful tool of Erdos and Rado which is called the Sunflower Lemma.Dissertation/ThesisPh.D. Mathematics 201
Quantification of astrocyte volume changes during ischemia in situ reveals two populations of astrocytes in the cortex of GFAP/EGFP mice
No full textValid inequalities for mixed-integer linear programming problems
No full textIn this work we focus on various cutting-plane methods for Mixed-integer Linear Programming (MILP) problems. It is well-known that MILP is a fundamental hard problem and many famous combinatorial optimization problems can be modeled using MILP formulations. It is also well-known that MILP formulations are very useful in many real life applications. Our first, rather theoretical, contribution is a new family of superadditive valid inequalities that are obtained from value functions of special surrogate optimization problems. Superadditive functions hold particular interest in MILP as they are fundamental in building integer programming duality, and all ``deepest valid inequalities'' are known to arise from superadditive functions. We propose a new family of superadditive functions that generate inequalities that are at least as strong as Chvatal-Gomory (CG-) inequalities. A special subfamily provides a new characterization of CG-cuts. Value functions of optimization problems are known to be super additive. We look at special surrogate optimization problems, and measure their complexity in terms of the number of integer variables in them. It turns out that the lowest possible nontrivial complexity class here includes all CG-cuts, and provides some stronger ones, as well. Our next contribution is a practically efficient, polynomial time method to produce ``deepest'' cuts form multiple simplex rows for the so called corner polyhedra. These inequalities have been receiving considerable attention lately. We provide a polynomial time column-generation algorithm to obtain such inequalities, based on an arbitrary (fixed) number of rows of the simplex tableau. We provide numerical evidence that these inequalities improve the CPLEX integrality gap at the root node on a well-known set of MILP instances, MIPLIB. In the last chapter, we consider a particular MILP instance, Optimal Resilient Distribution Grid Design Problem (ORDGDP). This is a problem of critical importance to infrastructure security and recently attracted a lot of attention from various government agencies (e.g. Presidential Policy Directive of Critical Infrastructure Security 2013). We formulate this problem as a MILP and propose various efficient solution methods blending together well-known decomposition ideas to overcome the numerical intractability encountered using commercial MILP software such as CPLEX.Ph.D.Includes bibliographical referencesby Emre Yamangi
Combinatorics of finite sets
No full textLet and let 2\sp{\lbrack n\rbrack} represent the subset lattice of (n) with sets ordered by inclusion. A collection I of subsets of (n) is called an ideal if every subset of a member of I is also in I. An intersecting family S in 2\sp{\lbrack n\rbrack } is called a star if there exists an element of (n) belonging to every member of S, and it is a 1-star if the intersection of every two members of I is exactly that element. Chvatal conjectured that if I is any ideal, then among the intersecting subfamilies of I of maximum cardinality there is a star. In Chapter 1, we prove Chvatal's conjecture for several special cases. Let I be an ideal in 2\sp{\lbrack n\rbrack } that is compressed with respect to a given element. We prove that among the largest intersecting families of I there is a star. We also prove that if the maximal elements B\sb1,\...,B\sb{q} of an ideal I can be partitioned into two 1-stars, then I satisfies Chvatal's conjecture.In Chapter 2, we consider the following two conjectures concerning intersecting families of a finite set. Conjecture 1: (Frankl and Furedi (18)) Given n, k, let be a collection of subsets of an n-set such that 1 for all A, B . Then \vert{\cal A}\vert \leq t\sb{n,k}, where t\sb{n,k} = \sum\sbsp{i=0}{k}{n-1\choose i}. Conjecture 2: (Snevily) Let S = \{ l\sb1, ...,l\sb{k}\} be a collection of k positive integers. If is a collection of subsets of X such that for all A, , then \vert {\cal A}\vert \leq t\sb{n,k}. We prove that Conjecture 1 is true when n > 4.5k\sp{3} + 7.5k\sp2 + 3k + 1. We prove necessary conditions for possible counterexamples to Conjecture 2 when n is sufficiently large.Let denote the bipartite graph whose vertices are the k and k + 1 sets of (2k + 1), with edges specified by the inclusion relationship. Erdos conjectured that contains a Hamitonian cycle. Any such cycle must be composed of two matchings between the middle levels of the Boolean lattice. We study such matchings that are invariant under cyclic permutations of the ground set. We then construct a new class of matchings called modular matchings and show that these are nonisomorphic to the lexical matchings. We describe the orbits of the modular matchings under automorphisms of and we also construct an example of a matching that is neither lexical nor modular.Finally, we generalize some results about special vertex labelings that, by a theorem of Rosa, yield decompositions of the complete graph K\sb{n} into isomorphic copies of certain specified graphs.Made available in DSpace on 2011-05-07T12:58:24Z (GMT). No. of bitstreams: 2
license.txt: 4922 bytes, checksum: 910b249b4beec47e7ab768910c8f966f (MD5)
9210996.pdf: 3366094 bytes, checksum: 9a484010039f533d9bd8a524a1c8b7aa (MD5)
Previous issue date: 1991Item marked as restricted to the 'UIUC Users [automated]' Group (id=2) by Howard Ding ([email protected]) on 2011-05-07T14:48:29Z
Item is restricted indefinitely.Restriction data tranferred 2014-07-01T11:21:57-05:00
Original Data
Group with Access UIUC Users [automated]
Release Date: none
Reason: ETDs are only available to UIUC Users without author permissionETDs are only available to UIUC Users without author permissionU of I Onl
Optimal cellular offloading via device-to-device communication networks with fairness constraints
No full textThe increasing demand for large data downloads on cellular networks is increasing congestion which decreases end user quality of service. This work addresses the problem of offloading the cellular network while distributing common content to a group of mobile devices that cooperate during the download process by forming device-to-device communication networks. The base station unicasts different chunks of the content to selected mobile devices that multicast it to each other over local ad hoc networks using multihop cooperation while maintaining fairness constraints on the energy consumption of the mobile devices. The optimal cellular offloading problem is formulated as a mixed integer linear programming problem and the corresponding complexity is analyzed. Then, a dynamic programming approach is proposed to adapt the solution to the dynamics of the network as the mobile devices move. Cellular offloading assuming single hop cooperation among the mobile devices proves to be significantly less computationally complex than cooperation using a higher number of hops; however both problems are NP-complete. Thus, polynomial time greedy algorithms are presented to obtain computationally fast solutions with good performance. Performance results demonstrate that significant cellular offloading gains can be achieved, even if only a very small fraction of the mobile devices' battery levels can be consumed for cooperation. © 2002-2012 IEEE.Aijaz A, 2013, IEEE WIREL COMMUN, V20, P104, DOI 10.1109-MWC.2013.6507401; Albano M., 2011, P 26 WIR WORLD RES F, P1; Al-Kanj L., 2011, P IEEE GLOB COMM C G, P1; Al-Kanj L, 2013, IEEE COMMUN SURV TUT, V15, P1736, DOI 10.1109-SURV.2012.121912.00052; Al-Kanj L., 2012, P ICT APR, P1; Andrews JG, 2012, IEEE J SEL AREA COMM, V30, P497, DOI 10.1109-JSAC.2012.120401; Balani R., 2007, ENERGY CONSUMPTION A; Calin D, 2010, IEEE COMMUN MAG, V48, P26, DOI 10.1109-MCOM.2010.5394026; Chvatal V., 1979, Mathematics of Operations Research, V4, DOI 10.1287-moor.4.3.233; Dimatteocy S., 2011, P IEEE MASS, P192; Feige U, 1998, J ACM, V45, P634, DOI 10.1145-285055.285059; Goldsmith A., 2005, WIRELESS COMMUNICATI; Han B, 2012, IEEE T MOBILE COMPUT, V11, P821, DOI 10.1109-TMC.2011.101; Lecompte D, 2012, IEEE COMMUN MAG, V50, P68, DOI 10.1109-MCOM.2012.6353684; Lee K, 2013, IEEE ACM T NETWORK, V21, P536, DOI 10.1109-TNET.2012.2218122; Li Y., 2011, P 6 ACM WORKSH CHALL, P43; Mahmud K, 2005, IEICE T COMMUN, VE88B, P1097, DOI 10.1093-ietcom-e88-b.3.1097; Malandrino F., 2012, P IEEE SECON, P263; Proakis J. G., 2001, DIGITAL COMMUNICATIO; Qiao DJ, 2002, IEEE INFOCOM SER, P580; Ristanovic N., 2011, P IEEE MASS, P202; Wang TY, 2013, IEEE J SEL AREA COMM, V31, P538, DOI 10.1109-JSAC.2013.SUP.0513048; WANG X, 2012, IEEE INT CONF MOB, P353; Whitbeck J, 2012, PERVASIVE MOB COMPUT, V8, P682, DOI 10.1016-j.pmcj.2012.02.001; Wolsey LA, 1998, INTEGER PROGRAMMING; Xu C., 2014, SPRINGER BRIEFS COMP; Yang Z. X., 2010, P 9 INT WORKSH PEER, P1, DOI 10.1109-ISAPE.2010.5695146; Yanmaz E, 2004, IEEE J SEL AREA COMM, V22, P862, DOI 10.1109-JSAC.2004.826923; Zhu D., 2008, J PERVASIVE MOBILE C, V4, P335; Zhuo XJ, 2014, IEEE T MOBILE COMPUT, V13, P541, DOI 10.1109-TMC.2013.150
Constructive proposal based on the bioclimatic analysis of the envelope of agro-industrial plants for the production of panela
No full textilustraciones, diagramas, fotografíasEn esta tesis se contribuye al entendimiento de las condiciones microclimaticas adecuadas al interior de las instalaciones agroindustriales para la producción Azúcar de Caña no Centrifugada, en inglés: Non-centrifugal Cane Sugar (NCS), conocida en Colombia como “Panela” en regiones tropicales, utilizando las estrategias del diseño bioclimático en la envolvente, garantizando condiciones de confort térmico para los trabajadores y optimizando el uso de la energía para el funcionamiento de la edificación, que se logra a través de la combustión del bagazo, obteniendo como resultado menos emisión de CO2, lo cual contribuye a la disminución de la huella de carbono y por ende la protección del medio ambiente. A partir de la simulación Dinámica de Fluidos Computacional (CFD) y Simulación Energética de Edificios (BES) se describió el comportamiento fluidodinámico e higrotérmico dentro de la edificación, se modelaron doce tratamientos analizando el efecto de las aberturas en las paredes y en la ventana cenital, junto con el uso de tres tipos de materiales de cubierta. Además, se determinaron los índices de confort térmico: temperatura efectiva y el índice de temperatura del globo y bulbo húmedo en inglés: Wet Bulb Globe Temperatures (WBGT), así como el confort térmico adaptativo en cada tratamiento. Posteriormente se simuló la ventilación natural para un modelo de la instalación con el equipo de la mesa de agua. Con esta investigación se realizan aportes en el área del diseño y análisis bioclimático de envolventes de instalaciones agroindustriales por medio de herramientas de simulación computacional enfocadas en optimizar el microambiente al interior de la edificación, mejorando el bienestar del trabajador y las condiciones de eficiencia energética del proceso de producción. (Texto tomado de la fuente).This thesis contributes to the understanding of the appropriate microclimatic conditions within the agroindustrial facilities for the production of Non Centrifuged Cane Sugar (ACNC), known in Colombia as "Panela" in tropical regions, using bioclimatic design strategies in the envelope, ensuring thermal comfort conditions for workers and optimizing the use of energy for the operation of the building that is achieved through the combustion of bagasse, resulting in lower CO2 emissions contributing to the reduction of the carbon footprint and therefore to the protection of the environment. From Computational Fluid Dynamics (CFD) and Building Energy Simulation (BES), the fluid dynamic and hygrothermal behavior inside the building is described, twelve treatments were modeled analyzing the effect of the openings. on the walls and in the zenithal window, together with the use of three types of roofing materials, in addition, the thermal comfort indexes were determined: effective temperature and WBGT, and the adaptive thermal comfort model in each treatment. Subsequently, natural ventilation was simulated for a scale model of the installation with the water table equipment. With this research, contributions are made in the field of bioclimatic design and analysis of agroindustrial facility envelopes by means of computational simulation tools focused on optimizing the microenvironment inside the building, improving the worker's well-being and the energy efficiency conditions of the production process.MaestríaMagíster en ConstrucciónEdificaciones sosteniblesArquitectura y Urbanism
Алгоритмы поиска с возвратом для построения гамильтонова разложения 4-регулярного мультиграфа
No full textWe consider a Hamiltonian decomposition problem of partitioning a regular graph into edge-disjoint Hamiltonian cycles. It is known that verifying vertex non-adjacency in the 1-skeleton of the symmetric and asymmetric traveling salesperson polytopes is an NP-complete problem. On the other hand, a suffcient condition for two vertices to be non-adjacent can be formulated as a combinatorial problem of finding a Hamiltonian decomposition of a 4-regular multigraph. We present two backtracking algorithms for verifying vertex non-adjacency in the 1-skeleton of the traveling salesperson polytope and constructing a Hamiltonian decomposition: an algorithm based on a simple path extension and an algorithm based on the chain edge fixing procedure. Based on the results of the computational experiments for undirected multigraphs, both backtracking algorithms lost to the known heuristic general variable neighborhood search algorithm. However, for directed multigraphs, the algorithm based on chain fixing of edges showed comparable results with heuristics on instances with existing solutions, and better results on instances of the problem where the Hamiltonian decomposition does not exist.Рассматривается задача построения гамильтонова разложения регулярного мультиграфа на гамильтоновы циклы без общих рёбер. Известно, что проверка несмежности вершин в полиэдральных графах симметричного и асимметричного многогранников коммивояжёра является NP-полной задачей. С другой стороны, достаточное условие несмежности вершин можно сформулировать в виде комбинаторной задачи построения гамильтонова разложения 4-регулярного мультиграфа. В статье представлены два алгоритма поиска с возвратом для проверки несмежности вершин в полиэдральном графе коммивояжёра и построения гамильтонова разложения 4-регулярного мультиграфа: алгоритм на основе последовательного расширения простого пути и алгоритм на основе процедуры цепного фиксирования рёбер. По результатам вычислительных экспериментов для неориентированных мультиграфов оба переборных алгоритма проиграли известному эвристическому алгоритму поиска с переменными окрестностями. Однако для ориентированных мультиграфов алгоритм на основе цепного фиксирования рёбер показал сопоставимые результаты с эвристиками на экземплярах задачи, имеющих решение, и лучшие результаты на экземплярах задачи, для которых гамильтонова разложения не существует
