A dual local search framework for combinatorial optimization problems with TSP application

In practice, solving realistically sized combinatorial optimization problems to optimality is often too time-consuming to be affordable; therefore, heuristics are typically implemented within most applications software. A specific category of heuristics has attracted considerable attention, namely local search methods. Most local search methods are primal in nature; that is, they start the search with a feasible solution and explore the feasible space for better feasible solutions. In this research, we propose a dual local search method and customize it to solve the traveling salesman problem (TSP); that is, a search method that starts with an infeasible solution, explores the dual space—each time reducing infeasibility, and lands in the primal space to deliver a feasible solution. The proposed design aims to replicate the designs of optimal solution methodologies in a heuristic way. To be more specific, we solve a combinatorial relaxation of a TSP formulation, design a neighborhood structure to repair such an infeasible starting solution, and improve components of intermediate dual solutions locally. Sample-based evidence along with statistically significant t-tests support the superiority of this dual design compared to its primal design counterpart.     

Moltiplicatori diH 1,2(Ω)

Riassunto In questo lavoro viene studiato l'insieme dei moltiplicatori diH ^1,2(Ω) con Ω aperto diR ⁿ. Nella prima parte vengono analizzate alcune proprietà di struttura dello spazio dei moltiplicatori, nella seconda viene data una caratterizzazione degli elementi di tale spazio.

---

Summary In this paper we study the space of multipliers ofH ^1,2(Ω). We give first some general properties of such space, then we give a characterization of its elements.

---

---

Lavoro eseguito nell'ambito dell'attività dei Gruppi di Ricerca del C.N.R. nell'anno 1970.

---

L'autore è borsista del C.N.R., contratto No. 115.3059.05177.     

Yang-baxter operators arising from (co)algebra structures

We construct parametrized Yang-Baxter operators from algebra struc-tures, transfer the theory to coalgebras, and find the cases where such operators arising from (co) algebras are isomorphic. We give examples in dimension 2.     

Makespan minimization in open shops: A polynomial time approximation scheme

In this paper, we demonstrate the existence of a polynomial time approximation scheme for makespan minimization in the open shop scheduling problem with an arbitrary fixed numberm of machines. For the variant of the problem where the number of machines is part of the input, it is known that the existence of an approximation scheme would implyP = NP. Hence, our result draws a precise separating line between approximable cases (i.e., withm fixed) and non-approximable cases (i.e., withm part of the input) of this shop problem. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Supported by the DIMANET/PECO Program of the European Union.Supported by a research fellowship of the Euler Institute for Discrete Mathematics and its Applications. This research was done while Gerhard Woeginger was with the Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands.     

Nowhere-Zero 5-Flows and Even (1,2)-Factors

A graph G = (V, E) admits a nowhere-zero k-flow if there exists an orientation H = (V, A) of G and an integer flow ${\varphi:A \to \mathbb{Z}}$ such that for all ${a \in A, 0 < |\varphi(a)| < k}$ . Tutte conjectured that every bridgeless graphs admits a nowhere-zero 5-flow. A (1,2)-factor of G is a set ${F \subseteq E}$ such that the degree of any vertex v in the subgraph induced by F is 1 or 2. Let us call an edge of G, F-balanced if either it belongs to F or both its ends have the same degree in F. Call a cycle of G F-even if it has an even number of F-balanced edges. A (1,2)-factor F of G is even if each cycle of G is F-even. The main result of the paper is that a cubic graph G admits a nowhere-zero 5-flow if and only if G has an even (1,2)-factor.     

Indecomposable Representations of the Superalgebra B(1,2)

Finite-dimensional indecomposable superbimodules over the superalgebra B(1,2) are treated. We propound a method for constructing indecomposable alternative superbimodules over B(1,2) containing a given socle (such can be presented by any irreducible module over B(1,2)). The method is based on adding on the Jordan basis. Also, for the characteristic 3 case, we give examples of Jordan indecomposable superbimodules which are not alternative.     

A parabolic problem arising in Financial Mathematics

We study a parabolic problem arising in Financial Mathematics. Under suitable conditions, we prove the existence and uniqueness of solutions in a general domain using the method of upper and lower solutions and a diagonal argument.     

A penalty-shift-insertion-based algorithm to minimize total flow time in no-wait flow shops

