A simple randomised algorithm for convex optimisation

We consider maximising a concave function over a convex set by a simple randomised algorithm. The strength of the algorithm is that it requires only approximate function evaluations for the concave function and a weak membership oracle for the convex set. Under smoothness conditions on the function and the feasible set, we show that our algorithm computes a near-optimal point in a number of operations which is bounded by a polynomial function of all relevant input parameters and the reciprocal of the desired precision, with high probability. As an application to which the features of our algorithm are particularly useful we study two-stage stochastic programming problems. These problems have the property that evaluation of the objective function is #P-hard under appropriate assumptions on the models. Therefore, as a tool within our randomised algorithm, we devise a fully polynomial randomised approximation scheme for these function evaluations, under appropriate assumptions on the models. Moreover, we deal with smoothing the feasible set, which in two-stage stochastic programming is a polyhedron.     

Computational experience with approximation algorithms for the set covering problem

The Set Covering problem (SCP) is a well known combinatorial optimization problem, which is NP-hard. We conducted a comparative study of nine different approximation algorithms for the SCP, including several greedy variants, fractional relaxations, randomized algorithms and a neural network algorithm. The algorithms were tested on a set of random-generated problems with up to 500 rows and 5000 columns, and on two sets of problems originating in combinatorial questions with up to 28160 rows and 11264 columns.On the random problems and on one set of combinatorial problems, the best algorithm among those we tested was a randomized greedy algorithm, with the neural network algorithm very close in second place. On the other set of combinatorial problems, the best algorithm was a deterministic greedy variant, and the randomized algorithms (both randomized greedy and neural network) performed quite poorly. The other algorithms we tested were always inferior to the ones mentioned above.     

Scheduling Classes on a College Campus

We consider the problem of scheduling a set of classes to classrooms with the objective of minimizing the number of classrooms used. The major constraint that we must obey is that no two classes can be assigned to the same classroom at the same time on the same day of the week. We present an algorithm that produces a nearly optimal schedule for an arbitrary set of classes. The algorithm's first stage produces a packing of classes using a combination of a greedy algorithm and a non-bipartite matching and the second stage consists of a bipartite matching.First we show that for one variant of the problem our algorithm produces schedules that require a number of classrooms that is always within a small additive constant of optimal. Then we show that for an interesting variant of the problem the same algorithm produces schedules that require a small constant factor more classrooms than optimal. Finally, we report on experimental results of our algorithm using actual data and also show how to create schedules with other desirable characteristics.     

The multicriteria p-facility median location problem on networks

In this paper we discuss the multicriteria p-facility median location problem on networks with positive and negative weights. We assume that the demand is located at the nodes and can be different for each criterion under consideration. The goal is to obtain the set of Pareto-optimal locations in the graph and the corresponding set of non-dominated objective values. To that end, we first characterize the linearity domains of the distance functions on the graph and compute the image of each linearity domain in the objective space. The lower envelope of a transformation of all these images then gives us the set of all non-dominated points in the objective space and its preimage corresponds to the set of all Pareto-optimal solutions on the graph. For the bicriteria 2-facility case we present a low order polynomial time algorithm. Also for the general case we propose an efficient algorithm, which is polynomial if the number of facilities and criteria is fixed.     

An Outer Approximation Algorithm Guaranteeing Feasibility of Solutions and Approximate Accuracy of Optimality

We treat a concave programming problem with a compact convex feasible set. Assuming the differentiability of the convex functions which define the feasible set, we propose two solution methods. Those methods utilize the convexity of the feasible set and the property of the normal cone to the feasible set at each point over the boundary. Based on the proposed two methods, we propose a solution algorithm. This algorithm takes advantages over classical methods: (1) the obtained approximate solution is always feasible, (2) the error of such approximate value can be evaluated properly for the optimal value of such problem, (3) the algorithm does not have any redundant iterations.     

Finding all solutions of affine generalized Nash equilibrium problems with one-dimensional strategy sets

