Improving a Lagrangian decomposition for the unconstrained binary quadratic programming problem

This paper presents a new alternative of Lagrangian decomposition based on column generation technique to solve the unconstrained binary quadratic programming problem. We use a mixed binary linear version of the original quadratic problem with constraints represented by a graph. This graph is partitioned into clusters of vertices forming subproblems whose solutions use the dual variables obtained by a coordinator problem. Computational experiments consider a set of difficult instances and the results are compared against other methods reported recently in the literature.     

A hybrid metaheuristic for multiobjective unconstrained binary quadratic programming

The conventional unconstrained binary quadratic programming (UBQP) problem is known to be a unified modeling and solution framework for many combinatorial optimization problems. This paper extends the single-objective UBQP to the multiobjective case (mUBQP) where multiple objectives are to be optimized simultaneously. We propose a hybrid metaheuristic which combines an elitist evolutionary multiobjective optimization algorithm and a state-of-the-art single-objective tabu search procedure by using an achievement scalarizing function. Finally, we define a formal model to generate mUBQP instances and validate the performance of the proposed approach in obtaining competitive results on large-size mUBQP instances with two and three objectives.     

Cooperative annealing Hopfield network for unconstrained binary quadratic programming problem

The updating rule of the original discrete Hopfield neural network (DHNN) is based on gradient descent dynamics, which always leads to the local minima problem. In this paper, by introducing the idea of the simulated annealing (SA) into the DHNN, we first propose an annealing HNN (AHNN) that permits temporary energy ascent to help the DHNN escape from local minima. Then, from a cooperative perspective, a population of the AHNN processes are simultaneously implemented and coupled by their acceptance probabilities, and thus a cooperative AHNN (CoAHNN) is proposed. The primary objective of the coupling in the CoAHNN is to create cooperative behavior via information exchange among neural networks. This objective helps in the decision of whether uphill moves will be accepted. In addition, coupling can provide information used online to guide the networks toward the global optimum. The CoAHNN is tested on 21 unconstrained binary quadratic programming problems (UBQP) with the size ranging from 3000 to 7000, and 48 maximum cut benchmark problems, a special case of the UBQP, with the size ranging from 512 to 3375. The UBQP consists in maximizing a quadratic 0–1 function. It is a well known NP-hard problem and is considered as a unified model for a variety of combinatorial optimization problems. Simulation results show that the CoAHNN is better than or competitive with other HNN based algorithms, metaheuristic algorithms and state-of-the-art algorithms.     

Optimization procedures for the bipartite unconstrained 0-1 quadratic programming problem

The bipartite unconstrained 0-1 quadratic programming problem (BQP) is a difficult combinatorial problem defined on a complete graph that consists of selecting a subgraph that maximizes the sum of the weights associated with the chosen vertices and the edges that connect them. The problem has appeared under several different names in the literature, including maximum weight induced subgraph, maximum weight biclique, matrix factorization and maximum cut on bipartite graphs. There are only two unpublished works (technical reports) where heuristic approaches are tested on BQP instances. Our goal is to combine straightforward search elements to balance diversification and intensification in both exact (branch and bound) and heuristic (iterated local search) frameworks. We perform a number of experiments to test individual search components and also to create new benchmarks when comparing against the state of the art, which the proposed procedure outperforms.     

Combining tabu Hopfield network and estimation of distribution for unconstrained binary quadratic programming problem

Unconstrained binary quadratic programming problem (UBQP) consists in maximizing a quadratic 0–1 function. It is a well known NP-hard problem and is considered as a unified model for a variety of combinatorial optimization problems. This paper combines a tabu Hopfield neural network (HNN) (THNN) with estimation of distribution algorithm (EDA), and thus a THNN–EDA is proposed for the UBQP. In the THNN, the tabu rule, instead of the original updating rule of the HNN, is used to govern the state transition or updating of neurons to search for the global minimum of the energy function. A probability vector in EDA model is built to characterize the distribution of promising solutions in the search space, and then the THNN is guided by the global search information in EDA model to search better solution in the promising region. Thus, the short term memory of the tabu mechanism in the THNN cooperates with the long term memory mechanism in the EDA to help the network escape from local minima. The THNN–EDA is tested on 21 UBQP benchmark problems with the size ranging from 3000 to 7000, and 48 maximum cut benchmark problems, a special case of the UBQP, with the size ranging from 512 to 3375. Simulation results show that the THNN–EDA is better than the other HNN based algorithms, and is better than or competitive with metaheuristic algorithms and state-of-the-art algorithms.     

