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 study proposes a methodology to address the reconfiguration of electrical distribution networks, formulating it as a mixed integer nonlinear optimization model. the complexity arises from disconnectors, with binar...
详细信息
this paper presents an application of the Multi-Objective Branch-and-Bound based on Decomposition (MOBB/D) method for Branch-and-Cut, combining branch-and-bound and cutting-plane methods. Traditionally, multi-objectiv...
详细信息
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.
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.
We present a new column generation approach based on Machine Learning (ML) for solving combinatorialoptimization *** aim of our method is to generate high-quality columns that belong to an optimal integer solution, i...
详细信息
Local search (LS) is an efficient method for solving combinatorialoptimization problems such as MaxSAT and Pseudo Boolean Problems (PBO). However, due to a lack of reasoning power and global information, LS methods g...
详细信息
Pseudo-Boolean (PB) constraints are highly expressive, and many combinatorialoptimization problems can be modeled using pseudo-Boolean optimization (PBO). It is recognized that stochastic local search (SLS) is a powe...
详细信息
暂无评论