Probabilistic asymptotic properties of some combinatorial optimization 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.     

Generalized asymptotic functions in nonconvex multiobjective optimization problems

In this paper, we use generalized asymptotic functions and second-order asymptotic cones to develop a general existence result for the nonemptiness of the proper efficient solution set and a sufficient condition for the domination property in nonconvex multiobjective optimization problems. A new necessary condition for a point to be efficient or weakly efficient solution is given without any convexity assumption. We also provide a finer outer estimate for the asymptotic cone of the weakly efficient solution set in the quasiconvex case. Finally, we apply our results to the linear fractional multiobjective optimization problem.     

Probabilistic analysis of optimization algorithms-some aspects from a practical point of view

In this paper the utility and the difficulties of probabilistic analysis for optimization algorithms are discussed. Such an analysis is expected to deliver valuable criteria-better than the worst-case complexity-for the efficiency of an algorithm in practice. The author has done much work of that kind in the field of linear programming. Based on that experience he gives some insight into the general principles for such an approach. He reports on some typical and representative attempts to analyze algorithms, resp. problems, of linear and combinatorial optimization. For each case he describes the problem, the stochastic model under consideration, the algorithm, the results, and tries to give a brief idea of the way these results could be obtained. He concludes with a discussion of some drawbacks and difficulties in that field of research. Among these are the strong sensibility with respect to the chosen model, the restriction of results to the asymptotic case, the restriction to somehow inefficient algorithms, etc. These points are the reasons why probabilistic analysis is of limited value for practice today. On the other hand, they show which principal problems should be attacked in the future to obtain the desired utility.     

Simulated annealing with asymptotic convergence for nonlinear constrained optimization

In this paper, we present constrained simulated annealing (CSA), an algorithm that extends conventional simulated annealing to look for constrained local minima of nonlinear constrained optimization problems. The algorithm is based on the theory of extended saddle points (ESPs) that shows the one-to-one correspondence between a constrained local minimum and an ESP of the corresponding penalty function. CSA finds ESPs by systematically controlling probabilistic descents in the problem-variable subspace of the penalty function and probabilistic ascents in the penalty subspace. Based on the decomposition of the necessary and sufficient ESP condition into multiple necessary conditions, we present constraint-partitioned simulated annealing (CPSA) that exploits the locality of constraints in nonlinear optimization problems. CPSA leads to much lower complexity as compared to that of CSA by partitioning the constraints of a problem into significantly simpler subproblems, solving each independently, and resolving those violated global constraints across the subproblems. We prove that both CSA and CPSA asymptotically converge to a constrained global minimum with probability one in discrete optimization problems. The result extends conventional simulated annealing (SA), which guarantees asymptotic convergence in discrete unconstrained optimization, to that in discrete constrained optimization. Moreover, it establishes the condition under which optimal solutions can be found in constraint-partitioned nonlinear optimization problems. Finally, we evaluate CSA and CPSA by applying them to solve some continuous constrained optimization benchmarks and compare their performance to that of other penalty methods.     

Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems

Various conic relaxations of quadratic optimization problems in nonnegative variables for combinatorial optimization problems, such as the binary integer quadratic problem, quadratic assignment problem (QAP), and maximum stable set problem have been proposed over the years. The binary and complementarity conditions of the combinatorial optimization problems can be expressed in several ways, each of which results in different conic relaxations. For the completely positive, doubly nonnegative and semidefinite relaxations of the combinatorial optimization problems, we discuss the equivalences and differences among the relaxations by investigating the feasible regions obtained from different representations of the combinatorial condition which we propose as a generalization of the binary and complementarity condition. We also study theoretically the issue of the primal and dual nondegeneracy, the existence of an interior solution and the size of the relaxations, as a result of different representations of the combinatorial condition. These characteristics of the conic relaxations affect the numerical efficiency and stability of the solver used to solve them. We illustrate the theoretical results with numerical experiments on QAP instances solved by SDPT3, SDPNAL+ and the bisection and projection method.     

On the Cauchy problem for macroscopic model of pedestrian flows

In this paper, we discuss the limit behavior of hyperbolic systems of conservation laws with stiff relaxation terms to the local systems as the relaxation time tends to zero. The prototype is crowd models derived from crowd dynamics according to macroscopic scaling when the flow of crowds is supposed to satisfy the paradigms of continuum mechanics. Under an appropriate structural stability condition, the asymptotic expansion is obtained when one assumes the existence of a smooth solution to the equilibrium system. In this case, the local existence of a classical solution is also shown.     