Systems Analysis; Solving unconstrained binary quadratic programming problem by global equilibrium search

A new algorithm based on global equilibrium search (GES) is developed to solve an unconstrained binary quadratic programming (UBQP) problem. It is compared with the best methods of solving this problem. The GES algorithm is shown to be better both in speed and solution quality.     

Lagrangean relaxation heuristics for the p-cable-trench problem

We address the p-cable-trench problem. In this problem, p facilities are located, a trench network is dug and cables are laid in the trenches, so that every customer - or demand - in the region is connected to a facility through a cable. The digging cost of the trenches, as well as the sum of the cable lengths between the customers and their assigned facilities, are minimized. We formulate an integer programming model of the problem using multicommodity flows that allows finding the solution for instances of up to 200 nodes. We also propose two Lagrangean Relaxation-based heuristics to solve larger instances of the problem. Computational experience is provided for instances of up to 300 nodes.     

Stability and regularization of the lexicographic vector problem of quadratic discrete programming

The paper studies the bounds of variation of input parameters for a vector quadratic discrete optimization problem, which do not expand the set of lexicographic optima. A stability criterion is described and a regularization method is presented, which makes it possible to pass from a possibly unstable problem to a series of perturbed stable problems with a previous set of lexicographic optima. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 54–62, March–April, 2000.     

A Lagrangean relaxation approach for the mixed-model flow line sequencing problem

In this study, a mixed-model flow line sequencing problem is considered. A mixed-model flow line is a special case of production line where products are transported on a conveyor belt, and different models of the same product are intermixed on the same line. We have focused on product-fixed, rate-synchronous lines with variable launching. Our objective function is minimizing makespan. A heuristic algorithm based on Lagrangean relaxation is developed for the problem, and tested in terms of solution quality and computational efficiency.     

信赖域共轭梯度法求解二次规划逆问题

为了有效地求解二次规划逆问题,提出了一种求解其对偶问题的子问题的光滑化信赖域共轭梯度法。该方法采用增广拉格朗日法求解其对偶问题,引入光滑函数将对偶问题的子问题转换成连续的无约束优化问题,将信赖域法与共轭梯度法结合,设计出求解二次规划逆问题的算法流程。数值实验结果表明,该方法可行且有效,与牛顿法相比,更适合求解大规模问题。     

A new branch-and-bound algorithm for standard quadratic programming problems

In this paper we propose convex and LP bounds for standard quadratic programming (StQP) problems and employ them within a branch-and-bound approach. We first compare different bounding strategies for StQPs in terms both of the quality of the bound and of the computation times. It turns out that the polyhedral bounding strategy is the best one to be used within a branch-and-bound scheme. Indeed, it guarantees a good quality of the bound at the expense of a very limited computation time. The proposed branch-and-bound algorithm performs an implicit enumeration of all the KKT (stationary) points of the problem. We compare different branching strategies exploiting the structure of the problem. Numerical results on randomly generated problems (with varying density of the underlying convexity graph) are reported which show the effectiveness of the proposed approach, in particular in limiting the growth of the number of nodes in the branch-and-bound tree as the density of the underlying graph increases.     

Lagrangean relaxation with clusters for point-feature cartographic label placement problems

This paper presents two new mathematical formulations for the point-feature cartographic label placement problem (PFCLP) and a new Lagrangean relaxation with clusters (LagClus) to provide bounds to these formulations. The PFCLP can be represented by a conflict graph and the relaxation divides the graph in small subproblems (clusters) that are easily solved. The edges connecting clusters are relaxed in a Lagrangean way and a subgradient algorithm improves the bounds. The LagClus was successfully applied to a set of instances up to 1000 points providing the best results of those reported in the literature.     

The ‘Idiot’ crash quadratic penalty algorithm for linear programming and its application to linearizations of quadratic assignment problems

ABSTRACT

