Extragradient Methods for Vector Equilibrium Problems in Banach Spaces

We consider the vector equilibrium problem, which extends the scalar equilibrium problem to vector valued bifunctions, in a Banach space setting. We propose an extragradient method for solving this problem. Under suitable assumptions on the bifunction, we prove that the generated sequence is weakly convergent to a solution of the problem. Then, we propose a regularization procedure which ensures strong convergence of the generated sequence to a solution of the problem.     

The stable crews problem

In this paper the classical stable roommates problem is generalized to situations when the two partners in a pair perform different roles. We propose an efficient algorithm to decide the existence of a stable matching in this problem.     

Buyback problem with discrete concave valuation functions

We discuss an online discrete optimization problem called the buyback problem. In the literature of the buyback problem, the valuation function representing the total value of selected elements is given by a linear function. In this paper, we consider a generalization of the buyback problem using nonlinear valuation functions. We propose an online algorithm for the problem with discrete concave valuation functions, and show that it achieves the tight competitive ratio, i.e., the competitive ratio of the proposed algorithm is equal to the known lower bound for the problem.     

Minimum norm solution to the positive semidefinite linear complementarity problem

In this article, we present an algorithm to compute the minimum norm solution of the positive semidefinite linear complementarity problem. We show that its solution can be obtained using the alternative theorems and a convenient characterization of the solution set of a convex quadratic programming problem. This problem reduces to an unconstrained minimization problem with once differentiable convex objective function. We propose an extension of Newton's method for solving the unconstrained optimization problem. Computational results show that convergence to high accuracy often occurs in just a few iterations.     

Minimum power multicasting problem in wireless networks

In this paper we deal with the minimum power multicasting (MPM) problem in wireless ad-hoc networks. By using an appropriate choice of the decision variables and by exploiting the topological properties of the problem, we are able to define an original formulation based on a Set Covering model. Moreover, we propose for its solution two exact procedures that include a preprocessing technique that reduces the huge number of the model’s constraints. We also report some experimental results carried out on a set of randomly generated test problems.     

A dynamic programming algorithm for the bilevel knapsack problem

We propose an efficient dynamic programming algorithm for solving a bilevel program where the leader controls the capacity of a knapsack, and the follower solves the resulting knapsack problem. We propose new recursive rules and show how to solve the problem as a sequence of two standard knapsack problems.     

Metaheuristics for the linear ordering problem with cumulative costs

The linear ordering problem with cumulative costs (LOPCC) is a variant of the well-known linear ordering problem, in which a cumulative propagation makes the objective function highly non-linear. The LOPCC has been recently introduced in the context of mobile-phone telecommunications. In this paper we propose two metaheuristic methods for this NP-hard problem. The first one is based on the GRASP methodology, while the second one implements an Iterated Greedy-Strategic Oscillation procedure. We also propose a post-processing based on Path Relinking to obtain improved outcomes. We compare our methods with the state-of-the-art procedures on a set of 218 previously reported instances. The comparison favors the Iterated Greedy - Strategic Oscillation with the Path Relinking post-processing, which is able to identify 87 new best objective function values.     

Vehicle routing problems with alternative paths: An application to on-demand transportation

The class of vehicle routing problems involves the optimization of freight or passenger transportation activities. These problems are generally treated via the representation of the road network as a weighted complete graph. Each arc of the graph represents the shortest route for a possible origin–destination connection. Several attributes can be defined for one arc (travel time, travel cost, etc.), but the shortest route modeled by this arc is computed according to a single criterion, generally travel time. Consequently, some alternative routes proposing a different compromise between the attributes of the arcs are discarded from the solution space. We propose to consider these alternative routes and to evaluate their impact on solution algorithms and solution values through a multigraph representation of the road network. We point out the difficulties brought by this representation for general vehicle routing problems, which drives us to introduce the so-called fixed sequence arc selection problem (FSASP). We propose a dynamic programming solution method for this problem. In the context of an on-demand transportation (ODT) problem, we then propose a simple insertion algorithm based on iterative FSASP solving and a branch-and-price exact method. Computational experiments on modified instances from the literature and on realistic data issued from an ODT system in the French Doubs Central area underline the cost savings brought by the proposed methods using the multigraph model.     

A control type method for solving the Cauchy–Stokes problem

In this work, we propose an approximate optimal control formulation of the Cauchy problem for the Stokes system. Here the problem is converted into an optimization one. In order to handle the instability of the solution of this ill-posed problem, a regularization technique is developed. We add a term in the least square function which happens to vanish while the algorithm converges. The efficiency of the proposed method is illustrated by numerical experiments.     

An evolutionary approach for bandwidth multicoloring problems

In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.     

A fast approximation algorithm for solving the complete set packing problem

We study the complete set packing problem (CSPP) where the family of feasible subsets may include all possible combinations of objects. This setting arises in applications such as combinatorial auctions (for selecting optimal bids) and cooperative game theory (for finding optimal coalition structures). Although the set packing problem has been well-studied in the literature, where exact and approximation algorithms can solve very large instances with up to hundreds of objects and thousands of feasible subsets, these methods are not extendable to the CSPP since the number of feasible subsets is exponentially large. Formulating the CSPP as an MILP and solving it directly, using CPLEX for example, is impossible for problems with more than 20 objects. We propose a new mathematical formulation for the CSPP that directly leads to an efficient algorithm for finding feasible set packings (upper bounds). We also propose a new formulation for finding tighter lower bounds compared to LP relaxation and develop an efficient method for solving the corresponding large-scale MILP. We test the algorithm with the winner determination problem in spectrum auctions, the coalition structure generation problem in coalitional skill games, and a number of other simulated problems that appear in the literature.     

