Search

The Wiener index of a graph is the sum of the distances between all pairs of vertices. It has been one of the main descriptors that correlate a chemical compound’s molecular structure with experimentally gathered data regarding the compound’s characteristics. In 2008, Wang and Zhang independently characterized trees with specified degree sequence that minimize the Wiener index. In the paper of Wang, a corollary on maximizing the Wiener index was pointed out to be incorrect by Zhang et. al. in 2010. Zhang et. al. also provided partial results and noted that the question turns out to be complicated. Later, Çela et. al. considered this question as a quadratic assignment problem and provided a polynomial time algorithm. We make some progress in this contribution, providing information on the candidate trees for the maximum Wiener index. Some interesting combinatorial relations to other objects arose from this study. We also consider the bound of this maximum value as well as study this question for trees with small diameter and for chemical trees with specified degree sequence.

This paper presents several optimization problems occurring in VLSI interconnect, Networks on Chip (NoC) design and 3D VLSI integration, all possessing closed-form solutions obtained by well-solvable Quadratic Assignment Problems (QAP). The first type of problems deals with the optimal ordering of signals in a bus bundle such that the switching power, delay and noise interference are minimized. We extend a known solution of ordering the signals in a bus bundle to minimize the impact of the first order wire-to-wire parasitic capacitance occurring between adjacent wires into a model accounting for also secondary components of wire-to-wire parasitic capacitances. The second type of problems arises in the mapping of computation tasks into an array of processors sharing a common bus, such as those found in NoC. We show a QAP closed-form solution to the optimal mapping problem which simultaneously minimizes the switching power and the average delay of the bus. The third problem deals with the optimization of 3D VLSI, vertically stacking ordinary ICs. Some of the above problems involve k-salesmen Traveling Salesman Problem (TSP), where costs are evaluated for elements located at k-distance apart along the tour. We show a simple proof that these are well-solvable problems and obtain their solution. This is then generalized to well-solvable QAPs obtained by superposition of such TSPs. A simple proof shows that if k-distance TSPs are well-solvable, so is the QAP obtained by their sum, where the solution of 1-distance TSPs dominates all the others.

In this paper, we consider combinatorial optimization problems with additional cardinality constraints. In k-cardinality combinatorial optimization problems, a cardinality constraint requires feasible solutions to contain exactly k elements of a finite set E. Problems of this type have applications in many areas, e.g. in the mining and oil industry, telecommunications, circuit layout, and location planning. We formally define the problem, mention some examples and summarize general results. We provide an annotated bibliography of combinatorial optimization problems of which versions with cardinality constraint have been considered in the literature.

In this work, we introduce the variance expression for quadratic assignment problem (QAP) costs. We also define classes of QAP instances, described by a common linear relaxation form. The use of the variance in these classes leads to the study of isomorphism and allows for a definition of a new difficulty index for QAP instances. This index is then compared to a classical measure found in the literature.

We survey recent developments in the fields of bipartite matchings, linear sum assignment and bottleneck assignment problems and applications, multidimensional assignment problems, quadratic assignment problems, in particular lower bounds, special cases and asymptotic results, biquadratic and communication assignment problems.

This paper surveys the recent results in stability analysis for discrete optimization problems, such as a traveling salesman problem, an assignment problem, a shortest path problem, a Steiner problem, a scheduling problem and so on. The terms “stability”, “sensitivity” or “postoptimal analysis” are generally used for the phase of an algorithm at which a solution (or solutions) of the problem has been already found, and additional calculations are also performed in order to investigate how this solution depends on changes in the problem data. In this paper, the main attention is paid to the stability region and to the stability ball of optimal or approximate solutions. A short sketch of some other close results has been added to emphasize the differences in approach surveyed.

The Quadratic Assignment Problem is known as a combinatorial optimization problem, which is very hard to solve exactly. A survey of recent methods for solving this problem is given. Then an exact algorithm is presented along with computational results on a variety of test problems. This algorithm obtains very good results and, for the first time to our knowledge, solves exactly problems of size up to twenty, this in less than twenty minutes.

In many applications it is necessary to find a minimum weight assignment that satisfies one or several additional resource constraints. For example, consider the problem of assigning persons to jobs where each assignment utilizes at least two scarce resources and the resource utilization is dependent on the person and the type of task. A practical situation where the above might occur is a slaughter house where the “cutters” are assigned to different cut patterns. In this case the resources are the time, the cost and the productivity measured in terms of quality and amount of the end products.In this paper we study the resource constrained assignment problem and derive several classes of valid inequalities based on the properties of the knapsack and assignment polytopes.We also present an algorithm that uses both the linear programming and the Lagrangean relaxation of the original problem in order to solve the separation problem. Some computational experiments are presented.