Coupling ant colony systems with strong local searches

Ant colony system is a well known metaheuristic framework, and many efficient algorithms for different combinatorial optimization problems have been derived from this general framework. In this paper some directions for improving the original framework when a strong local search routine is available, are identified. In particular, some modifications able to speed up the method and make it competitive on large problem instances, on which the original framework tends to be weaker, are described. The resulting framework, called Enhanced Ant Colony System is tested on three well-known combinatorial optimization problems arising in the transportation field. Many new best known solutions are retrieved for the benchmarks available for these optimization problems.     

The asymptotic probabilistic behaviour of quadratic sum assignment problems

In this paper a surprising probabilistic behaviour of quadratic sum assignment problems is shown. The relative difference between worst and optimal solution value tends to zero with probability tending to one as the size of the problem goes to infinity. This result suggests that for high dimensional quadratic assignment problems even very simple approximation algorithms can in practice yield good suboptimal solutions.     

Provably good solutions for the traveling salesman problem

The determination of true optimum solutions of combinatorial optimization problems is seldomly required in practical applications. The majority of users of optimization software would be satisfied with solutions of guaranteed quality in the sense that it can be proven that the given solution is at most a few percent off an optimum solution. This paper presents a general framework for practical problem solving with emphasis on this aspect. A detailed discussion along with a report about extensive computational experiments is given for the traveling salesman problem.     

Subset simulation for unconstrained global optimization

Global optimization problem is known to be challenging, for which it is difficult to have an algorithm that performs uniformly efficient for all problems. Stochastic optimization algorithms are suitable for these problems, which are inspired by natural phenomena, such as metal annealing, social behavior of animals, etc. In this paper, subset simulation, which is originally a reliability analysis method, is modified to solve unconstrained global optimization problems by introducing artificial probabilistic assumptions on design variables. The basic idea is to deal with the global optimization problems in the context of reliability analysis. By randomizing the design variables, the objective function maps the multi-dimensional design variable space into a one-dimensional random variable. Although the objective function itself may have many local optima, its cumulative distribution function has only one maximum at its tail, as it is a monotonic, non-decreasing, right-continuous function. It turns out that the searching process of optimal solution(s) of a global optimization problem is equivalent to exploring the process of the tail distribution in a reliability problem. The proposed algorithm is illustrated by two groups of benchmark test problems. The first group is carried out for parametric study and the second group focuses on the statistical performance.     

Coradiant sets and $$\varepsilon $$-efficiency in multiobjective optimization

In multi-parametric programming an optimization problem is solved as a function of certain parameters, where the parameters are commonly considered to be bounded and continuous. In this paper, we use the case of strictly convex multi-parametric quadratic programming (mp-QP) problems with affine constraints to investigate problems where these conditions are not met. Based on the combinatorial solution approach for mp-QP problems featuring bounded and continuous parameters, we show that (i) for unbounded parameters, it is possible to obtain the multi-parametric solution if there exists one realization of the parameters for which the optimization problem can be solved and (ii) for binary parameters, we present the equivalent mixed-integer formulations for the application of the combinatorial algorithm. These advances are combined into a new, generalized version of the combinatorial algorithm for mp-QP problems, which enables the solution of problems featuring both unbounded and binary parameters. This novel approach is applied to mixed-integer bilevel optimization problems and the parametric solution of the dual of a convex problem.     

Exponential convergence for a periodically driven semilinear heat equation

We consider a semilinear heat equation in one space dimension, with a periodic source at the origin. We study the solution, which describes the equilibrium of this system and we prove that, as the space variable tends to infinity, the solution becomes, exponentially fast, asymptotic to a steady state. The key to the proof of this result is a Harnack type inequality, which we obtain using probabilistic ideas.     

二次分配问题的大洪水算法求解

大洪水算法是一种求解组合优化问题的独特方法,该方法通过模拟洪水上涨的过程来达到求解一些组合优化难题的目的.本文运用该方法求解二次分配问题(QAP),设计了相应的算法程序,并对QAPLIB(二次分配基准问题库)中的算例进行了实验测试,结果表明,大洪水算法可以快速有效地求得二次分配问题的优化解,是求解二次分配问题的一个新的较好方案.     

Probabilistische analyse von heuristiken der kombinatorischen optimierung – ein überbllck

