We show how under certain conditions one can extend constructions of integrality gaps for semidefinite relaxations into ones that hold for stronger systems: those SDP to which the so-called k-level constraints of the ...
详细信息
ISBN:
(纸本)9783642130359
We show how under certain conditions one can extend constructions of integrality gaps for semidefinite relaxations into ones that hold for stronger systems: those SDP to which the so-called k-level constraints of the Sherali-Adams hierarchy are added. the value of k above depends on properties of the problem. We present two applications, to the QUADRATIC programming problem and to the MAXCUTGAIN problem. Our technique is inspired by a paper of [Raghavendra and Steurer [Raghavendra and Steurer, FOGS 09] and our result gives a doubly exponential improvement for QUADRATIC programming on another result by the same authors [Raghavendra and Steurer. FOGS 09]. they provide tight integrality-gap for the system above which is valid up to k = (log log n)(Omega(1)) whereas we give such a gap for up to k = n(Omega(1)).
the concept of walkable urban development has gained increased attention due to its public health, economic, and environmental sustainability benefits. Unfortunately, land zoning and historic under-investment have res...
详细信息
ISBN:
(纸本)9781577358800
the concept of walkable urban development has gained increased attention due to its public health, economic, and environmental sustainability benefits. Unfortunately, land zoning and historic under-investment have resulted in spatial inequality in walkability and social inequality among residents. We tackle the problem of Walkability optimizationthrough the lens of combinatorialoptimization. the task is to select locations in which additional amenities (e.g., grocery stores, schools, restaurants) can be allocated to improve resident access via walking while taking into account existing amenities and providing multiple options (e.g., for restaurants). To this end, we derive Mixed-integer Linear programming (MILP) and Constraint programming (CP) models. Moreover, we show that the problem's objective function is submodular in special cases, which motivates an efficient greedy heuristic. We conduct a case study on 31 underserved neighborhoods in the City of Toronto, Canada. MILP finds the best solutions in most scenarios but does not scale well with network size. the greedy algorithm scales well and finds high-quality solutions. Our empirical evaluation shows that neighbourhoods with low walkability have a great potential for transformation into pedestrian-friendly neighbourhoods by strategically placing new amenities. Allocating 3 additional grocery stores, schools, and restaurants can improve the "WalkScore" by more than 50 points (on a scale of 100) for 4 neighbourhoods and reduce the walking distances to amenities for 75% of all residential locations to 10 minutes for all amenity types. Our code and paper appendix are available at https://***/khalil-research/walkability.
the proceedings contain 53 papers. the topics discussed include: the combinatorics of sequencing the corn genome;online frequency assignment in wireless communication networks;information distance from a question to a...
详细信息
ISBN:
(纸本)9783540735441
the proceedings contain 53 papers. the topics discussed include: the combinatorics of sequencing the corn genome;online frequency assignment in wireless communication networks;information distance from a question to an answer;a new field splitting algorithm for intensity-modulated radiation therapy;seed-based exclusion method for non-coding RNA gene search;integerprogramming formulations and computations solving phylogenetic and population genetic problems with missing or genotypic data;improved exact algorithms for counting 3- and 4-colorings;quadratic kernelization for convex recoloring of tress;on the number of cycles in planar graphs;an improved exact algorithm for cubic graph TSP;dimension, halfspaces, and the density of hard sets;isolation concepts for enumerating dense subgraphs;counting minimum weighted dominating sets;volume computation using a direct Monte Carlo method;and improved throughput bounds for interference-aware routing in wireless networks.
the exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we p...
详细信息
ISBN:
(数字)9783319334615
ISBN:
(纸本)9783319334615;9783319334608
the exact solution of bilevel optimization problems is a very challenging task that received more and more attention in recent years, as witnessed by the flourishing recent literature on this topic. In this paper we present ideas and algorithms to solve to proven optimality generic Mixed-integer Bilevel Linear Programs (MIBLP's) where all constraints are linear, and some/all variables are required to take integer values. In doing so, we look for a general-purpose approach applicable to any MIBLP (under mild conditions), rather than ad-hoc methods for specific cases. Our approach concentrates on minimal additions required to convert an effective branch-and-cut MILP exact code into a valid MIBLP solver, thus inheriting the wide arsenal of MILP tools (cuts, branching rules, heuristics) available in modern solvers.
One of the most famous conjectures in combinatorialoptimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to 4/3. For 40 years, the best kno...
详细信息
ISBN:
(纸本)9783031598340;9783031598357
One of the most famous conjectures in combinatorialoptimization is the four-thirds conjecture, which states that the integrality gap of the subtour LP relaxation of the TSP is equal to 4/3. For 40 years, the best known upper bound was 1.5, due to Wolsey [Wol80]. Recently, Karlin, Klein, and Oveis Gharan [KKO22] showed that the max entropy algorithm for the TSP gives an improved bound of 1.5 - 10(-36). In this paper, we show that the approximation ratio of the max entropy algorithm is at least 1.375, even for graphic TSP. thus the max entropy algorithm does not appear to be the algorithm that will ultimately resolve the four-thirds conjecture in the affirmative, should that be possible.
A process integration model is developed based on mixed integer linear programming. the analysis is carried out using the reMIND software in combination withthe commercial optimization software CPLEX. the steam produ...
详细信息
ISBN:
(纸本)9788895608051
A process integration model is developed based on mixed integer linear programming. the analysis is carried out using the reMIND software in combination withthe commercial optimization software CPLEX. the steam production (heat recovery boiler, bark boiler and steam turbines) and the process steam consumers (digester, evaporation plant, bleaching plant as well as pulp dry machine and paper making machine) are modeled as separate modules and thereafter linked and are validated using the operation data from a pulp and paper mill in the Northern Sweden. the whole plant is simulated and initial optimization runs are performed in which the cost is to be minimized.
Difficult combinatorialoptimization problems coming from practice are nowadays often approached by hybrid metaheuristics that combine principles of classical metaheuristic techniques with advanced methods from fields...
详细信息
Difficult combinatorialoptimization problems coming from practice are nowadays often approached by hybrid metaheuristics that combine principles of classical metaheuristic techniques with advanced methods from fields like mathematical programming, dynamic programming, and constraint programming. If designed appropriately, such hybrids frequently outperform simpler "pure" approaches as they are able to exploit the underlying methods' individual advantages and benefit from synergy. this article starts with a general review of design patterns for hybrid approaches that have been successful on many occasions. More complex practical problems frequently have some special structure that might be exploited. In the field of mixed integer linear programming, three decomposition techniques are particularly well known for taking advantage of special structures: Lagrangian decomposition, Dantzig-Wolfe decomposition (column generation), and Benders' decomposition. It has been recognized that these concepts may also provide a very fruitful basis for effective hybrid metaheuristics. We review the basic principles of these decomposition techniques and discuss for each promising possibilities for combinations with metaheuristics. the approaches are illustrated with successful examples from literature. (C) 2014 Elsevier B.V. All rights reserved.
Majority of process plants contain heat exchanger networks. these facilitate heat exchange between hot and cold process streams and thus lower demand for energy of the entire plant. As a result, this leads not only to...
详细信息
ISBN:
(纸本)9788895608051
Majority of process plants contain heat exchanger networks. these facilitate heat exchange between hot and cold process streams and thus lower demand for energy of the entire plant. As a result, this leads not only to lower operational costs but can also cause an abatement of emissions plants produce. the aim of this paper is to provide a multi-objective optimization algorithm that can be used for automated synthesis of small-scale heat exchanger networks commonly used in waste-to-energy process plants. this algorithm employs two optimization models, first of which is an MILP (Mixed-integer Linear programming) model that does not support stream splitting or any other feature requiring non-linear constraints. Optimum design of a simple HEN is always quickly reached due to model's linearity. the other model is a more sophisticated MINLP (Mixed-integer Non-Linear programming) one which contains non-linear constraints and therefore its computational requirements are relatively high. Both models are based on previous work of Turek et al. (2009) and are enhanced withthe emphasis on obtaining a global solution within a reasonable time frame. Also, an existing heat exchanger network is analyzed in the paper and possible improvements are discussed.
We present a new method to compute upper bounds of the number of solutions of binary integerprogramming (BIP) problems. Given a BIP, we create a dynamic programming (DP) table for a redundant knapsack constraint whic...
详细信息
ISBN:
(纸本)9783642135194
We present a new method to compute upper bounds of the number of solutions of binary integerprogramming (BIP) problems. Given a BIP, we create a dynamic programming (DP) table for a redundant knapsack constraint which is obtained by surrogate relaxation. We then consider a Lagrangian relaxation of the original problem to obtain an initial weight bound on the knapsack. this bound is then refined through subgradient optimization. the latter provides a variety of Lagrange multipliers which allow us to filter infeasible edges in the DP table. the number of paths in the final table then provides an upper bound on the number of solutions. Numerical results show the effectiveness of our counting framework on automatic recording and market split problems.
In light of significant complexity of the byproduct gas system in steel industry (which limits an ability to establish its physics-based model), this study proposes a data-based predictive optimization (DPO) method to...
详细信息
ISBN:
(纸本)9781509067817
In light of significant complexity of the byproduct gas system in steel industry (which limits an ability to establish its physics-based model), this study proposes a data-based predictive optimization (DPO) method to carry out real-time adjusting for the gas system. Two stages of the method, namely the prediction modeling and real-time optimization, are involved. At the prediction stage, the states of the optimized objectives, the consumption of the outsourcing natural gas and oil, the power generation and the tank levels, are forecasted based on a proposed mixed Gaussian kernel-based prediction intervals (PIs) construction model. the Jacobian matrix of this model is represented by a kernel matrix through derivation, which greatly facilitates the subsequent calculation. At the second stage, a rolling optimization based on a mathematical programming technique involving continuous and integer decision-making variables is developed via the prediction intervals.
暂无评论