Integral equation methods for scattering by infinite rough surfaces

In this paper, we consider the Dirichlet and impedance boundary value problems for the Helmholtz equation in a non‐locally perturbed half‐plane. These boundary value problems arise in a study of time‐harmonic acoustic scattering of an incident field by a sound‐soft, infinite rough surface where the total field vanishes (the Dirichlet problem) or by an infinite, impedance rough surface where the total field satisfies a homogeneous impedance condition (the impedance problem). We propose a new boundary integral equation formulation for the Dirichlet problem, utilizing a combined double‐ and single‐layer potential and a Dirichlet half‐plane Green's function. For the impedance problem we propose two boundary integral equation formulations, both using a half‐plane impedance Green's function, the first derived from Green's representation theorem, and the second arising from seeking the solution as a single‐layer potential. We show that all the integral equations proposed are uniquely solvable in the space of bounded and continuous functions for all wavenumbers. As an important corollary we prove that, for a variety of incident fields including an incident plane wave, the impedance boundary value problem for the scattered field has a unique solution under certain constraints on the boundary impedance. Copyright © 2003 John Wiley & Sons, Ltd.     

一种无证书的环签名方案和一个基于身份的多重签名方案

在这篇文章里,我们用双线性对构造了一种无证书的环签名方案,并证明它是无条件匿名的,且在随机预言模型中,计算性Diffie-Hellman问题是难解的,我们方案在适应性选择消息攻击下是存在性不可伪造的,它的安全性比在基于身份的公钥密码体制下高.本文首次用多线性形式构造了一个基于身份的广播多重签名方案,它的安全性是基于计算性Diffie-Hellman困难问题.     

A new exact method for the two-dimensional orthogonal packing problem

The two-dimensional orthogonal packing problem (2OPP) consists in determining if a set of rectangles (items) can be packed into one rectangle of fixed size (bin). In this paper we propose two exact algorithms for solving this problem. The first algorithm is an improvement on a classical branch&bound method, whereas the second algorithm is based on a new relaxation of the problem. We also describe reduction procedures and lower bounds which can be used within enumerative methods. We report computational experiments for randomly generated benchmarks which demonstrate the efficiency of both methods: the second method is competitive compared to the best previous methods. It can be seen that our new relaxation allows an efficient detection of non-feasible instances.     

Equivalence of variational inequality problems to unconstrained minimization

In this paper we propose a class of merit functions for variational inequality problems (VI). Through these merit functions, the variational inequality problem is cast as unconstrained minimization problem. We estimate the growth rate of these merit functions and give conditions under which the stationary points of these functions are the solutions of VI. This work was supported by the state key project “Scientific and Engineering Computing”.     

Boundary Identification for a Blast Furnace

In this paper,the authors discuss an inverse boundary problem for the axi- symmetric steady-state heat equation,which arises in monitoring the boundary corrosion for the blast-furnace.Measure temperature at some locations are used to identify the shape of the corrosion boundary. The numerical inversion is complicated and consuming since the wear-line varies during the process and the boundary in the heat problem is not fixed.The authors suggest a method that the unknown boundary can be represented by a given curve plus a small perturbation,then the equation can be solved with fixed boundary,and a lot of computing time will be saved. A method is given to solve the inverse problem by minimizing the sum of the squared residual at the measuring locations,in which the direct problems are solved by axi- symmetric fundamental solution method. The numerical results are in good agreement with test model data as well as industrial data,even in severe corrosion case.     

Fourier Moment Method with Regularization for the Cauchy Problem of Helmholtz Equation

In this paper, we consider the reconstruction of the wave field in a bounded domain. By choosing a special family of functions, the Cauchy problem can be transformed into a Fourier moment problem. This problem is ill-posed. We propose a regularization method for obtaining an approximate solution to the wave field on the unspecified boundary. We also give the convergence analysis and error estimate of the numerical algorithm. Finally, we present some numerical examples to show the effectiveness of this method.     

Approximation of dense-n/2-subgraph and table compression problems

We develop improved approximation algorithms for two NP-hard problems: the dense-n/2-subgraph and table compression.Based on SDP relaxation and advanced rounding techniques,we first propose 0. 5982 and 0. 5970-approximation algorithms respec- tively for the dense-n/2-subgraph problem (DSP) and the table compression problem (TCP). Then we improve these bounds to 0. 6243 and 0. 6708 respectively for DSP and TCP by adding triangle inequalities to strengthen the SDP relaxation.The results for TCP beat the 0. 5 bound of a simple greedy algorithm on this problem,and hence answer an open question of Anderson in an affirmative way.     

Inner Approximation Method for a Reverse Convex Programming Problem

In this paper, we consider a reverse convex programming problem constrained by a convex set and a reverse convex set, which is defined by the complement of the interior of a compact convex set X. We propose an inner approximation method to solve the problem in the case where X is not necessarily a polytope. The algorithm utilizes an inner approximation of X by a sequence of polytopes to generate relaxed problems. It is shown that every accumulation point of the sequence of optimal solutions of the relaxed problems is an optimal solution of the original problem.     

强向量均衡问题与不动点问题的粘性逼近算法

讨论了强向量均衡问题与非扩张映射不动点问题的公共解.首先,给出了强向量均衡问题的辅助问题,并在适当的条件下,证明了其解的存在性和唯一性结果.然后,利用这些结果,提出了强向量均衡问题与非扩张映射不动点问题公共解的粘性逼近算法,并进一步证明了,在适当的条件下,由该算法产生的迭代序列强收敛于强向量均衡问题和非扩张映射不动点问题的公共解.