We consider a class of generalized Nash equilibrium problems with quadratic cost functions and common linear constraints for all players. Further we focus on the case where every player has a single strategy variable within a bounded set. For this problem class we present an algorithm that is able to compute all solutions and that terminates finitely. Our method is based on a representation of the solution set as a finite union of polyhedral sets using sign conditions for the derivatives of the cost and constraint functions. The effectiveness of the algorithm is shown in various examples from literature.     

带有边集限制的最均匀支撑树问题

本在无向网络中，建立了带有边集限制的最均匀支撑树问题的网络模型．中首先解决最均匀支撑树问题，并给出求无向网络中最均匀支撑树的多项式时间算法；然后，给出了求无向网络中带有边集限制的最小树多项式时间算法；最后，在已解决的两个问题的基础上解决了带有边集限制的最均匀支撑树问题．     

Computing the minimal covering set

We present the first polynomial-time algorithm for computing the minimal covering set of a (weak) tournament. The algorithm draws upon a linear programming formulation of a subset of the minimal covering set known as the essential set. On the other hand, we show that no efficient algorithm exists for two variants of the minimal covering set–the minimal upward covering set and the minimal downward covering set–unless P equals NP. Finally, we observe a strong relationship between von Neumann–Morgenstern stable sets and upward covering on the one hand, and the Banks set and downward covering on the other.     

Algorithms of common solutions for variational inclusions, mixed equilibrium problems and fixed point problems

In this paper, we present an iterative algorithm for finding a common element of the set of solutions of a mixed equilibrium problem and the set of fixed points of an infinite family of nonexpansive mappings and the set of a variational inclusion in a real Hilbert space. Furthermore, we prove that the proposed iterative algorithm has strong convergence under some mild conditions imposed on algorithm parameters.     

一种新修正的求解变分不等式的双次梯度外梯度算法

当可行集为一光滑凸函数的下水平集时, 本文提出一种修正的双次梯度外梯度算法(MTSEGA)用于求解Hilbert空间中单调且Lipschitz连续的变分不等式. MTSEGA在每步迭代过程中仅需计算向半空间的两次投影及一次映射的值. 在与已知算法相同的假设条件下, 证明了新算法产生的序列能弱收敛到相关问题的一个解.     

Hybrid methods with regularization for minimization problems and asymptotically strict pseudocontractive mappings in the intermediate sense

In this paper we introduce an iterative algorithm for finding a common element of the fixed point set of an asymptotically strict pseudocontractive mapping S in the intermediate sense and the solution set of the minimization problem (MP) for a convex and continuously Frechet differentiable functional in Hilbert space. The iterative algorithm is based on several well-known methods including the extragradient method, CQ method, Mann-type iterative method and hybrid gradient projection algorithm with regularization. We obtain a strong convergence theorem for three sequences generated by our iterative algorithm. In addition, we also prove a new weak convergence theorem by a modified extragradient method with regularization for the MP and the mapping S.     

一类非凸不可微规划的算法

讨论一类带非凸不可微函数约束的非凸不可微规划的求解,提出一种基于分枝定界技巧的算法,该算法具有全局收敛性．     

Quasi-concave functions on meet-semilattices

This paper deals with maximization of set functions defined as minimum values of monotone linkage functions. In previous research, it has been shown that such a set function can be maximized by a greedy type algorithm over a family of all subsets of a finite set. In this paper, we extend this finding to meet-semilattices.We show that the class of functions defined as minimum values of monotone linkage functions coincides with the class of quasi-concave set functions. Quasi-concave functions determine a chain of upper level sets each of which is a meet-semilattice. This structure allows development of a polynomial algorithm that finds a minimal set on which the value of a quasi-concave function is maximum. One of the critical steps of this algorithm is a set closure. Some examples of closure computation, in particular, a closure operator for convex geometries, are considered.     

Shape and topology optimization for elliptic boundary value problems using a piecewise constant level set method

The aim of this paper is to propose a variational piecewise constant level set method for solving elliptic shape and topology optimization problems. The original model is approximated by a two-phase optimal shape design problem by the ersatz material approach. Under the piecewise constant level set framework, we first reformulate the two-phase design problem to be a new constrained optimization problem with respect to the piecewise constant level set function. Then we solve it by the projection Lagrangian method. A gradient-type iterative algorithm is presented. Comparisons between our numerical results and those obtained by level set approaches show the effectiveness, accuracy and efficiency of our algorithm.     