This paper proposes a penalty-shift-insertion (PSI)-based algorithm for the no-wait flow shop scheduling problem to minimize total flow time. In the first phase, a penalty-based heuristic, derived from Vogel’s approximation method used for the classic transportation problem is used to generate an initial schedule. In the second phase, a known solution is improved using a forward shift heuristic. Then the third phase improves this solution using a job-pair and a single-job insertion heuristic. Results of the computational experiments with a large number of randomly generated problem instances show that the proposed PSI algorithm is relatively more effective and efficient in minimizing total flow time in a no-wait flow shop than the state-of-the-art procedures. Statistical significance of better results obtained by the proposed algorithm is also reported.     

A functional equation arising in dynamic programming

In this paper, we utilize some fixed point theorems of contractive type to present a few existence and uniqueness theorems for a functional equation arising in dynamic programming of continuous multistage decision processes.     

一种改进的蚁群算法及其在TSP中的应用

蚁群算法是一种求解复杂组合优化问题的新的拟生态算法,也是一种基于种群的启发式仿生进化算法,属于随机搜索算法的一种,并用于较好地解决TSP问题.然而此算法也有它自己的缺陷,如易于陷入局部优化、搜索时间长等.通过对基本蚁群算法的介绍及相关因素的分析,提出了一种改进的蚁群算法,用于解决TSPLAB问题的10个问题,并与参考文献中的F-W、NCSOM、ASOM算法进行比较,计算机仿真结果表明了改进算法的有效性.如利用改进的蚁群算法解决lin105问题,其最优解为14382.995933(已知最优解为14379),相对误差是0.0209%,计算出的最小值几乎接近于已知最优解.     

On the Grassmanian of lines in PG(4,q) and R(1,2) reguli

An R(1,2) regulus is a collection of q+1 mutually skew planes in PG(5,q) with the property that a line meeting three of the planes must meet all the planes. An (l,π)-configuration is the collection of lines in PG(4,q) meeting a line l and a plane π skew to l. A correspondence between (l,π)-configurations in PG(4-,q) and R(1,2) reguli in the associated Grassmanian space G(1,4) is examined. Bose has shown that R(1,2) reguli represent Baer subplanes of a Desarguesian projective plane in a linear representation of the plane. With the purpose of examining the relations between two Baer subplanes of PG(2,q²), the author examines the possible intersections of a 3-flat with an R(1,2) regulus.     

关于广义逆矩阵A(1,2)T,S的刻画推广

本文通过一类秩等方程给出了A(1,2)T,S、A(2)T,S的一种刻画及一类秩等方程有解的充分必要条件,推广了文献[1]、[4]的结论,并改进了[4]关于矩阵A的Drazin逆Ad的一类刻画的证明.     

A note on makespan minimization in two-stage flexible flow shops with uniform machines

We consider the two-stage flexible flow shop makespan minimization problem with uniform parallel machines. Soewandi and Elmaghraby [Soewandi, H., Elmaghraby, S., 2003. Sequencing on two-stage hybrid flowshops with uniform machines to minimize makespan. IIE Transaction 35, 467–477] developed a heuristic (S–E) and derived a machine speed-dependent worst-case ratio bound for it. We point out that this bound works well when the uniform machines have approximately equal speeds but is not indicative of the performance of the S–E heuristic when the machine speeds are in a wide range. Motivated by this observation, we propose an alternative tight machine-speed dependent worst-case bound for the S–E heuristic that works well when the machine speeds vary significantly. We then combine the two speed-dependent ratio bounds into a speed-independent bound. Our findings facilitate the narrowing of the gap between experimental performance and worst-case bound for the S–E heuristic.     

Flag-Transitive 2-Designs Arising from Line-Spreads in PG(2n-1,2)

A Singer cycle in GL(n,q) is an element of order q permuting cyclically all the nonzero vectors. Let be a Singer cycle in GL(2n,2). In this note we shall count the number of lines in PG (2n-1,2) whose orbit under the subgroup of index 3 in the Singer group is a spread. The lines constituting such a spread are permuted cyclically by the group ³, hence gives rise to a flag-transitive 2-(2²ⁿ ,4,1) design.     

A problem arising in finite population sampling theory

A probability sampling design is a probability functionp(s) on subsetss of [1, ..., i, ..., N. Let _ij denote the joint inclusion probability fori andj. The problem is to determine conditions under which a fixed size (n) sampling designp exists so that _ij (x _i –x _j )² for a vector of real numbersx=(x ₁, ...,x _N ), or equivalently, so that for some order of the coefficients _ik = _ij + _jk . Some necessary conditions for the proportionality to hold are obtained, and it is conjectured that it is satisfied only in special circumstances.