Approximate integerprogramming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 center dot (K - c) + c whi...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
Approximate integerprogramming is the following: For a given convex body K subset of R-n, either determine whether K boolean AND Z(n) is empty, or find an integer point in the convex body 2 center dot (K - c) + c which is K, scaled by 2 from its center of gravity c. Approximate integerprogramming can be solved in time 2(O(n)) while the fastest known methods for exact integerprogramming run in time 2(O(n)) center dot n(n). So far, there are no efficientmethods for integerprogramming known that are based on approximate integerprogramming. Our main contribution are two such methods, each yielding novel complexity results. First, we showthat an integer point x * is an element of (K boolean AND Z(n)) can be found in time 2(O(n)), provided that the remainders of each component x(i)* mod l for some arbitrarily fixed l >= 5(n + 1) of x * are given. the algorithm is based on a cutting-plane technique, iteratively halving the volume of the feasible set. the cutting planes are determined via approximate integerprogramming. Enumeration of the possible remainders gives a 2(O(n))n(n) algorithm for general integerprogramming. this matches the current best bound of an algorithm by Dadush (2012) that is considerably more involved. Our algorithm also relies on a new asymmetric approximate Caratheodory theorem that might be of interest on its own. Our second method concerns integerprogramming problems in standard equation form Ax = b, 0 <= x <= u, x is an element of Z(n). Such a problem can be reduced to the solution of Pi(i) O(logu(i) + 1) approximate integerprogramming problems. this implies, for example that knapsack or subset-sum problems with polynomial variable range 0 <= x(i) <= p(n) can be solved in time (logn)(O(n)). For these problems, the best running time so far was n(n) center dot 2(O(n)).
We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. this problem arises in video game settings where designers aim to have players use different "weapon...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
We consider the problem of designing a linear program that has diverse solutions as the right-hand side varies. this problem arises in video game settings where designers aim to have players use different "weapons" or "tactics" as they progress. We model this design question as a choice over the constraint matrix A and cost vector c to maximize the number of possible supports of unique optimal solutions (what we call "loadouts") of Linear Programs max{c(inverted perpendicular) x vertical bar Ax <= b, x >= 0} with nonnegative data considered over all resource vectors b. We provide an upper bound on the optimal number of loadouts and provide a family of constructions that have an asymptotically optimal number of loadouts. the upper bound is based on a connection between our problem and the study of triangulations of point sets arising from polyhedral combinatorics, and specifically the combinatorics of the cyclic polytope. Our asymptotically optimal construction also draws inspiration from the properties of the cyclic polytope.
Mixed integer Linear programming (MILP) technology is a versatile method used for formulating and solving combinatorialoptimization problems. During the solving process, primal heuristics help to quickly find good fe...
详细信息
ISBN:
(纸本)9798350350227;9798350350210
Mixed integer Linear programming (MILP) technology is a versatile method used for formulating and solving combinatorialoptimization problems. During the solving process, primal heuristics help to quickly find good feasible solutions, which can aid branch-and-bound (B&B) algorithms in reducing the primal-dual gap and pruning the B&B search tree. the heuristics employed by existing open-source solvers follow empirical rules summarized from real-world instances, enabling the solvers to achieve generally good performance but sometimes performing poorly on specific instances. In response, this paper proposes a method that uses hierarchical sequence models to learn the patterns of given instances and assigns a heuristic configuration for them. Compared to the default settings of the solver, the proposed method enables heuristic module to perform better, finding feasible solutions more quickly and reducing the primal-dual gap. Experimental results indicate that the proposed method can improve the solver's average performance on given instances by 27%.
the proceedings contain 44 papers. the special focus in this conference is on Evolutionary Multi-Criterion optimization. the topics include: A Systematic Way of Structuring Real-World Multiobjective optimization ...
ISBN:
(纸本)9783031272493
the proceedings contain 44 papers. the special focus in this conference is on Evolutionary Multi-Criterion optimization. the topics include: A Systematic Way of Structuring Real-World Multiobjective optimization Problems;IK-EMOViz: An Interactive Knowledge-Based Evolutionary Multi-objective optimization Framework;an Interactive Decision Tree-Based Evolutionary Multi-objective Algorithm;data-Driven Evolutionary Multi-objective optimization Based on Multiple-Gradient Descent for Disconnected Pareto Fronts;Eliminating Non-dominated Sorting from NSGA-III;scalability of Multi-objective Evolutionary Algorithms for Solving Real-World Complex optimization Problems;Multi-objective Learning Using HV Maximization;sparse Adversarial Attack via Bi-objective optimization;preface;visual Exploration of the Effect of Constraint Handling in Multiobjective optimization;investigating Innovized Progress Operators with Different Machine Learning Methods;end-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location;online Learning Hyper-Heuristics in Multi-Objective Evolutionary Algorithms;surrogate-assisted Multi-objective optimization via Genetic programming Based Symbolic Regression;learning to Predict Pareto-Optimal Solutions from Pseudo-weights;a Relation Surrogate Model for Expensive Multiobjective Continuous and combinatorialoptimization;pareto Front Upconvert by Iterative Estimation Modeling and Solution Sampling;an Improved Fuzzy Classifier-Based Evolutionary Algorithm for Expensive Multiobjective optimization Problems with Complicated Pareto Sets;approximation of a Pareto Set Segment Using a Linear Model with Sharing Variables;feature-Based Benchmarking of Distance-Based Multi/Many-objective Optimisation Problems: A Machine Learning Perspective;a Two-Stage Algorithm for integer Multiobjective Simulation optimization;partially Degenerate Multi-objective Test Problems;peak-A-Boo! Generating Multi-objective Multiple Peaks Benchmark Problems with
We consider the minimum-norm-point (MNP) problem of polyhedra, a well-studied problem that encompasses linear programming. Inspired by Wolfe's classical MNP algorithm, we present a general algorithmic framework th...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
We consider the minimum-norm-point (MNP) problem of polyhedra, a well-studied problem that encompasses linear programming. Inspired by Wolfe's classical MNP algorithm, we present a general algorithmic framework that performs first order update steps, combined with iterations that aim to 'stabilize' the current iterate with additional projections, i.e., finding a locally optimal solution whilst keeping the current tight inequalities. We bound the number of iterations polynomially in the dimension and in the associated circuit imbalance measure. In particular, the algorithm is strongly polynomial for network flow instances. the conic version of Wolfe's algorithm is a special instantiation of our framework;as a consequence, we obtain convergence bounds for this algorithm. Our preliminary computational experiments show a significant improvement over standard first-order methods.
A directed feedback vertex set (DFVS) of a directed graph is a subset of vertices whose removal makes the graph acyclic. Finding a DFVS of minimum cardinality is the goal of the directed feedback vertex set problem, a...
详细信息
ISBN:
(纸本)9783031692567;9783031692574
A directed feedback vertex set (DFVS) of a directed graph is a subset of vertices whose removal makes the graph acyclic. Finding a DFVS of minimum cardinality is the goal of the directed feedback vertex set problem, an NP-hard combinatorialoptimization problem. We first consider two mixed integer linear programming (MILP) models for this problem, which, when solved with Gurobi, are effective on graphs of small to medium complexity but do not scale well to large instances. Aiming at better scalability and higher robustness over a large variety of graphs, we investigate a large neighborhood search (LNS) in which a destroy operator removes randomly chosen nodes from an incumbent DFVS and one of the MILP models is used for repair. Regarding the destroy operator, finding a best degree of destruction is challenging. A main contribution lies in proposing several selection strategies for this parameter as well as a strategy for choosing the more promisingMILP model for repair. We evaluate the performance of the MILP models and different LNS variants on benchmark instances and compare the approaches to each other as well as to state-of-the-art procedures. Results show that our LNS variants yield clearly better solutions on average than standalone MILP solving. Even though our approaches cannot outperform the state-of-the-art, we gain valuable insights on beneficially configuring such a MILP-based LNS.
this paper studies the location-routing problem in the pallet pooling system. Considering the characteristic of simultaneous delivery and pickup, a mixed integer linear programming model is proposed for the location-r...
详细信息
Using large language models (LLMs) for tasks like text-to-SQL translation often requires describing the database schema as part of the model input. LLM providers typically charge as a function of the number of tokens ...
详细信息
We consider box-constrained integer programs with objective g(Wx)+ c(inverted perpendicular) x, where g is a "complicated" function with an m dimensional domain. Here we assume we have n >> m variables...
详细信息
ISBN:
(数字)9783031327261
ISBN:
(纸本)9783031327254;9783031327261
We consider box-constrained integer programs with objective g(Wx)+ c(inverted perpendicular) x, where g is a "complicated" function with an m dimensional domain. Here we assume we have n >> m variables and that W is an element of Z(mxn) is an integer matrix with coefficients of absolute value at most Delta We design an algorithm for this problem using only the mild assumption that the objective can be optimized efficiently when all but m variables are fixed, yielding a running time of n(m) (m Delta)(O)(m(2)). Moreover, we can avoid the term n(m) in several special cases, in particular when c = 0. Our approach can be applied in a variety of settings, generalizing several recent results. An important application are convex objectives of low domain dimension, where we imply a recent result by Hunkenschroder et al. [SIOPT'22] for the 0-1-hypercube and sharp or separable convex g, assuming W is given explicitly. By avoiding the direct use of proximity results, which only holds when g is separable or sharp, we match their running time and generalize it for arbitrary convex functions. In the case where the objective is only accessible by an oracle and W is unknown, we further show that their proximity framework can be implemented in n(m(Delta))(O)(m(2))- time instead of n(m Delta)(O)(m(3)). Lastly, we extend the result by Eisenbrand andWeismantel [SODA'17, TALG'20] for integer programs with few constraints to a mixed-integer linear program setting where integer variables appear in only a small number of different constraints.
the increasing power consumption of Data Center Networks (DCN) is becoming a major concern for network operators. the object of this paper is to provide a survey of state-of-the-art methods for reducing energy consump...
详细信息
the increasing power consumption of Data Center Networks (DCN) is becoming a major concern for network operators. the object of this paper is to provide a survey of state-of-the-art methods for reducing energy consumption via (1) enhanced scheduling and (2) enhanced aggregation of traffic flows using Software-Defined Networks (SDN), focusing on the advantages and disadvantages of these approaches. We tackle a gap in the literature for a review of SDN-based energy saving techniques and discuss the limitations of multi-controller solutions in terms of constraints on their performance. the main this survey paper is that the two classes of SDN- based methods, scheduling and flow aggregation, significantly reduce energy consumption in DCNs. We also suggest that Machine Learning has the potential to further improve these classes of solutions and argue that hybrid ML-based solutions are the next frontier for the field. the perspective gained as a consequence of this analysis is that advanced ML-based solutions and multi-controller-based solutions may address the limitations of the state-of-the-art, and should be further explored for energy optimization in DCNs.
暂无评论