An O(n3) algorithm is described for solving algebraic assigment problems.

A class of combinatorial optimization problems with sum- and bottleneck objective function is described, having the following probabilistic asymptotic behaviour: With probability tending to one the ratio between worst and optimal objective function value approaches one as the size of the problem tends to infinity. Problems belonging to this class are among others quadratic assignment problems, as well as certain combinatorial and graph theoretical optimization problems. The obtained results suggest that even very simple heuristic algorithms incline to yield good solutions for high dimensional problems of this class.

We propose a parallel branch and bound algorithm for the quadratic assignment problem; this algorithm has been implemented on an asynchronous multiprocessor machine with shared memory (the Cray X-MP). For problems with size n ≥ 10, the improvement in using n processors is very close to n , and moreover very good results are obtained for a classical example from the literature with size 12.

We give an example of iterative dual changes in Assignment Problems which does not converge to the solution. To built up the example we use properties of the Fibonacci Sequence.

By generalizing matroid axiomatics we provide a framework in which independence systems may be classified. The concept is applied to independence systems arising from well known combinatorial optimization problems such as k-matroid intersection, matchoid, vertex packing in finite graphs and travelling salesman problems.

Local search is widely used to solve approximately NP-complete combinatorial optimization problems. But, little is known about quality of obtained local minima, for a given neighborhood. We concentrate on one of the most difficult optimization problems, the Quadratic Assignment Problem, and we give an upper bound for the quality of solutions obtained with deepest local search. Moreover, other recently established results on the traveling salesman problem, the graph bipartitioning problem and the maximum independent set problem can be deduced as particular cases.

This article is a brief exposition of some of the important links between machine learning and combinatorial optimization. We explain how efficient `learnability' in standard probabilistic models of learning is linked to the existence of efficient randomized algorithms for certain natural combinatorial optimization problems, and we discuss the complexity of some of these optimization problems.

Local search and its variants simulated annealing and tabu search are very popular meta-heuristics to approximatively solve NP-hard optimization problems. Several experimental studies in the literature have shown that in practice some problems (e.g. the Traveling Salesman Problem, Quadratic Assignment Problem) behave very well with these heuristics, whereas others do not (e.g. the Low Autocorrelation Binary String Problem). The autocorrelation function, introduced by Weinberger, measures the ruggedness of a landscape which is formed by a cost function and a neighborhood. We use a derived parameter, named the autocorrelation coefficient, as a tool to better understand these phenomena. In this paper we mainly study cost functions including penalty terms. Our results can be viewed as a first attempt to theoretically justify why it is often better in practice to enlarge the solution space and add penalty terms than to work solely on feasible solutions. Moreover, some new results as well as previously known results allow us to obtain a hierarchy of combinatorial optimization problems relatively to their ruggedness. Comparing this classification with experimental results reported in the literature yields a good agreement between ruggedness and difficulty for local search methods. In this way, we are also able to justify theoretically why a neighborhood is better than another for a given problem.

We extend the classical linear assignment problem to the case where the cost of assigning agent j to task i is a multiplication of task i’s cost parameter by a cost function of agent j. The cost function of agent j is a linear function of the amount of resource allocated to the agent. A solution for our assignment problem is defined by the assignment of agents to tasks and by a resource allocation to each agent. The quality of a solution is measured by two criteria. The first criterion is the total assignment cost and the second is the total weighted resource consumption. We address these criteria via four different problem variations. We prove that our assignment problem is NP-hard for three of the four variations, even if all the resource consumption weights are equal. However, and somewhat surprisingly, we find that the fourth variation is solvable in polynomial time. In addition, we find that our assignment problem is equivalent to a large set of important scheduling problems whose complexity has been an open question until now, for three of the four variations.

We discuss the relationship between Gilmore–Lawler lower bounds with decomposition for the quadratic assignment problem and a lagrangean relaxation of a particular integer programming formulation

The frequency assignment problem is the problem of assigning frequencies to transmission links such that either no interference occurs, or the amount of interference is minimized. We present an approximation algorithm for this problem that is inspired by Karmarkar's interior point potential reduction approach to combinatorial optimization problems. A non convex quadratic model of the problem is developed, that is very compact as all interference constraints are incorporated in the objective function. Moreover, optimizing this model may result in finding multiple solutions to the problem simultaneouly. Several preprocessing techniques are discussed. We report on computational experience with both real-life and randomly generated instances.

The quadratic assignment problem (QAP) is among the hardest combinatorial optimization problems. Very few instances of this problem can be solved in polynomial time. In this paper we address the problem of allocating rooms among people in a suitable shape of corridor with some constraints of undesired neighborhood. We give a linear time algorithm for this problem that we formulate as a QAP.