Quadratic problems defined on a convex hull of points

In this paper we consider an algorithm for a class of quadratic problems defined on a polytope which is described as the convex hull of a set of points. The algorithm is based on simplex partitions using convex underestimating functions.     

Finding the shortest paths by node combination

By repeatedly combining the source node’s nearest neighbor, we propose a node combination (NC) method to implement the Dijkstra’s algorithm. The NC algorithm finds the shortest paths with three simple iterative steps: find the nearest neighbor of the source node, combine that node with the source node, and modify the weights on edges that connect to the nearest neighbor. The NC algorithm is more comprehensible and convenient for programming as there is no need to maintain a set with the nodes’ distances. Experimental evaluations on various networks reveal that the NC algorithm is as efficient as Dijkstra’s algorithm. As the whole process of the NC algorithm can be implemented with vectors, we also show how to find the shortest paths on a weight matrix.     

An automatic algorithm selection approach for the multi-mode resource-constrained project scheduling problem

This paper investigates the construction of an automatic algorithm selection tool for the multi-mode resource-constrained project scheduling problem (MRCPSP). The research described relies on the notion of empirical hardness models. These models map problem instance features onto the performance of an algorithm. Using such models, the performance of a set of algorithms can be predicted. Based on these predictions, one can automatically select the algorithm that is expected to perform best given the available computing resources. The idea is to combine different algorithms in a super-algorithm that performs better than any of the components individually. We apply this strategy to the classic problem of project scheduling with multiple execution modes. We show that we can indeed significantly improve on the performance of state-of-the-art algorithms when evaluated on a set of unseen instances. This becomes important when lots of instances have to be solved consecutively. Many state-of-the-art algorithms perform very well on a majority of benchmark instances, while performing worse on a smaller set of instances. The performance of one algorithm can be very different on a set of instances while another algorithm sees no difference in performance at all. Knowing in advance, without using scarce computational resources, which algorithm to run on a certain problem instance, can significantly improve the total overall performance.     

Methods for optimizing gas transmission networks

We describe two methods for the optimization of gas transmission networks. The first method reduces the number of variables in the optimization problem by eliminating the pipe-flow variables. The second method solves an optimization problem with the full set of variables to achieve better behaviour. These two methods are compared by a series of tests based on the British Gas NTS (National Transmission System). The results of these tests are reported. By formulating the network problem as an optimization problem we have been able to replace heuristics by well proven methods. The reliability of the algorithm using the reduced set of unknowns varied depending on the size of problem and the type of objective function being minimized. The algorithm using the full set of unknowns had no such difficulties, even though it needs to be used with some care. The algorithm is robust in the sense that when the objective function has the necessary continuities, there is a feasible point and the penalty terms ensure positive curvature, then a solution is found reliably. The algorithm based on the reduced set of unknowns is considerably faster than that using the full set, when it succeeds. The factor between the times taken ranges from 1.2 to 5 (average 3) for the smallest network. For the second case comparison is harder since the reduced set algorithm was given a head start in five cases. For the other five the factor is between 2.3 and 8.3. For the largest problem there is just one case in which the comparison is on equal terms, and here the factor is 18. It is clear that the reliability of the full set algorithm is bought at a considerable cost which rises as the problem gets bigger. The main conclusion is that the Sequential Augmented Lagrange Method yields a reliable algorithm for minimizing objective functions of practical interest based on gas networks such as the British Gas National Transmission System. It is not satisfactory to carry over to the case with machines techniques like those of the nodal and loop methods which work well on networks with no machines.     

Combination between global and local methods for solving an optimization problem over the efficient set

In this paper, we propose an algorithm for globally solving optimization problems over efficient sets. The algorithm is established based on a branch and bound scheme in which the bounding procedure is performed by using the well known weak duality theorem in Lagrange duality. A suitable combination of this algorithm with a local search procedure in d.c. optimization (named DCA) leads to a promising global algorithm, whose efficiency is more or less confirmed by computational experiments on a large set of test problems.