To various problems of combinatorial optimization we consider the question how the value of the optimal solution resp. the values of some approximative solutions are predetermined with high probability to a given distribution. We present results to probabilistic analysis of heuristics. We consider the problems Traveling Salesman, Minimum Perfect Matching. Minimum Spanning Tree, Linear Optimization, Bin Packing, Multi-processor-Scheduling, Subset Sum and some problems to random graphs.     

Inverse Scattering for the Problem with Impedance-type Boundary

This paper deals with the inverse scattering problems for the Helmholtz equation with impedance boundary condition. It aims at reconstructing the unknown impedance coefficient from the knowledge of scattered wave fields. We generalize the concept of classic solution (CS) to optimal solution (OS) by a nonlinear optimization problem. Then, based on potential theory, we establish an inversion procedure to get the approximation of OS which is defined as the regularized solution (RS) in this paper. The convergence result for RS is proven from which one can get OS and CS stably and efficiently.     

The Million-Variable “March” for Stochastic Combinatorial Optimization

Combinatorial optimization problems have applications in a variety of sciences and engineering. In the presence of data uncertainty, these problems lead to stochastic combinatorial optimization problems which result in very large scale combinatorial optimization problems. In this paper, we report on the solution of some of the largest stochastic combinatorial optimization problems consisting of over a million binary variables. While the methodology is quite general, the specific application with which we conduct our experiments arises in stochastic server location problems. The main observation is that stochastic combinatorial optimization problems are comprised of loosely coupled subsystems. By taking advantage of the loosely coupled structure, we show that decomposition-coordination methods provide highly effective algorithms, and surpass the scalability of even the most efficiently implemented backtracking search algorithms.     

Budgeted matching and budgeted matroid intersection via the gasoline puzzle

Many polynomial-time solvable combinatorial optimization problems become NP-hard if an additional complicating constraint is added to restrict the set of feasible solutions. In this paper, we consider two such problems, namely maximum-weight matching and maximum-weight matroid intersection with one additional budget constraint. We present the first polynomial-time approximation schemes for these problems. Similarly to other approaches for related problems, our schemes compute two solutions to the Lagrangian relaxation of the problem and patch them together to obtain a near-optimal solution. However, due to the richer combinatorial structure of the problems considered here, standard patching techniques do not apply. To circumvent this problem, we crucially exploit the adjacency relations on the solution polytope and, surprisingly, the solution to an old combinatorial puzzle.     

Elementary landscape decomposition of the 0-1 unconstrained quadratic optimization

Landscapes’ theory provides a formal framework in which combinatorial optimization problems can be theoretically characterized as a sum of an especial kind of landscape called elementary landscape. The elementary landscape decomposition of a combinatorial optimization problem is a useful tool for understanding the problem. Such decomposition provides an additional knowledge on the problem that can be exploited to explain the behavior of some existing algorithms when they are applied to the problem or to create new search methods for the problem. In this paper we analyze the 0-1 Unconstrained Quadratic Optimization from the point of view of landscapes’ theory. We prove that the problem can be written as the sum of two elementary components and we give the exact expressions for these components. We use the landscape decomposition to compute autocorrelation measures of the problem, and show some practical applications of the decomposition.     

Simulated N-Body: New Particle Physics-Based Heuristics for a Euclidean Location-Allocation Problem

The general facility location problem and its variants, including most location-allocation and P-median problems, are known to be NP-hard combinatorial optimization problems. Consequently, there is now a substantial body of literature on heuristic algorithms for a variety of location problems, among which can be found several versions of the well-known simulated annealing algorithm. This paper presents an optimization paradigm that, like simulated annealing, is based on a particle physics analogy but is markedly different from simulated annealing. Two heuristics based on this paradigm are presented and compared to simulated annealing for a capacitated facility location problem on Euclidean graphs. Experimental results based on randomly generated graphs suggest that one of the heuristics outperforms simulated annealing both in cost minimization as well as execution time. The particular version of location problem considered here, a location-allocation problem, involves determining locations and associated regions for a fixed number of facilities when the region sizes are given. Intended applications of this work include location problems with congestion costs as well as graph and network partitioning problems.     

半导体中扩散方程初始边界问题的解的渐近性

In this paper, we study the asymptotic behavior of the solutions to the initial boundary value problem for unipolar drift diffusion equations for semiconductors. Under the proper assumptions on doping profile and initial value, we prove that the smooth solutions to these evolutionary problems tend to the unique stationary solution exponentially as time tends to infinity.