We provide the first meaningful documentation and analysis of the ‘Idiot’ crash implemented by Forrest in Clp that aims to obtain an approximate solution to linear programming (LP) problems for warm-starting the primal simplex method. The underlying algorithm is a penalty method with naive approximate minimization in each iteration. During initial iterations an approach similar to augmented Lagrangian is used. Later the technique corresponds closely to a classical quadratic penalty method. We discuss the extent to which it can be used to obtain fast approximate solutions of LP problems, in particular when applied to linearizations of quadratic assignment problems.     

On solutions of fuzzy random multiobjective quadratic programming with applications in portfolio problem

In this paper, a multiobjective quadratic programming problem fuzzy random coefficients matrix in the objectives and constraints and the decision vector are fuzzy variables is considered. First, we show that the efficient solutions fuzzy quadratic multiobjective programming problems series-optimal-solutions of relative scalar fuzzy quadratic programming. Some theorems are to find an optimal solution of the relative scalar quadratic multiobjective programming with fuzzy coefficients, having decision vectors as fuzzy variables. An application fuzzy portfolio optimization problem as a convex quadratic programming approach is discussed and an acceptable solution to such problem is given. At the end, numerical examples are illustrated in the support of the obtained results.     

Lagrangean-based solution approaches for the generalized problem of locating capacitated warehouses

The traditional capacitated warehouse location problem consists of determining the number and the location of capacitated warehouses on a predefined set of potential sites such that the demands of a set of customers are met. A very common assumption made in modeling this problem in almost all of the existing research is that the total capacity of all potential warehouses is sufficient to meet the total demand. Whereas this assumption facilitates to define a well‐structured problem from the mathematical modeling perspective, it is in fact restrictive, not realistic, and hence rarely held in practice. The modeling approach presented in this paper breaks away from the existing research in relaxing this very restrictive assumption. This paper therefore investigates the generalized problem of locating warehouses in a supply chain setting with multiple commodities with no restriction on the total capacity and the demand. A new integer programming formulation for this problem is presented, and an algorithm based on Lagrangean relaxation and decomposition is described for its solution. Three Lagrangean heuristics are proposed. Computational results indicate that reasonably good solutions can be obtained with the proposed algorithms, without having to use a general purpose optimizer.     

Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem

We consider in this paper a new lagrangean relaxation with clusters for the Manufacturer's Pallet Loading Problem (MPLP). The relaxation is based on the MPLP formulated as a Maximum Independent Set Problem (MISP) and represented in a conflict graph that can be partitioned in clusters. The edges inter clusters are relaxed in a lagrangean fashion. Computational tests attain the optimality for some instances considered difficult for a lagrangean relaxation. Our results show that this relaxation can be a successful approach for hard combinatorial problems modeled in conflict graphs. Moreover, we propose a column generation approach for the MPLP derived from the idea behind the lagrangean relaxation proposed.     

A Long-step barrier method for convex quadratic programming

In this paper we propose a long-step logarithmic barrier function method for convex quadratic programming with linear equality constraints. After a reduction of the barrier parameter, a series of long steps along projected Newton directions are taken until the iterate is in the vicinity of the center associated with the current value of the barrier parameter. We prove that the total number of iterations isO(nL) orO(nL), depending on how the barrier parameter is updated.On leave from Eötvös University, Budapest and partially supported by OTKA 2116.     

求解一类特殊的双层规划问题的遗传算法

主要研究上层函数及其约束函数不要求具有凸性和可微性,下层是关于下层决策变量是凸二次规划的双层规划模型,通过Karush-Kuhn-Tucher 条件转化为一个单层规划,利用下层是正定二次规划,将下层的决策变量表示为关于 Lagrangian乘子的表达式,从而降低了搜索空间的维数,设计了遗传算法,并通过数值实验表明该遗传算非常有效。     

非凸二次规划全局极小问题的新型分枝定界算法

针对求解多面集上二次函数的全局近似最优解问题,利用逐步缩小对偶间隙的处理办法,提出了一个新型分枝定界算法。新算法的主要改进之处是利用了Lagrange 对偶性获取下界。最后,用构造和随机产生的问题实例,对提出的新算法和传统的分枝定界算法做了初步的数值比较实验。计算实验表明算法对求解中大规模非凸二次规划问题的有效性。