G Royer

G Ramasamy

P Eudes

8 Be, 12 C, 16 O, 20 Ne, 24 Mg, and 32 S nuclei and alpha clustering within a generalized liquid drop model

The potential energy governing the shape and the entrance and decay channels of the 12 C, 16 O, 20 Ne, 24 Mg, and 32 S 4n-nuclei has been determined within a generalized liquid drop model. Different three-dimensional and planar shapes have been investigated: linear chain, triangle, square, tetrahedron, pentagon, trigonal bipyramid, square pyramid, hexagon, octahedron, octogon and cube. The rms radii of the linear chains are higher than the experimental rms radii of the ground states. The binding energies of the planar shapes at the contact point are lower than the ones of the three-dimensional configurations. The α particle plus A-4 daughter configuration leads always to the lowest potential barrier relatively to the sphere configuration.

Introduction

Hydrogen burning in stars leads to a dense and hot core of helium and to the nucleosynthesis of other nuclei having a possible n-α structure: 16 O, 20 Ne, 24 Mg, 28 Si, 32 S, ... In these 4n-nuclei the clustertype states coexist with the mean-field-type states [1]. In 12 C the ground state wave function contains a large amount of 3α cluster wave function. Experimentally, a new high spin 5 -state has been observed recently. It fits well the ground state rotational band of an equilateral triangular spinning top [2]. In 16 O recent calculations lead for the ground state to a tetrahedral configuration of α particles in agreement with the energy spectrum and with the electromagnetic properties [3,4] while some excited states are due to the mean-field-type excitation mode while other ones are due to the cluster structure of α+ 12 C. In connection with the excited 0 + 2 Hoyle state of 12 C and possible excited Hoyle state of 16 O, the α condensate character of the α-linear chain has been proposed after comparing a large number of Brink functions with Tohsaki-Horiuchi-Schuck-Röpke wave functions [5,6].

The generalized liquid drop model (GLDM) previously defined to describe the fission, fusion, ... processes [7][8][9] has been used to determine the L-dependent potential energy of the following planar or three-dimensional α clusters: aligned α chains, isosceles triangle, square, tetrahedron, pentagon, trigonal bipyramid, square pyramid, hexagon, octahedron, octogon and cube.

Generalized liquid drop model

The GLDM energy is the sum of the volume, surface, Coulomb and proximity energies.

For two separated spherical nuclei :

E V = -15.494 (1 -1.8I 2 1 )A 1 + (1 -1.8I 2 2 )A 2 MeV, (1)
E S = 17.9439 (1 -2.6I 2 1 )A 2/3 1 + (1 -2.6I 2 2 )A 2/3 2 MeV, (2)
E C = 0.6e 2 Z 2 1 /R 1 + 0.6e 2 Z 2 2 /R 2 + e 2 Z 1 Z 2 /r, ( 3
)
where I i is the relative neutron excess.

The proximity energy must be added to the surface energy to take into account the effects of the nuclear forces between the surfaces in regard in a gap or a neck between nuclei.

Calculations using Antisymmetrized Molecular Dynamics and Fermionic Molecular Dynamics and without assuming α clustering led for the different states to triangular α-configurations with different angles allowing the reproduction of the low-lying spectrum [10,11]. Using effective field theory and Monte Carlo lattice calculations it has been shown that the 12 C ground state and the first excited state have a compact triangular configuration while the Hoyle state and the second excited state have an obtuse triangular configuration of alpha clusters [12]. These predictions are strengthened by the observation of a new high spin 5 -state at 22. 4 MeV compatible with a ground state rotational band of an equilateral triangular spinning top with a D 3h symmetry. Then the Hoyle state is interpreted as the band head of the stretching vibration or breathing mode of this triangular configuration [2].

These oblate ternary configurations have been studied within the GLDM in placing three α particles at the tops on an isosceles triangle characterized by the angle θ. At the contact point the energy of the linear chain of three α particles (θ=180 deg.) is higher than the energy of the equilateral triangular shape, the energy difference reaching 7.4 MeV. This is also in favor of an equilateral triangular configuration of the ground state (the energy being almost constant between 120 and 180 degrees). The experimental rms charge radius of the ground state is < r 2 > 1/2 = 2.47 fm. Within the GLDM, at the contact point the rms radius is 2.43 fm for a triangular shape and 3.16 fm for a linear chain. Furthermore the empirical electric quadrupole moment is negative which disagrees with the configuration of three-aligned α particles for the ground state shape [9].

16 O nucleus

For the ground state a tetrahedral molecule of alpha particles is predicted [3,4] and for the first excited spin-0 state a square configuration [3]. In Fig. 1 the energies of these two configurations determined from the GLDM are shown. At the contact point between the four spherical α particles the rms radius is 2.54 fm for a tetrahedron, 2.83 fm for a square and 4.15 fm for a prolate linear chain. Experimentally the rms charge radius of the ground state is < r 2 > 1/2 = 2.70 fm. The ground state has probably not a linear chain configuration. The binding energy is higher for the tetrahedral molecule than for the square shape since for these configurations the proximity energy plays a very important role and the tetrahedron is linked by six bonds and the square by only four bonds. On the contrary, the Coulomb repulsion is lower for the square. The energy difference between the two shapes is 13.7 MeV which is close to Q 4α (14.4 MeV), the energy of the 0 + 6 state (15.1 MeV) and 14.0 MeV the energy of a 0 + state. The relative energies at the contact point are respectively 0, 1.3, 4.4, 9.3 and 16 MeV for L = 0, 2, 4, 6 and 8 for the tetrahedral shape and 0, 1.1, 3.5, 7.4 and 12.6 MeV for L = 0, 2, 4, 6 and 8 for the square shape. The ground state can also be described as double closed shell wave functions but several low-lying excited states are also described within the 12 C+ 4 He cluster. The potential energies of the 12 C+ 4 He, 8 Be+ 8 Be, and aligned 6 Li+ 4 He+ 6 Li systems have been calculated assuming a spherical shape for the compound nucleus and each nucleus (see Fig. 2). The threshold energies are : 7.2 MeV for Q4 He+ 12 C , 14.4 for Q 4α , 14.6 for Q8 Be+ 8 Be , and 35.3 for Q6 Li+ 4 He+ 6 Li . The top of the barriers corresponds to separated nuclei maintained in unstable equilibrium by the balance between the attractive nuclear proximity forces and the repulsive Coulomb forces. Quasimolecular 12 C+ 4 He one-body shapes have almost the same energy than the spherical compound nucleus.

20 Ne nucleus

The trigonal bipyramid, square pyramid and pentagonal molecules have been studied. Their energies are compared in Fig. 3. The rms radius is 2.76 fm for a trigonal bipyramid, 2.79 fm for a square pyramid and 3.29 fm for a pentagon at the contact point. The experimental rms charge radius is < r 2 > 1/2 = 3.01 fm, lower than the rms radius of a prolate linear chain. The binding energy of the trigonal bipyramid is the highest. The number of bonds is five for the pentagon, eight for the square pyramid and nine for the trigonal bipyramid. At the contact point, the energy difference between the trigonal bipyramid and the square pyramid is 21.3 MeV and 15.3 between the square pyramid and the pentagon, while Q 5α = 19.2 MeV. For the trigonal bipyramid the relative energies to the ground state at the contact point are respectively 0, 1.7, 5.6, 11.7 and 20.1 MeV for L = 0, 2, 4, 6 and 8 . For the square pyramid the values are 0, 1.0, 3.2, 6.8 and 11.7 MeV for L = 0, 2, 4, 6 and 8 . For the pentagon it is : 0, 0.6, 2.0, 4.3 and 7.3 MeV for L = 0, 2, 4, 6 and 8 . Experimentally the energies of the 2 + 0 and 4 + 0 states are respectively 1.63 and 4.25 MeV.

The ground state band contains the 16 O+ 4 He cluster at most 70% and the potential energies of the 16 O+ 4 He, 12 C+ 8 Be, 10 B+ 10 B, and linear 8 Be+ 4 He+ 8 Be systems have been determined assuming spherical shapes for all the nuclei (see Fig. 4). The respective threshold energies are : 4.73 MeV for Q16 O+ 4 He , 11.98 for Q8 Be+ 12 C , 19.35 for Q8 Be+ 4 He+ 8 Be , and 31.14 MeV for Q10 B+ 10 B . In the 16 O+ 4 He channel quasimolecular one-body shapes have roughly the same energy than the spherical nucleus and the minimum has a cluster structure corresponding to the two 4 He and 16 O nuclei in contact.

24 Mg nucleus

The energies of the hexagonal and octahedral α-molecules are displayed in Fig. 5. The experimental rms charge radius of the ground state is only < r 2 > 1/2 = 3.06 fm. At the contact point the rms radius is 2.85 fm for an octahedron and 3.79 fm for an hexagon, which excludes the planar shape and the linear chain as possible ground state shapes. The binding energy is higher for the octahedral configuration since there are twelve bonds for the octahedron and only six for the hexagon.

The potential energies of the 16 O+ 8 Be, are also shown in Fig.

S nucleus

The octogonal and cubic α-molecules have been investigated. Their energies are compared in Fig. 6. The experimental rms charge radius is < r 2 > 1/2 = 3.26 fm. The rms radius is 4.85 fm for an octogon and 3.37 fm for a cube at the contact point which seems to exclude the planar and linear configurations. The binding energy is higher for the cubic configuration than for the octogonal shape, indeed there are twelve bonds for the cube and only eight for the octogon. The potential energies of the 28 Si+ 4 He, 24 Mg+ 8 Be, 20 Ne+ 12 C, and 16 O+ 16 O systems are also given in Fig. 6. The threshold energies are : 6.95 MeV for Q4

Binding energy

The binding energy of these nuclei can be reproduced within the molecular structure picture by summing the binding energy of n alphas plus the number of bonds multiplied by around 2. The binding energy these nuclei can also be obtained within a core+α cluster model since this energy is the sum of the binding energies of one alpha and the one of the daughter nucleus plus roughly the and the proximity energy between the two nuclei. (5)

Conclusion

Within an α-particle model the energy of the 12 C, 16 O, 20 Ne, 24 Mg and 32 S nuclei has been determined assuming different α-molecule configurations: linear chain, triangle, square, tetrahedron, pentagon, trigonal bipyramid, square pyramid, hexagon, octahedron, octogon, and cube. Within a macroscopic approach the potential barriers governing the entrance and decay channels of these 4n-nuclei via alpha emission or absorption have also been compared.

The rms radii of the prolate chains seem incompatible with the experimental rms radii of the ground states. The binding energies of the three-dimensional molecules are higher than the binding energies of the planar shapes. The core+α cluster system leads always to the lowest potential barrier. The binding energy can be obtained within the sum of the binding energy of n alphas plus 2.4 MeV multiplied by the number of bonds or by the sum of the binding energy of one alpha and the one of the daughter nucleus plus the Coulomb energy and the proximity energy between the two nuclei.

Fig. 1 :

 1 Fig. 1: Potential energy of α-tetrahedron (left part) and of the α-square (right part) as functions of the angular momentum (in unit) and rms radius.

Fig. 2 :

 2 Fig. 2: Potential energy governing the 12 C+ 4 He, 8 Be+ 8 Be, and 6 Li+ 4 He+ 6 Li nuclear systems versus the distance between the mass centres (at L = 0).

Fig. 3 :Fig. 4 :

 34 Fig. 3: Potential energy of the trigonal bipyramid (on the left), square pyramid (on the right) and the pentagon (on the bottom) as functions of the angular momentum (in unit) and rms radius.

Fig. 5 :

 5 Fig. 5: Potential energies of an hexagon and an octahedron from the contact point as a function of the rms radius and potential barriers governing the 16 O+ 8 Be, 12 C+ 12 C, 8 Be+ 8 Be+ 8 Be, and 10 B+ 4 He+ 10 B reactions versus the distance between the mass centres.

Fig. 6 :

 6 Fig. 6: Potential energies of octogonal and cubic molecules from the contact point as a function of the rms radius and potential barriers governing the 28 Si+ 4 He, 24 Mg+ 8 Be, 20 Ne+ 12 C, and 16 O+ 16 O systems versus the distance between the mass centres.

4 4 )

 44 MeV. B( 12 C) = 3 × B(α) + 3(bonds) × 2.42 MeV, B( 16 O) = 4 × B(α) + 6(bonds) × 2.41 MeV, B( 20 Ne) = 5 × B(α) + 8(bonds) × 2.40 MeV, B( 24 Mg) = 6 × B(α) + 12(bonds) × 2.37 MeV. (It is difficult to explain this value of 2.4 MeV per bond since it does not correspond to the sum of the mean Coulomb energy and proximity energy by bond.

B( 12

 12 C) = B( 8 Be) + B(α) + 7.37 MeV, B( 16 O) = B( 12 C) + B(α) + 7.16 MeV, B( 20 Ne) = B( 16 O) + B(α) + 4.73 MeV, B( 24 Mg) = B( 20 Ne) + B(α) + 9.32 MeV.

  12 C+ 12 C, 8 Be+ 8 Be+ 8 Be, and 10 B+ 4 He+ 10 B systems

  5. The different Q values are : 9.32 MeV Q4 He+ 20 Ne , 13.93 for Q12 C+ 12 C , 14.14 for Q8 Be+ 16 O , 28.48 for Q 6α , 28.76 for Q8 Be+ 8 Be+ 8 Be , and 40.46 for Q10 B+ 4 He+ 10 B .

  He+ 28 Si , 16.54 for Q16 O+ 16 O , 17.02 for Q8 Be+ 24 Mg , 18.97 for Q12 C+ 20 Ne , 30.96 for Q12 C+ 8 Be+ 12 C , 34.17 for Q14 N + 4 He+ 14 N , and 45.42 for Q 8α . The energy of the 28 Si+ 4 He one-body nucleus is relatively constant till the spherical nucleus allowing the cohabitation of different quasimolecular shapes. The superdeformed band contains the 16 O+ 16 O component by about 44 %.


Sandro Pirkwieser
email: pirkwieser|raidl@ads.tuwien.ac.at

Günther R Raidl

Jakob Puchinger
email: jakobp@csse.unimelb.edu.au

Combining Lagrangian Decomposition with an Evolutionary Algorithm for the Knapsack Constrained Maximum Spanning Tree Problem

We present a Lagrangian decomposition approach for the Knapsack Constrained Maximum Spanning Tree problem yielding upper bounds as well as heuristic solutions. This method is further combined with an evolutionary algorithm to a sequential hybrid approach. Experimental investigations, including a comparison to a previously suggested simpler Lagrangian relaxation based method, document the advantages of the new approach. Most of the upper bounds derived by Lagrangian decomposition are optimal, and together with the evolutionary algorithm, large instances with up to 12000 nodes can be either solved to provable optimality or with a very small remaining gap in reasonable time.

Introduction

The Knapsack Constrained Maximum Spanning Tree (KCMST) problem has been introduced by Yamamato and Kubo [START_REF] Yamamato | Invitation to the Traveling Salesman's Problem[END_REF]. It arises in practice in certain situations where the aim is to design a profitable communication network under a strict limit on total costs for cable laying or similar resource constraints.

We are given an undirected connected graph G = (V, E) with node set V and edge set E ⊆ V × V representing all possible connections. Each edge e ∈ E has associated a weight w e ∈ Z + (corresponding to costs) and a profit p e ∈ Z + . In addition, a weight limit (capacity) c > 0 is specified. A feasible KCMST is a spanning tree T ⊆ E on G, i.e. a cycle-free subgraph connecting all nodes, whose weight e∈T w e does not exceed c. The objective is to find a KCMST with maximum total profit e∈T p e . More formally, we can introduce binary variables x e , ∀e ∈ E, indicating which edges are part of the solution, i.e. x e = 1 ↔ e ∈ T and x e = 0 otherwise, and write the KCMST problem as:

max p(x) = e∈E p e x e (1)
s. t. x represents a spanning tree [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF] e∈E w e x e ≤ c (3)

x e ∈ {0, 1} ∀e ∈ E (4)
Obviously, the problem represents a combination of the classical minimum spanning tree problem (with changed sign in the objective function) and the classical 0-1 knapsack problem due to constraint (3). Yamada et al. [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF] gave a proof for the KCMST problem's N P-hardness.

After summarizing previous work for this problem in the next section, we present a Lagrangian decomposition approach in Section 3. It is able to yield tight upper bounds as well as lower bounds corresponding to feasible heuristic solutions. Section 4 describes an evolutionary algorithm for the KCMST problem utilizing the edge-set representation. Section 5 explains how this evolutionary algorithm can be effectively combined with the Lagrangian decomposition approach in a sequential manner. Experimental results are presented in Section 6. They document the excellent performance of the whole hybrid system, which is able to solve almost all test instances with graphs of up to 12000 nodes to provable optimality or with a very small gap in reasonable time.

Previous Work

While numerous algorithms and studies exist for the standard minimum spanning tree problem, the 0-1 knapsack problem, and various related constrained network design problems, we are only aware of the following literature specifically addressing the KCMST problem.

Yamamato and Kubo [START_REF] Yamamato | Invitation to the Traveling Salesman's Problem[END_REF] introduced this problem, but neither proved N Phardness nor presented any solution algorithms. This was first done by Yamada et al. [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF]. They described a Lagrangian relaxation approach in which the knapsack constraint (3) is relaxed, yielding the simple maximum spanning tree problem which can be solved efficiently. The Lagrangian dual problem of finding a best suited Lagrangian multiplier for the relaxed weight constraint is solved by a simple bisection method. The Lagrangian relaxation approach also yields feasible heuristic solutions, which are further improved by a 2-opt local search. In order to also determine provable optimal solutions for instances of restricted size, the Lagrangian relaxation is embedded in a branch-and-bound framework. While the approach is able to optimally solve instances with up to 1000 nodes and 2800 edges when edge weights and profits are uncorrelated, performance degrades substantially in the correlated case.

The only other work for the KCMST problem we are aware of is the first author's master thesis [START_REF] Pirkwieser | A Lagrangian Decomposition Approach Combined with Metaheuristics for the Knapsack Constrained Maximum Spanning Tree Problem[END_REF]. It formed the basis for this article, and we refer to it for further details, in particular for more computational results.

The problem also exists in its minimization version [START_REF] Aggarwal | Minimal spanning tree subject to a side constraint[END_REF], for which Jörnsten and Migdalas document the superiority of Lagrangian decomposition, and subsequently solving each subproblem to optimality, for generating valid bounds [START_REF] Jörnsten | Designing a minimal spanning tree network subject to a budget constraint[END_REF].

Lagrangian Decomposition for the KCMST Problem

Lagrangian relaxation is a commonly used technique from the area of mathematical programming to determine upper bounds for maximization problems. Though the solutions obtained are in general infeasible for the original problem, they can lend themselves to create feasible solutions and thus to derive lower bounds, too. For a general introduction to Lagrangian relaxation, see [START_REF] Fisher | The Lagrangian Relaxation Method for Solving Integer Programming Problems[END_REF][START_REF] Fisher | An application oriented guide to Lagrangean Relaxation[END_REF][START_REF] Beasley | Lagrangian relaxation[END_REF]. Lagrangian Decomposition (LD) is a special variant that can be meaningful when there is evidence of two or possibly more intertwined subproblems, and each of them can be efficiently solved on its own by specialized algorithms.

As the KCMST problem is a natural combination of the maximum spanning tree problem and the 0-1 knapsack problem, we apply LD by aiming at such a partitioning. For this purpose, we split variables x e , ∀e ∈ E, by introducing new variables y e and including linking constraints, leading to the following equivalent reformulation: Stating KCMST-LD(λ) in a more compact way and emphasizing the now independent subproblems yields

max p(x) = e∈E p e x e ( 5
(MST) max {(p -λ) T x | x = a spanning tree, x ∈ {0, 1} E } + (14) (KP) max {λ T y | w T y ≤ c, y ∈ {0, 1} E }. ( 15
)
For a particular λ, the maximum spanning tree (MST) subproblem ( 14) can be efficiently solved by standard algorithms. In our implementation we apply Kruskal's algorithm [START_REF] Kruskal | On the shortest spanning subtree of a graph and the travelling salesman problem[END_REF] based on a union-find data structure when the underlying graph is sparse and Prim's algorithm [START_REF] Prim | Shortest connection networks and some generalizations[END_REF] utilizing a pairing heap with dynamic insertion [START_REF] Fredman | The pairing heap: a new form of self-adjusting heap[END_REF] for dense graphs. The 0-1 knapsack subproblem ( 15) is known to be weakly N P-hard, and practically highly efficient dynamic programming approaches exist [START_REF] Kellerer | Knapsack Problems[END_REF], whereas we apply the COMBO algorithm [START_REF] Martello | Dynamic programming and strong bounds for the 0-1 knapsack problem[END_REF].

It follows from Lagrangian relaxation theory that for any choice of Lagrangian multipliers λ, the optimal solution value to KCMST-LD(λ), denoted by v(KCMST-LD(λ)), is always at least as large as the optimal solution value of the original KCMST problem, i.e., KCMST-LD(λ) provides a valid upper bound. To obtain the tightest (smallest) upper bound, we have to solve the Lagrangian dual problem:

min λ∈R E v(KCMST-LD(λ)). ( 16
)
This dual problem is piecewise linear and convex, and standard algorithms like an iterative subgradient approach can be applied for (approximately) solving it. More specifically, we use the volume algorithm [START_REF] Barahona | The volume algorithm: producing primal solutions with a subgradient method[END_REF] which has been reported to outperform standard subgradient methods in many cases including set covering, set partitioning, max cut, and Steiner tree problems [START_REF] Haouaria | A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem[END_REF]. In fact, preliminary tests on the KCMST problem also indicated its superiority over a standard subgradient algorithm [START_REF] Pirkwieser | A Lagrangian Decomposition Approach Combined with Metaheuristics for the Knapsack Constrained Maximum Spanning Tree Problem[END_REF]. The volume algorithm's name is inspired by the fact that primal solutions are considered and that their values come from approximating the volumes below the active faces of the dual problem.

Strength of the Lagrangian Decomposition

According to integer linear programming theory, Lagrangian relaxation always yields a bound that is at least as good as the one obtained by the corresponding linear programming (LP) relaxation. The Lagrangian relaxation's bound can be substantially better when the relaxed problem does not fulfill the integrality property, i.e., the solution to the LP relaxation of the relaxed problem -KCMST-LD(λ) in our case -is in general not integer. For seeing whether or not this condition is fulfilled here, we have to consider both independent subproblems. Compact models having the integrality property exist for MST, see e.g. [START_REF] Magnanti | Optimal trees[END_REF]. Furthermore, the integrality property is obviously not fulfilled for the knapsack subproblem. Thus, we may expect to obtain bounds that are better than those from the linear programming relaxation of KCMST.

In comparison, in the Lagrangian relaxation approach from [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF] the knapsack constraint is relaxed and only the MST problem remains. This approach therefore fulfills the integrality property and, thus, is in general weaker than our LD.

We further remark that the proposed LD can in principle be strengthened by adding the cardinality constraint e∈E y e = |V |-1 to the knapsack subproblem. The resulting cardinality constrained knapsack problem is still only weakly N Phard, and pseudo-polynomial algorithms based on dynamic programming are known for it [START_REF] Kellerer | Knapsack Problems[END_REF]. Our investigations indicate, however, that the computational demand required for solving this refined formulation is in practice substantially higher and does not pay off the typically only small quality increase of the obtained bound [START_REF] Pirkwieser | A Lagrangian Decomposition Approach Combined with Metaheuristics for the Knapsack Constrained Maximum Spanning Tree Problem[END_REF].

Deriving Lower Bounds

In some iterations of the volume algorithm, the obtained spanning tree is feasible with respect to the knapsack constraint and can be directly used as a lower bound, hence resulting in a simple Lagrangian heuristic. In order to further improve such solutions this heuristic is strengthened by consecutively applying a local search based on the following edge exchange move.

1. Select an edge (u, v) ∈ E \ T to be considered for inclusion (see below). 2. Determine the path P ⊆ T connecting nodes u and v in the current tree.

Including e in T would yield the cycle P ∪ {(u, v)}. 3. Identify a least profitable edge ẽ ∈ P that may be replaced by (u, v) without violating the knapsack constraint:

ẽ = minarg p e | e ∈ E ∧ w(T ) -w e + w (u,v) ≤ c , ( 17
)
where w(T ) = e∈T w e . In case of ties, an edge with largest weight is chosen. 4. If replacing ẽ by (u, v) improves the solution, i.e.

p ẽ < p (u,v) ∨ (p ẽ = p (u,v) ∧ w ẽ > w (u,v)
), perform this exchange.

For selecting edge (u, v) in step 1 we consider two possibilities:

Random selection: Randomly select an edge from E \ T .

Greedy selection: At the beginning of the local search, all edges are sorted according to decreasing p e = p e -λ e , the reduced profits used to solve the MST subproblem. Then, in every iteration of local search, the next less profitable edge not active in the current solution is selected. This results in a greedy search where every edge is considered at most once.

Since Lagrangian multipliers are supposed to be of better quality in later phases of the optimization process, local search is only applied when the ratio of the incumbent lower and upper bounds is larger than a certain threshold τ . Local search stops after ρ consecutive non-improving iterations have been performed.

A Suitable Evolutionary Algorithm

Evolutionary algorithms (EAs) have often proven to be well suited for finding good approximate solutions to hard network design problems. In particular for constrained spanning tree problems, a large variety of EAs applying very different representations and variation operators have been described, see e.g. [START_REF] Julstrom | Edge sets: an effective evolutionary coding of spanning trees[END_REF] for an overview.

Here, we apply an EA based on a direct edge-set representation for heuristically solving the KCMST problem, since this encoding and its corresponding variation operators are known to provide strong locality and heritability. Furthermore, variation operators can efficiently be applied in time that depends (almost) only linearly on the number of nodes. In fact, our EA closely follows the description of the EA for the degree constrained minimum spanning tree problem in [START_REF] Julstrom | Edge sets: an effective evolutionary coding of spanning trees[END_REF]. Only the initialization and variation operators are adapted to conform with the knapsack constraint.

The general framework is steady-state, i.e. in each iteration one feasible offspring solution is created by means of recombination, mutation, and eventually local improvement, and it replaces the worst solution in the population. Duplicates are not allowed in the population; they are always immediately discarded. The EA's operators work as follows.

Initialization. To obtain a diversified initial population, a random spanning tree construction based on Kruskal's algorithm is used. Edges are selected with a bias towards those with high profits. The specifically applied technique is exactly as described in [START_REF] Julstrom | Edge sets: an effective evolutionary coding of spanning trees[END_REF]. In case a generated solution is infeasible with respect to the knapsack constraint, it is stochastically repaired by iteratively selecting a not yet included edge at random, adding it to the tree, and removing an edge with highest weight from the induced cycle. Recombination. An offspring is derived from two selected parental solutions in such a way that the new solution candidate always exclusively consists of inherited edges: In a first step all edges contained in both parents are immediately adopted. The remaining parental edges are merged into a single candidate list. From this list, we iteratively select edges by binary tournaments with replacement favoring high-profit edges. Selected edges are included in the solution if they do not introduce a cycle; otherwise, they are discarded. The process is repeated until a complete spanning tree is obtained. Finally, its validity with respect to the knapsack constraint is checked. An infeasible solution is repaired in the same way as during initialization, but only considering parental edges for inclusion. Mutation. We perform mutation by inserting a randomly selected new edge and removing another edge from the introduced cycle. The choice of the edge to be included is biased towards high-profit edges by utilizing a normallydistributed rank-based selection as described in [START_REF] Julstrom | Edge sets: an effective evolutionary coding of spanning trees[END_REF]. The edge to be removed from the induced cycle is chosen at random among those edges whose removal would retain a feasible solution. Local Search. With a certain probability, a newly derived candidate solution is further improved by the local search procedure described in Section 3.2.

Hybrid Lagrangian Evolutionary Algorithm

Preliminary tests clearly indicated that the EA cannot compete with the performance of LD in terms of running time and solution quality. However, following similar ideas as described in [START_REF] Haouaria | A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem[END_REF] for the price-collecting Steiner tree problem, we can successfully apply the EA for finding better final solutions after performing LD. Hereby, the EA is adapted to exploit a variety of (intermediate) results from LD. In detail, the following steps are performed after LD has terminated and before the EA is executed:

1. If the profit of the best feasible solution obtained by LD corresponds to the determined upper bound, we already have an optimal solution. No further actions are required. 2. For the selection of edges during initialization, recombination, and mutation of the EA, original edge profits p e are replaced by reduced profits p e = p e -λ e .

In this way, Lagrangian dual variables are exploited, and the heuristic search emphasizes the inclusion of edges that turned out to be beneficial in LD. 3. The edge set to be considered by the EA is reduced from E to a subset E containing only those edges that appeared in any of the feasible solutions encountered by LD. For this purpose, LD is extended to mark these edges. 4. The best feasible solution obtained by LD is included in the EA's initial population. 5. Finally, the upper bound obtained by LD is passed to the EA and exploited by it as an additional stopping criterion: When a solution with a corresponding total profit is found, it is optimal and the EA terminates.

Experimental Results

The described algorithms have been tested on a large variety of different problem instances, and comparisons have been performed in particular with the previous Lagrangian relaxation based method from [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF]. This section summarizes most important results; more details can be found in [START_REF] Pirkwieser | A Lagrangian Decomposition Approach Combined with Metaheuristics for the Knapsack Constrained Maximum Spanning Tree Problem[END_REF]. All experiments were run on a 1.6GHz Pentium M PC with 1.25GB RAM.

As in [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF], we consider instances based on random complete graphs K |V |γ and planar graphs P |V |,|E|γ . Since we could not obtain the original instances, we created them in the same way by our own. In addition we constructed larger maximal planar graphs P |V |γ . Parameter γ represents the type of correlation between profits and weights: uncorrelated ('u'): p e and w e , e ∈ E, are independently chosen from the integer interval [START_REF] Yamamato | Invitation to the Traveling Salesman's Problem[END_REF]100]; weakly correlated ('w'): w e is chosen as before, and p e := 0.8w e +v e , where v e is randomly selected from [START_REF] Yamamato | Invitation to the Traveling Salesman's Problem[END_REF]20]; strongly correlated ('s'): w e is chosen as before, and p e := 0.9w e + 10 .

For details on the methods used to construct the (maximal) planar graphs, we refer to [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF][START_REF] Pirkwieser | A Lagrangian Decomposition Approach Combined with Metaheuristics for the Knapsack Constrained Maximum Spanning Tree Problem[END_REF]. In case of complete graphs, the knapsack capacity is c = 20•|V |-20, in case of (maximal) planar graphs c = 35 • |V |. For each combination of graph type, graph size, and correlation, 10 instances have been considered.

We show and compare results for the Lagrangian relaxation (LR), Lagrangian relaxation with local search (LR+LS), and associated branch-and-bound (B&B) from [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF], our Lagrangian decomposition with the simple primal heuristic (LD) and optionally local search (LD+LS), and the combination of LD and the EA (LD+LS+EA).

Robust settings for strategy parameters have been determined by preliminary tests. For the results presented here the following setup has been used.

The volume algorithm within the LD approach terminates when either the lower and upper bounds become identical and, thus, an optimal solution has been reached, or when the upper bound did not improve over the last 500 iterations in case of planar graphs and 1000 iterations in case of complete graphs. For completeness, we provide the following further details for the volume algorithm based on its description in [START_REF] Barahona | The volume algorithm: producing primal solutions with a subgradient method[END_REF]: The target value T always is updated by T := 0.95LB and T := 0.475(LB + U B) for planar and complete graphs, respectively, with the exception T := 0.95T iff U B < 1.05T . Parameter f is initialized with 0.1 and multiplied by 0.67 after 20 consecutive red iterations when f > 10 -8 in case of planar graphs and f > 10 -6 for complete graphs and is multiplied by 1.1 after a green iteration when f < 1. Factor α is initialized with 0.1 and it is checked after every 100 and 200 iterations in case of planar and complete graphs, respectively, if the upper bound decreased less than 1%; if so and α > 10 -5 then α := 0.85α. All these update rules are similar to those used in [START_REF] Haouaria | A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem[END_REF].

For the optional local search, greedy edge selection is used for complete graphs and random edge selection for all others. The application threshold is set to τ = 0.99. As maximum number of iterations without improvement, ρ = 200 is used in case of uncorrelated and weakly correlated planar graphs, and ρ = 100 in all other cases.

For the EA, the population size is 100, binary tournament selection is used, and recombination and mutation are always applied. For the biasing towards edges with higher profits, parameters α and β (see [START_REF] Julstrom | Edge sets: an effective evolutionary coding of spanning trees[END_REF]) are both set to 1.5. Local search is performed with random edge selection for each new candidate solution with a probability of 20% with ρ = 50 and a maximum of 5000 total iterations for graphs having less than 8000 nodes and 10000 total iterations for larger graphs.

Results on planar and complete graphs are shown in Table 1. For LR, LR+LS, and B&B, they are adopted from [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF]. Average values based on 10 different instances are printed. Columns LB show obtained lower bounds, i.e. the objective values of the best feasible solutions. Upper bounds (U B) are expressed in terms of the relative gap to these lower bounds: gap = (U B -LB)/LB; corresponding standard deviations are listed in columns σ gap . Columns Opt show numbers of instances (out of 10) for which the gap is zero and, thus, optimality has been proven. Average CPU-times for the runs are printed in columns t in seconds, and the average numbers of iterations of the volume algorithm in columns iter.

With respect to the CPU-times listed for branch-and-bound, we remark that they were measured on an IBM RS/6000 44P Model 270 workstation, and therefore, they cannot directly be compared with the times from our methods. The maximum time limit for B&B was 2000 seconds.

Most importantly, we can see that LD obtains substantially smaller gaps than both, LR and LR+LS. In fact, LD's average gaps are never larger than 0.063%, and for a large number of instances, optimality is already proven. On the remaining instances, enhancing LD by applying local search is beneficial; in most cases gaps are significantly reduced, and a few more instances could be solved to proven optimality. Overall, only 40 out of 330 instances remain, for 586.6 268.9 1.78 10 0.17 801 7222.9 6.76 13.17 7 0.37 817 7222.9 6.76 13.17 which LD+LS was not able to find optimal solutions and prove their optimality.

As already observed in [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF], strongly correlated instances are typically harder to solve than uncorrelated ones. A comparison of the heuristic solutions obtained from LD+LS with solutions from an exact approach3 further indicated that almost all of them are actually optimal; LD+LS just cannot prove their optimality since the upper bounds were not tight enough. As a consequence, additionally applying the EA after LD+LS was not very meaningful for these instances. Tests not shown here confirmed that only in rare cases, gaps could further be reduced by the EA.

Our LD is extremely fast, needing for none of these instances more than seven seconds. The time overhead introduced by local search is also only very moderate, in particular since the improved heuristic solutions implied a faster convergence of the volume algorithm.

In order to investigate the usefulness of the proposed LD+LS+EA hybrid, we now turn to the larger maximal planar graphs, for which Table 2 presents results. For the EA, we additionally list the average number of EA iterations iter EA , the relative amount of edges discarded after performing LD red = (|E| -|E |)/|E| • 100%, and the number of optimal solutions Opt EA , among Opt, found by the EA.

Again, the solutions obtained by LD are already quite good and gaps are in general small. The inclusion of local search clearly increases the number of optimal solutions found, leaving only 21 out of all 180 instances for which optimality is not yet proven. The hybrid approach (LD+LS+EA) works almost perfectly: Gaps are reduced to zero, and thus proven optimal solutions are achieved for all but three instances. The values in column Opt EA document that the EA plays a significant role in finally closing gaps. The three remaining instances are solved with gaps less than 0.00003%.

In general, results of Tables 1 and2 indicate that it is harder to close the optimality gap for smaller than for larger instances. One reason seems to be that with increasing graph size, more edges have the same profit and weight values. Tests on other types of instances, with differently determined profits and weights, are therefore interesting future work.

Conclusions

We presented a Lagrangian decomposition approach for the N P-hard KCMST problem to derive upper bounds as well as heuristic solutions. Experimental results on large graphs revealed that the upper bounds are extremely tight, in fact most of the time even optimal. Heuristic solutions can be significantly improved by applying a local search, and many instances can be solved to provable optimality already in this way.

For the remaining, larger instances, a sequential combination of LD with an evolutionary algorithm has been described. The EA makes use of the edgeset encoding and corresponding problem-specific operators and exploits results from LD in several ways. In particular, the graph is shrunk by only considering edges also appearing in heuristic solutions of LD, Lagrangian dual variables are exploited by using final reduced costs for biasing the selection of edges in the EA's operators, and the best solution obtained from LD is provided to the EA as seed in the initial population.

Computational results document the effectiveness of the hybrid approach. The EA is able to close the gap and provide proven optimal solutions in almost all of the remaining difficult cases. Hereby, the increase in running time one has to pay is only moderate.

The logical next step we want to pursue is to enhance the branch-and-bound method from [START_REF] Yamada | Algorithms to solve the knapsack constrained maximum spanning tree problem[END_REF] by also utilizing the more effective LD or even the hybrid LD/EA instead of the simple Lagrangian relaxation.

In general, we believe that such combinations of Lagrangian relaxation and metaheuristics like evolutionary algorithms are highly promising for many combinatorial optimization tasks. Future work therefore includes the consideration

1 P 10000u 15 .

 115 854 294872.0 0.03 0.09 9 7.37 835 294872.0 0.03 0.099 12.42 853 39% 5000 294872.0 0.03 01102 341901.7 0.80 0.86 3 19.49 981 341904.0 0.12 0.20 7 26.97 919 46% 3503 341904.4 1087 330117.3 1.44 1.45 3 17.02 887 330122.0 0.03 0.09 9 39.37 922 23% 3968 330122.0 0.03 0.09 9 92 969 737450.2 0.07 0.12 7 24.63 956 737450.6 0.01 0.03 9 56.66 1029 39% 1877 737450.7 964 427406.4 0.19 0.39 7 25.51 1021 427406.9 0.06 0.09 7 61.62 1048 44% 1681 427407.2 1102 512985.4 0.38 0.48 3 32.69 1033 512986.9 0.08 0.13 7 77.05 1037 45% 2147 512987.3 1148 495164.0 1.14 1.38 2 34.38 1019 495169.5 0.04 0.08 8 141.99 1044 23% 8225 495169.6 0.02 0.06 9 1

Table 1 .

 1 Results of Lagrangian algorithms on planar and complete graphs.

	Instance	Yamada et al.[2] LR LR+LS B&B gap gap t[s] Opt t[s] iter [•10 -5 ] [•10 -5 ]	LD LB [•10 -5 ] [•10 -5 ] gap σ gap Opt t[s] iter	LD+LS LB gap σ gap Opt [•10 -5 ] [•10 -5 ]
	P 50,127u	948.2 454.1 0.43 10 0.19 983 3558.5 62.56 89.70 3 0.30 976 3559.0 47.58 49.16 3
	P 100,260u

Table 2 .

 2 Results of Lagrangian and hybrid algorithms on maximal planar graphs.

		Opt Opt
		gap
	LD+LS+EA	t[s] iter red iter EA LB gap σ
		Opt
		gap
	LD+LS	LB gap σ
		Opt t[s] iter
		gap
		gap σ
	LD	LB
		t[s] iter
		Instance

EA [•10

We also implemented a not yet published exact branch-and-cut algorithm, which is able to solve these instances to proven optimality.

of further problems, but also the closer investigation of other forms of collaboration between Lagrangian relaxation based methods and metaheuristics, including intertwined and parallel models.


Sam Huston
email: shuston@csse.unimelb.edu.au

Jakob Puchinger
email: jakobp@csse.unimelb.edu.au

Peter Stuckey

The Core Concept for 0/1 Integer Programming

In this paper we examine an extension of the core concept for the 0/1 Multidimensional Knapsack Problem (MKP) towards general 0/1 Integer Programming (IP) by allowing negative profits, weights and capacities. The core concept provides opportunities for heuristically solving the MKP, achieving higher quality solutions and shorter runtimes than general IP methods. We provide the theoretical foundations of the extended core concept and further provide computational experiments showing that we can achieve similar computational behavior for extended MKP instances with negative weights, profits and capacities.

Introduction

The core concept for the 0/1 Multidimensional Knapsack Problem (MKP) [START_REF] Puchinger | The core concept for the multidimensional knapsack problem[END_REF][START_REF] Puchinger | The multidimensional knapsack problem: Structure and algorithms[END_REF] has been shown to be very effective in providing opportunities for heuristically solving the MKP, achieving higher quality solutions and shorter run-times than general IP methods. In this paper we will examine the possibilities of extending the core concept towards general 0/1 Integer Programming (IP).

The Multidimensional Knapsack Problem (MKP) is defined as:

maximize z = n j=1 p j x j (1) subject to n j=1 w ij x j ≤ c i , i = 1, . . . , m (2)
x j ∈ {0, 1}, j = 1, . . . , n.,

where the profits p j , the weights w ij , and the capacities c i are all positive. Allowing negative values for those parameters results in general 0/1 Integer Problems. This is because it is possible to transform any 0/1 IP into this format. [START_REF] Bertsimas | Introduction to Linear Optimization[END_REF] The aim of the core concept is to reduce the original problem to a core of items for which it is hard to decide whether or not they will occur in an optimal solution. All variables corresponding to items outside the core are fixed to their optimal values.

The core of a given MKP is defined with respect to some ordering of the variables in the problem. The ordering results in variables that are expected to be in the knapsack (set to one) occur before those which are not expected to be in the knapsack (set to zero). Given the optimal solution of the MKP the exact core is defined as the set of variables from the first variable that takes the value zero to the last variable that takes the value one. In order to devise an exact core for a given MKP, the optimal solution has to be known. However, being able to heuristically obtain good approximations to cores and solve those smaller problems, may lead to high quality solutions in short computational times.

The underlying concept of such a heuristic is to order the items of the MKP according to a specific efficiency measure. This ordering will allow to partition the items into three sections. The first section which contains items which are included in the knapsack (variables set to one). The second section, named the approximate core, containing the items which may or may not be included in the knapsack (variables set to either one or zero). Finally the third section contains the items which are not included in the knapsack (variables set to zero). The aim is to have the approximate core closely mimic the exact core.

The following example illustrates the core concept for a small 2-dimensional knapsack problem. The variables are ordered by an efficiency measure described later. The first line shows the optimal integer solution, while the second line shows the optimal solution to the LP-relaxation of the problem. The exact core is shown in bold in the first line, while an approximate core (adding 2 variables around the non 0-1 LP solution values) is shown in bold in the second line.

IP 1 1 0 0 1 0 1 0 0 0 LP 1 1 1 1 1 0.96 0.23 0 0 0 In the remainder of the paper, we first introduce the core concept in the context of its previous uses. We then extend the efficiency measure used for MKPs to general 0/1 Integer Programs, and prove that the efficiency measure is tightly related to the optimal solution. In Section 4 we show the result of experiments illustrating the effectiveness of the approximate core computations, the loss of precision that arises from restricting the problem to an approximate core, and the improvement in best solutions found if we use approximate cores.

Background

The Multidimensional Knapsack Problem

A comprehensive overview of practical and theoretical results for the MKP can be found in the monograph on knapsack problems by [START_REF] Kellerer | Knapsack Problems[END_REF]). Solving the MKP with heuristic methods seems to be the method of choice for the bigger instances described in the literature, since no exact method is known for solving these instances to optimality. Besides exact techniques for solving small to moderately sized instances, based on dynamic programming [START_REF] Gilmore | The theory and computation of knapsack functions[END_REF][START_REF] Weingartner | Methods for the solution of the multidimensional 0/1 knapsack problem[END_REF] and branch-and-bound [START_REF] Shih | A branch and bound method for the multiconstraint zero-one knapsack problem[END_REF][START_REF] Gavish | Efficient algorithms for solving the multiconstraint zero-one knapsack problem to optimality[END_REF], many kinds of meta-heuristics have been applied to the MKP [START_REF] Glover | Critical event tabu search for multidimensional knapsack problems[END_REF][START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF]. See [START_REF] Raidl | Empirical analysis of locality, heritability and heuristic bias in evolutionary algorithms: A case study for the multidimensional knapsack problem[END_REF] for a recent survey and comparison of evolutionary algorithms for the MKP. The hybrid tabusearch methods presented in [START_REF] Vasquez | A hybrid approach for the 0-1 multidimensional knapsack problem[END_REF][START_REF] Vasquez | Improved results on the 0-1 multidimensional knapsack problem[END_REF] are currently yielding the best known results for the commonly used benchmark instances.

The core concept for KP and MKP

The core concept was first presented for the classical 0/1-Knapsack Problem (KP) [START_REF] Balas | An algorithm for large zero-one knapsack problems[END_REF] and led to very successful knapsack algorithms [START_REF] Martello | A new algorithm for the 0-1 knapsack problem[END_REF][START_REF] Pisinger | An expanding-core algorithm for the exact 0-1 knapsack problem[END_REF][START_REF] Pisinger | A minimal algorithm for the 0-1 knapsack problem[END_REF]. These ideas were also studied in the context of bi-criteria knapsack problems in (Gomes da [START_REF] Gomes Da Silva | Core problems in bi-criteria 0,1knapsack: new developments[END_REF]. The core concept was successfully extended to the MKP [START_REF] Puchinger | The core concept for the multidimensional knapsack problem[END_REF][START_REF] Puchinger | The multidimensional knapsack problem: Structure and algorithms[END_REF], leading to highly competitive heuristic algorithms.

It should be noted here that the KP core concept is not effective for producing good heuristic solutions for strongly correlated problem instances. Pisinger [START_REF] Pisinger | An expanding-core algorithm for the exact 0-1 knapsack problem[END_REF] discusses why these problems are difficult to solve using the core concept. We would expect similar results for strongly correlated general 0/1 IP problems.

The classical greedy heuristic for KP packs the items into the knapsack in decreasing order of their efficiencies pj wj as long as the knapsack constraint is not violated. The same ordering also defines the solution structure of the LP-relaxation, which consists of three parts: The first part contains all variables set to one, the second part consists of at most one split item (s), whose corresponding LP-value is fractional, and finally the remaining variables, which are always set to zero, form the third part.

The precise definition of the core of KP introduced by [START_REF] Balas | An algorithm for large zero-one knapsack problems[END_REF] requires the knowledge of an optimal integer solution x * . Assume that the items are sorted according to decreasing efficiencies and let

a := min{j | x * j = 0}, b := max{j | x * j = 1}.
(4) The core is given by the items in the interval C = {a, . . . , b}. It is obvious that the split item is always part of the core. If the split item would not be part of the core, the core would either start after the split item or end before it. The first case is impossible, since this would break the capacity constraint. The second case would contradict the optimality of the solution, because we would still be able to add more items to the knapsack without violating the capacity constraint.

These ideas have been expanded to MKP without major difficulties [START_REF] Puchinger | The core concept for the multidimensional knapsack problem[END_REF][START_REF] Puchinger | The multidimensional knapsack problem: Structure and algorithms[END_REF]. The main difference is that the choice of the efficiency measure is not obvious for the MKP any more. The efficiency measure:

e j = p j s j ,
where s j = m i=1 u i w ij , and u i are the dual variable values of the LP-relaxation of the MKP, provided the best theoretical and practical results.

Let x * be an optimal solution and assume that the items are sorted according to the decreasing efficiency measure e, then define a := min{j | x * j = 0} and b := max{j | x * j = 1}.

(5) The core is given by the items in the interval C := {a, . . . , b}, and the core problem (MKPC) is defined as

maximize z = j∈C p j x j + p (6) subject to j∈C w ij x j ≤ c i -wi , i = 1, . . . , m (7) x j ∈ {0, 1}, j ∈ C, (8)
with p = a-1 j=1 p j and wi =

a-1 j=1 w ij , i = 1, . . . , m.
In contrast to KP, the solution of the LPrelaxation of MKP does not consist of a single fractional split item, but its up to m fractional values give rise to a whole split interval S := {s, . . . , t}, where s and t are the first and the last index of variables with fractional values after sorting by efficiency e.

The split interval S e has been precisely characterized. Let x LP be the optimal solution of the LP-relaxation of MKP.

Theorem 1 ( [START_REF] Puchinger | The core concept for the multidimensional knapsack problem[END_REF][START_REF] Puchinger | The multidimensional knapsack problem: Structure and algorithms[END_REF]) For efficiency values e j we have:

x LP j =    1 if e j > 1 , ∈ [0, 1] if e j = 1 , 0 if e j < 1 . (9)
3 Extending the core concept

As mentioned above, the main goal of this paper is to extend the core concept to general 0/1 Integer Programs. We show how the efficiency measure for the classical MKP problem can be adapted in such a way that the ordering of the variables according to this measure remains valuable for devising good approximate cores. We further provide a characterization of the structure of the LP relaxation of the 0/1 Integer Program.

We take all 0/1 IP problems to be transformable into the same structure as MKP, see equation 1.

Such a transformation is possible for any 0/1 IP, see any linear programming text book, (e.g. [START_REF] Bertsimas | Introduction to Linear Optimization[END_REF]). This means that the only difference between MKP and this formulation of 0/1 IP problems is that the coefficients are permitted to take either positive or negative values.

We extend the previously defined efficiency measure e j to create a tuple based measure. We introduce ordering variables, o j which take values representing a section of the ordering. Variables x j are sorted in decreasing (lexicographic) order of efficiency (o j , e j ), in other words they are first sorted by section variable, o j , and then efficiency value e j .

These extensions are implemented as indicated in equation 10:

(o j , e j ) =                              (7, pj sj ) if p j > 0 ∧ s j < 0 (6, p j ) if p j > 0 ∧ s j = 0 (5, 1 sj ) if p j = 0 ∧ s j < 0 (4, pj sj ) if p j > 0 ∧ s j > 0 (4, sj pj ) if p j < 0 ∧ s j < 0 (4, 1) if p j = 0 ∧ s j = 0 (3, 1 sj ) if p j = 0 ∧ s j > 0 (2, p j ) if p j < 0 ∧ s j = 0 (1, pj sj ) if p j < 0 ∧ s j > 0 (10)
The ordering is designed to minimize the size of the split interval, which is completely contained in section o j = 4. Our experiments in Section 4 show that the center of the core and the center of the split interval are close for our benchmark instances.

The sections o j ∈ {7, 6, 5} contain items that are purely beneficial: they either increase profit or "on average" remove weight from the optimal solution without decreasing profit. They are ordered to maximize profit and removal of weight. Similarly the sections o j ∈ {1, 2, 3} contain items that are purely detrimental to the problem: they either decrease profit or add weight. Again they are ordered to maximize profit and removal of weight.

Using this efficiency measure the nature of the split interval can be characterized as follows. Let x LP be the optimal solution of the LP-relaxation of general 0/1 IP.

Theorem 2

x LP j = 1 if e j > 1 or o j > 4, ∈ [0, 1] if e j = 1 and o j = 4, 0 if 0 ≤ e j < 1 or o j < 4. ( 11
)
Proof The dual LP (DLP) associated with the LP-relaxation of the general 0/1 IP formulation is given by: minimise

m i=1 c i u i + n j=1 v j (12) subject to m i=1 w ij u i + v j ≥ p j , j = 1, ..., n (13) u i , v j ≥ 0, i = 1, ..., m, j = 1, ..., n, (14)
where u i are the dual variables corresponding to the problem's constraints and each v j corresponds to the inequality x j ≤ 1. For the optimal primal and dual solutions the following complementary slackness conditions hold for j = 1, ..., n. .

x j m i=1 w ij u i + v j -p j = 0 (15) v j (x j -1) = 0 (16)
(For more details on linear programming duality and complementary slackness conditions, refer to any textbook on linear programming, e.g. [START_REF] Bertsimas | Introduction to Linear Optimization[END_REF].)

We illustrate the result for each section in the definitions of the ordered tuple (o j , e j ).

Consider the top 3 sections (o j ∈ {7, 6, 5}). Clearly in each case we have that p j > s j . Hence satisfying equation ( 13) requires that v j > 0. Therefore equation ( 16) implies that x j = 1.

Consider the bottom 3 sections (o j ∈ {1, 2, 3}). Clearly in each case p j < s j . Hence the expression m i=1 w ij u i + v j -p j or equivalently s j + v j -p j is greater than 0, since v j ≥ 0. In order to satisfy equation 15 x j = 0.

For section (4, pj sj ) we consider two cases. If e j = pj sj > 1 then p j > s j since s j > 0 and the same reasoning as for cases o j ∈ {7, 6, 5} applies, while if e j < 1 then p j < s j and the same reasoning as cases o j ∈ {1, 2, 3} applies.

For section (4, sj pj ) we consider two cases. If e j = sj pj > 1 then p j > s j since p j < 0 and the same reasoning as for cases o j ∈ {7, 6, 5} applies, while if e j < 1 then p j < s j and the same reasoning as cases o j ∈ {1, 2, 3} applies.

For the remaining case, e j = 1 and o j = 4, there is nothing to prove.

The ordering within the top and bottom groups o j ∈ {1, 2, 3}, and o j ∈ {5, 6, 7} is not set by the proof, these orderings are based upon maximizing profit. Other possible orderings could be considered for these groups without changing our characterization of the split interval.

An illustration of the ordering (o j , e j ) is given in Table 1. This example shows some of the sections described above. As predicted by the theorem, the split interval exists entirely within section o j = 4.

Computational experiments

Benchmark Problems

All of the following computational experiments were performed on a 3GHz Intel Pentium D with 4 Gb RAM, using the programming language Mercury and the commercial mixed integer programming solver CPLEX 10.0.

In order to study the core concept on 0/1 IP we generated example problems using the Chu and Beasley [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF] benchmark instances for the MKP, as the starting point.

These benchmark problems consist of classes of randomly created instances for each combination of n ∈ {100, 250, 500} items, m ∈ {5, 10, 30} constraints and tightness ratios 0.25, 0.50.75. The tightness ratio refers to the ratio between the constraint value and the sum of the corresponding weights.

α = c i n j=1 w ij ∈ {0.25, 0.5, 0.75} (17)
Weights are integers between 0 and 1000. Profits are generated by the equation:

p j = m i=1 w ij m + [500r i ] ∈ {0.25, 0.5, 0.75}
where r i is a random number generated from (0, 1].

For each permutation of n, m and α, 10 instances are provided.

In order to generate 0/1 Integer Programs with negative values we multiply a random percentage of the weights and profits of a given problem by -1. The percentages used are 5%, 10%, 20%. Larger percentages of negative values were tried, however the problems quickly became optimally solvable in short run-times.

The set of profits and the set of all weights are operated on separately. This ensures that there is a fixed percentage of negative profits and a fixed percentage of negative weights. Combinations of different percentages of negative weights and profits were tried, however almost invariably this made the problems easier and thus faster to solve. This process will change the tightness ratio. In order to maintain the tightness ratio the capacities have to be adjusted:

ĉi = c i * n j=1 ŵi,j n j=1 w i,j
, w i,j represents the original weights, ŵi,j represents the adjusted weights, and ĉi represents the new constraint value. Since the sum of the adjusted weights may become negative, it is possible that the new capacity ĉi will also be negative.

It can be seen that the generated problems are general 0/1 IP problems. There are nine classes of generated problems for each combination of n and m, corresponding to three different tightness ratios, and the three percentages of negative coefficients.

0/1 IP Core Analysis

We provide empirical results supporting our adaptation of the efficiency measure e, (see Table 2). This table shows information about actual cores when the above efficiency function is utilized. The problems shown in these tables are based upon the smaller instances in Chu and Beasley's benchmark library [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF]. Specifically these problems use n = 100, m ∈ {5, 10}, and n = 250, m = 5. These problems were chosen because they are solvable in reasonable runtime. This means that the optimal solutions can be found, and the size of the core can be determined.

The tables show the averaged values over 10 problem instances. Average values listed include size of the split interval (|S e |), size of the exact core (|C e |), percentage that the split interval covers the exact core (ScC), percentage that the exact core covers the split interval (ScC), and the distance between the center of the split interval and the center of the exact core (|C dist |) as a percentage of the number of items in the problem.

The table entries for 0% negative coefficients shows that the newly defined efficiency value provides equivalent results for standard MKP problems as those reported in [START_REF] Puchinger | The core concept for the multidimensional knapsack problem[END_REF][START_REF] Puchinger | The multidimensional knapsack problem: Structure and algorithms[END_REF]. As expected from Theorem 2, negative values do not increase the size of the split interval. The size of the split interval and the core actually decreases as the number of negative weights increases. The center of the core remains close to the center of the split interval. These results show that the chosen ordering, based on the optimal dual variable values of the LP-relaxation, is a good indicator of the actual location of the core.

Approximate core algorithm

In order to evaluate the influence of negative values on solution quality and run-times an approximate core algorithm was implemented. This algorithm is similar to the algorithm implemented by [START_REF] Puchinger | The core concept for the multidimensional knapsack problem[END_REF][START_REF] Puchinger | The multidimensional knapsack problem: Structure and algorithms[END_REF] δ were chosen to approximately reflect the size of the actual cores detected in the previous section: δ ∈ 0.1n, 0.15n, 0.2n, 0.1n + 2m, 0.2n + 2m. The problems shown in these tables are based upon the smaller instances in Chu and Beasley's benchmark library [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF]. They are the same set of problems used to investigate the actual core sizes in the previous section.

The results of this experiment are shown in Table 3. It shows the average values over 10 problems with the same tightness ratio. Values shown for the original problem include the average optimal IP solution for the problem (z), then the average amount of CPU-time taken to produce the optimal IP solution in seconds (t[s]). Values shown for each core include the average percentage difference between the optimal IP solution(z * ) and the IP solution produced by the core problem(z), (% opt = 100 * (z * -z)/z * ), the number of times the optimal solution was reached (#), and the average CPU-time taken to solve the core IP, as a percentage of the CPU-time taken to solve the original IP problem, %t = 100 * (t core /t original ).

The solution to the approximate cores are (on average over 10 problem instances) always within 0.7 % of the optimal solution. The results shown in Table 3 show that smaller approximate core sizes produce a significant increase in speed. However they are less likely to produce the optimal solution, and on average produce solutions of lesser quality than the larger cores. As the percentage of negative values increases the problems become faster to solve. Larger negative percentages were examined, however run-times were too small to see any benefit from the core concept.

Larger 0/1 IP with Fixed Time Runs

We now investigate fixed-time runs over larger problem instances. These tests are performed over instances which are currently very hard or not at all solvable to optimality. The instances used are based on the hardest benchmarks provided by [START_REF] Chu | A genetic algorithm for the multidimensional knapsack problem[END_REF], n = 500, m ∈ 5, 10, 30 Again these problems were adjusted to contain negative values in a manner similar to the problems above. All of the results shown here are performed over problems with 10% negative weights, and 10% negative profits. The constraints are also adjusted accordingly.

Table 4 shows the best feasible solution for the original problem and the core problems as a percentage of the LP solution, ( % LP = 100 * (LP -IP )/LP ). These values are averaged over 10 instances of similar problems. Standard deviations are provided as subscripts. The smallest values for each row are highlighted in bold. This table also shows the number of times a particular core size has lead to the best solution for a problem, (#). The final column for each core size is the average number of nodes explored in the branch and cut tree used by CPLEX.

The experiments show that for the considered time limits the results obtained on the core problems are, on average, better that the results ob-tained from the original problem. There is also a inverse relationship between the size of the core and the number of nodes explored. As the size of the core decreases the number of nodes explored increases. The best average results for a time limit of 500 seconds is δ = 0.2. It can be seen that smaller time limits provide best results with smaller approximate core sizes.

Related Work

The most closely related work to this paper is the application of the core concept to the MKP [START_REF] Puchinger | The core concept for the multidimensional knapsack problem[END_REF][START_REF] Puchinger | The multidimensional knapsack problem: Structure and algorithms[END_REF]. We extend the results therein to general 0/1 Integer Programs, and show that the core concept continues to be valuable in the more general case.

Recently, very interesting results have been achieved with heuristics for 0/1 Mixed Integer Programming Problems with the goal of devising better feasible solutions earlier in the optimization process. Local Branching [START_REF] Fischetti | Local Branching[END_REF] combines local search and general branchand-bound by introducing local branching constraints forcing the search to explore the neighborhoods of current feasible solutions first.

In Relaxation Induced Neighborhood Search (RINS) [START_REF] Danna | Exploring relaxation induced neighborhoods to improve MIP solutions[END_REF] subproblems for finding better feasible solutions are solved at some nodes of the branch-and-bound tree. The subproblems are obtained by fixing the variables having identical values in the current best feasible solution and in the current solution of the LP-relaxation, leaving the remaining variables free.

RINS and local branching are local-search based ideas, reducing the subproblems to certain neighborhoods around a currently feasible solution. Our approach requires an LP solution only, and does not make use of feasible solutions at all.

Conclusions

We have extended the core concept, previously successfully used for finding better solutions to Multiple Knapsack Problems to general 0/1 Integer Programs. We provided an ordering of the variables using dual information, which results in a compact split interval just as for the standard MKP. This ordering is used to reduce the size of the tackled instances and obtain near-optimal solutions in shorter run-times. Our computational experiments show, that for challenging 0/1 Integer Programs with a large number of variables compared to the number of constraints, the core concept provides better solutions than directly solving the original problem using a commercial solver. In the future we plan to test our approach on other widely used large 0/1 IP benchmarks.

Table 3 :

 3 Solving different sized cores for various percentages of negative values to optimality. (All values shown are averaged over 10 problem instances) Fixed time runs of larger benchmark instances. Various core sizes are shown for 10% negative coefficients. All values shown are averaged over 10 problem instances.

Table 1 :

 1 . The approximate core is generated by adding δ items to either side of the center of the split interval. The values of W eight 1 W eight 2 Profit Example 2-dimensional 0/1 IP problem. The 3 sections are separated based upon the IP solution. This example shows an exact core using the efficiency measure defined in Theorem 2.

								s j	(o j , e j )	LP IP
				-1	-1	1	-0.89 (7,0.89) 1.00 1
				-9	12	7	-5.17 (7,0.74) 1.00 1
				0	0		8	0.00 (6,8.00) 1.00 1
				-2	13	12	0.24	(4,50)	1.00 1
				5	0		19	3.77 (4,5.04) 1.00 1
				-5	-4	-3	-4.31 (4,1.44) 1.00 1
				16	21	18	14.88 (4,1.21) 1.00 1
				13	15	14	11.81 (4,1.19) 1.00 0
				-6	-10	-5	-5.87 (4,1.17) 1.00 1
				20	-8	14	14.00 (4,1.00) 0.71 1
				-6	-11	-6	-6.00 (4,1.00) 0.85 0
				20	16	15	17.22 (4,0.87) 0.00 0
				10	8		6	8.61 (4,0.70) 0.00 0
				-1	-14	-4	-2.63 (4,0.66) 0.00 0
				14	9		5	11.76 (4,0.43) 0.00 0
				16	-3	3	11.66 (4,0.26) 0.00 0
				-7	23	-9	-2.19 (4,0.24) 0.00 0
				-1	10	0	0.59 (3,1.69) 0.00 0
				7	0		-5	5.28 (1,0.95) 0.00 0
				24	10	-9	19.43 (1,0.46) 0.00 0
					e -0% negative weights		e -5% negative weights
					0% negative profits			5% negative profits
	n	m	α	|S e |	|C e |	ScC	CcS	C dist |S e | |C e |	ScC	CcS	C dist
	100 5 0.25 5.00 20.20 28.12 100.00 3.30 5.00 20.00 31.58 100.00 2.90
		0.5	5.00 22.10 27.49 100.00 3.45 5.00 15.90 28.33 86.00	2.65
		0.75 5.00 20.00 26.32 100.00 3.40 5.00 14.80 35.91 98.00	3.50
	250 5 0.25 2.00 12.68 18.16 100.00 2.46 2.00 13.36 17.35 100.00 3.12
		0.5	2.00 12.20 18.45 100.00 1.38 2.00 9.60 21.47 100.00 1.20
		0.75 2.00 10.40 20.18 100.00 1.56 2.00 10.96 21.04 100.00 1.92
	100 10 0.25 10.00 23.20 46.57 100.00 2.90 9.90 25.80 42.74 96.67	3.45
		0.5	9.80 25.80 48.17 96.00	3.10 9.70 23.70 44.06 100.00 3.00
		0.75 9.70 18.30 54.36 94.00	3.00 9.20 16.90 60.09 93.19	2.45
		Average		5.61 18.32 31.98 98.89	2.73 5.53 16.75 33.62 97.10	2.69
					e -10% negative weights	e -20% negative weights
					10% negative profits			20% negative profits
	n	m	α	|S e |	|C e |	ScC	CcS	C dist |S e | |C e |	ScC	CcS	C dist
	100 5 0.25 5.00 23.60 22.31 100.00 4.30 5.00 18.60 29.55 100.00 2.70
		0.5	5.00 19.40 27.11 100.00 3.00 4.60 9.80 57.68 95.50	1.20
		0.75 4.80 12.40 47.28 98.00	1.60 2.50 16.90 30.34 86.67	7.00
	250 5 0.25 2.00 10.36 20.27 100.00 1.22 2.00 10.52 20.22 98.00	2.02
		0.5	2.00 11.72 18.79 100.00 2.22 2.00 8.84 24.31 100.00 1.94
		0.75 2.00	7.28 30.13 98.00	1.24 1.56 6.08 40.80 100.00 1.74
	100 10 0.25 9.70 24.20 42.19 97.89	4.05 9.70 28.00 37.91 100.00 4.15
		0.5	9.50 20.10 49.20 97.00	3.20 8.40 20.10 47.86 98.89	3.35
		0.75 8.80 14.30 65.99 92.70	2.05 4.30 13.80 35.51 92.50	4.05
		Average		5.42 15.92 35.92 98.18	2.54 4.45 14.74 36.02 96.84	3.13

Table 2 :

 2 Split intervals, core sizes, mutual coverage of the split interval and cores, distances of the centers for various percentages of negative values. (Values are averaged over 10 instances of each problem.)

Acknowledgements

National ICT Australia is funded by the Australian Government's Backing Australia's Ability initiative, in part through the Australian Research Council.


Michel Lagarde

Catherine Calzada

Michel Guichardant

Evelyne Véricel

In vitro and in vivo bimodal effects of docosahexaenoic acid supplements on redox status and platelet function

Docosahexaenoic acid (DHA) is a prominent nutrient of marine lipids. Together with eicosapentaenoic acid, it is recognized as a protective molecule against atherosclerosis and thrombosis through the regulation of blood cell functions, especially platelets. Its high unsaturation index may however make it prone to peroxidation, which is usually considered as deleterious. This short review takes into consideration this possibility related to DHA concentrations both in vitro and in vivo. It is suggested that protective effects of DHA on platelet activation depend on the reduction of oxidative stress, and appear bimodal with the abolishment of such a protection when DHA is used at relatively high concentrations.

Introduction

Docosahexaenoic acid (DHA) is one of the long-chain polyunsaturated fatty acids (PUFA) of the omega-3 family found in marine lipids. Together with eicosapentaenoic acid (EPA), DHA is wellknown for its anti-atherothrombotic potential, in particular by decreasing the arachidonic acid (ArA) content of blood cells [START_REF] Spector | Essentiality of fatty acids[END_REF], inhibiting thromboxane production in platelets, as well as leukotriene B4 formation in leukocytes [START_REF] Kinsella | Dietary n-3 polyunsaturated fatty acids and amelioration of cardiovascular disease: possible mechanisms[END_REF]. In addition to these inhibitory effects on ArA metabolism, DHA may decrease athero-thrombogenesis through the action of its lipoxygenase (LOX) end-products. Mono-hydroxylated derivatives produced through 12-, and 15-LOX, namely 11-, 14-, and 17-OH-22:6 (11-, 14-, and 17-HDoHE), respectively, inhibit the thromboxane-induced platelet aggregation (induced by the stable thromboxane A2 receptor agonist U-46619), even stronger than 12-OH-20:4 and -20:5 (12-HETE and -HEPE) [START_REF] Croset | Inhibition by lipoxygenase products of TXA2-like responses of platelets and vascular smooth muscle. 14-Hydroxy from 22:6n-3 is more potent than 12-HETE[END_REF]. More recently, the double lipoxygenase product of DHA, 10(S),17(S)-diHDoHE, named protectin DX, has been shown to inhibit platelet aggregation through the inhibition of cyclooxygenase-1, which initiates prostanoid synthesis including the potent pro-aggregatory thromboxane A2, as well as the response to the thromboxane A2 mimetic U-46619 [START_REF] Chen | Poxytrins, a class of oxygenated products from polyunsaturated fatty acids, potently inhibit blood platelet aggregation[END_REF]. In addition, DHA is known to be oxygenated into several di/tri-OH derivatives (protectin D1, maresins, and resolvins) that are potent inhibitors of the inflammation process [START_REF] Serhan | Pro-resolving lipid mediators are leads for resolution physiology[END_REF]. Supplementation of humans with long-chain omega-3 PUFA is usually considered as a positive approach to decrease the risk of atherosclerosis and thrombosis [START_REF] Nestel | Fish oil and cardiovascular disease: lipids and arterial function[END_REF], as recently reviewed [START_REF] Kromhout | Update on cardiometabolic health effects of ω-3 fatty acids[END_REF], although some controversies arose in the recent years [START_REF] Rizos | Association between omega-3 fatty acid supplementation and risk of major cardiovascular disease events: a systematic review and metaanalysis[END_REF]. Among the controversial issues are the intake doses of those highly unsaturated PUFA, which may be prone to peroxidation [START_REF] North | Detection of lipid radicals by electron paramagnetic resonance spin trapping using intact cells enriched with polyunsaturated fatty acid[END_REF]. We have been especially interested in the effects of different concentrations of DHA upon blood platelets and their blood environment both in vitro and in vivo, in particular regarding the redox status.

In vitro effects of DHA on platelet reactivity and redox status

When compared with EPA, DHA pre-incorporated in human platelet phospholipids was more potent to inhibit platelet aggregation induced by various agonists. While EPA was substantially released, and oxygenated like endogenous ArA in response to thrombin, DHA was preferentially transferred from phosphatidylcholine to phosphatidylethanolamine [START_REF] Croset | In vitro incorporation and metabolism of icosapentaenoic and docosahexaenoic acids in human platelets--effect on aggregation[END_REF], especially their plasmalogen subclass [START_REF] Croset | Incorporation and turnover of eicosapentaenoic and docosahexaenoic acids in human blood platelets in vitro[END_REF]. One possible mechanism for the high potential of DHA to inhibit thrombin-induced platelet aggregation is the strongest inhibition of endogenous ArA oxygenation by cyclooxygenase, while the lipoxygenase activity was not altered [START_REF] Croset | Different metabolic behavior of long-chain n-3 polyunsaturated fatty acids in human platelets[END_REF]. The cyclooxygenase inhibition by DHA was however alleviated by doubling the concentration of DHA added to platelets, without altering the inhibition of platelet aggregation, presumably because prostaglandin D2 formation, a potent inhibitor of platelet aggregation, was increased [START_REF] Gaudette | Albumin-bound docosahexaenoic acid and collagen-induced human platelet reactivity[END_REF]. We might speculate that such a paradoxical effect might be explained by the oxidative stress induced by high concentrations of DHA, which could have increased the cyclooxygenase activity (see later results below). In addition to the inhibition of platelet cyclooxygenase by DHA enrichment, the response of DHA-rich platelets to the thromboxane A2 mimetic U-46619 was strongly inhibited through the decreased affinity of this agonist to its membrane receptor sites [START_REF] Swann | Enrichment of platelet phospholipids with eicosapentaenoic acid and docosahexaenoic acid inhibits thromboxane A2/prostaglandin H2 receptor binding and function[END_REF]. Another platelet function, the pro-coagulant activity of platelet phosphatidylserine exposure in response to collagen, can be altered by DHA (or EPA) enrichment in vitro. Again, the inhibitory effect of those PUFA, only significant at 0.75 mM, was not increased by doubling their concentration [START_REF] Larson | Exogenous modification of platelet membranes with the omega-3 fatty acids EPA and DHA reduces platelet procoagulant activity and thrombus formation[END_REF]. Considering the high unsaturation of long-chain omega-3 PUFA, especially DHA, it is likely that lipid peroxidation will be favored when their concentrations are increased in biological systems. Indeed, PUFA, and in particular DHA, increase free radical formation in oxidative stress conditions [START_REF] North | Detection of lipid radicals by electron paramagnetic resonance spin trapping using intact cells enriched with polyunsaturated fatty acid[END_REF]. We have been interested in the dose-related effect of DHA on human platelet redox status after in vitro enrichment. A dose-dependent increased DHA concentration in membrane phospholipids (phosphatidylcholine and phosphatidylethanolamine) after incubation with albumin-bound DHA (DHA/albumin ratios of 0.01, 0.1, and 1, corresponding to 0.5, 5, and 50 µM) was observed but, at the lowest concentration, this was only significant in the plasmalogen ethanolamine subclass. This observation has been discussed regarding the potential antioxidant activity of the plasmalogen subclass [START_REF] Véricel | Pro-and antioxidant activities of docosahexaenoic acid on human blood platelets[END_REF]. Malondialdehyde (MDA) and the 12-lipoxygenase end-product 12-HETE, measured as markers of oxidative stress, were significantly increased after the highest enrichment, but significantly decreased at the lowest one. These results suggest a bimodal effect according to DHA concentrations, with an interesting protection against lipid peroxidation at low concentrations [START_REF] Véricel | Pro-and antioxidant activities of docosahexaenoic acid on human blood platelets[END_REF]. The increased peroxidation observed after the highest enrichment was in agreement with significant decreased platelet alpha-and gamma-tocopherols.

In vivo effects of DHA on platelet function and their blood environment

As a component of long-chain omega-3 PUFA, DHA intake has long been reported a protective agent against atherosclerosis and thrombosis as recently reviewed [START_REF] Nestel | Fish oil and cardiovascular disease: lipids and arterial function[END_REF][START_REF] Kromhout | Update on cardiometabolic health effects of ω-3 fatty acids[END_REF][START_REF] Gissi | Gruppo Italiano per lo Studio della Sopravvivenza nell'Infarto miocardico)-Prevenzione-Investigators, Dietary supplementation with n-3 polyunsaturated fatty acids and vitamin E after myocardial infarction: results of the GISSI Prevenzione trial[END_REF][START_REF] Kris-Etherton | Fish consumption, fish oil, omega-3 fatty acids, and cardiovascular disease[END_REF], acting through several ways. One of them is the inhibition of blood platelet activation via mechanisms already mentioned above such as competition with ArA metabolism, especially thromboxane formation. However, metaanalyses revealed heterogeneities in results that might be due to different intake doses [START_REF] Rizos | Association between omega-3 fatty acid supplementation and risk of major cardiovascular disease events: a systematic review and metaanalysis[END_REF], and high daily supplementation may decrease antioxidant defenses such as alpha-tocopherol in plasma [START_REF] Sanders | The influence of a fish oil high in docosahexaenoic acid on plasma lipoprotein and vitamin E concentrations and haemostatic function in healthy male volunteers[END_REF]. Considering the deleterious effect of oxidative stress in platelet [START_REF] Aviram | LDL-platelet interaction under oxidative stress induces macrophage foam cell formation[END_REF][START_REF] Jain | Relationship of blood thromboxane-B2 (TxB2) with lipid peroxides and effect of vitamin E and placebo supplementation on TxB2 and lipid peroxide levels in type 1 diabetic patients[END_REF][START_REF] Ferroni | Oxidant stress and platelet activation in hypercholesterolemia[END_REF][START_REF] Véricel | Diabetic patients without vascular complications display enhanced basal platelet activation and decreased antioxidant status[END_REF] and blood mononuclear cell functions [START_REF] Meskini | Glutathione peroxidase activity and metabolism of arachidonic acid in peripheral blood mononuclear cells from elderly subjects[END_REF], we have investigated the relationship between the doses of DHA intake and the reactivity of those cells. In a study with healthy human volunteers, increasing doses (200, 400, 800, and 1600 mg/day) of DHA in triacylglycerols from micro-algae were consumed for two-weeks each dose. There was a dosedependent increase of DHA in plasma phospholipids, as well as in platelet phosphatidylcholine and phosphatidylethanolamine. Whether, the increase in phosphatidylethanolamine reflected a preferential incorporation within their plasmalogen subclass, as found in vitro (see above), was not investigated. In terms of platelet reactivity, the dose-response was bimodal with a maximal inhibition of platelet aggregation and cyclo-oxygenation of exogenous ArA after 800 mg/day DHA. After 1600 mg/day DHA, the aggregation was less inhibited and cyclo-oxgenase activity was not significantly altered [START_REF] Guillot | Increasing intakes of the longchain omega-3 docosahexaenoic acid: effects on platelet functions and redox status in healthy men[END_REF]. In addition, platelet vitamin E (alpha-tocopherol) significantly increased after 200 mg/day DHA. In agreement with this increased antioxidant status in platelets, urinary isoprostanes (8-epi-PGF2), as a marker of the global redox status, were significantly decreased after this low dose intake of DHA, whereas they were significantly increased after 1600 mg/day DHA [START_REF] Guillot | Increasing intakes of the longchain omega-3 docosahexaenoic acid: effects on platelet functions and redox status in healthy men[END_REF]. This clearly suggests that low dosages of DHA are protective against platelet-related atherothrombotic risk in relation with an antioxidant effect at low dosage of DHA, whereas the highest dose tested (1600 mg/day DHA) was less potent against platelet reactivity, possibly because of an increased oxidative stress.

Plasma low-density lipoproteins (LDL) were also studied in response to the different doses of DHA. LDL cholesterol esters and phospholipids were dose-dependently enriched in DHA according to the intake doses. However, a bimodal effect of this DHA enrichment could be observed, with a significant increase of LDL alpha-tocopherol content, and decrease of LDL MDA after 200, 400, and 800 mg DHA/day, but not after 1600 mg. Interestingly, the lag phase in the copper-induced oxidation of LDL was similarly increased after those three doses but not after the highest dose, meaning that the intermediary doses of DHA may protect against LDL oxidation. Although not significantly different from the other doses, the most active dose in such a protection, and MDA decrease was observed after 400 mg/day DHA [START_REF] Calzada | Subgram daily supplementation with docosahexaenoic acid protects low-density lipoproteins from oxidation in healthy men[END_REF]. In parallel, the apoptosis of blood mononuclear cells induced by oxidized LDL was tested. While there was a dose-dependent correlation in the IL-2 transcript expression with DHA intake, monocyte apoptosis was significantly attenuated after 400 mg/day DHA, and such a protective effect was maintained at higher doses, although to a lesser extent [START_REF] Mebarek | Effects of increasing docosahexaenoic acid intake in human healthy volunteers on lymphocyte activation and monocyte apoptosis[END_REF]. Altogether, these results obtained in healthy volunteers strongly suggest that daily doses of DHA lower than one gram should be recommended to decrease the athero-thrombotic risk related to blood cell reactivity, especially platelets. Several markers even suggest that the most active daily doses of DHA might be lower than 500 mg. In agreement with these dose-effect investigations in healthy volunteers, it has previously been shown that low daily doses of DHA + EPA (150 + 30 mg) exhibit the same protective effects in elderly people, through a reduction of oxidative stress [START_REF] Véricel | The influence of low intake of n-3 fatty acids on platelets in elderly people[END_REF]. The effects of different intake doses of DHA in healthy human volunteers has been recently reviewed [START_REF] Lagarde | Dose-effect and metabolism docosahexaenoic acid: Pathophysiological relevance in blood platelets[END_REF]. Interestingly, and more recently, the intake of 400 mg/day DHA in type-2 diabetic patients has shown similar protection, with even more potency than in healthy volunteers. Indeed, platelet aggregation was decreased by 50%, several markers of oxidative stress were significantly decreased, and vitamin E was significantly increased in both blood plasma and platelets [START_REF] Véricel | Moderate oral supplementation with docosahexaenoic acid improves platelet function and oxidative stress in type 2 diabetic patients[END_REF]. This suggests that the higher the oxidative stress, the higher the efficiency of DHA moderate intake to decrease such a stress. The mechanism underlying such a protection through a decreased oxidative stress is not clear. We might however speculate that DHA being easily oxidized, it might have a trapping effect of oxidant species at low doses, then saving vitamin E as observed in several studies, although participating in the oxidative stress at high concentrations. In favor of this hypothesis is the observation that a dosedependent formation of 4-hydroxy-hexenal, one specific peroxidation by-product from omega-3 PUFA, was observed after DHA intake, while 4-hydroxy-nonenal, the counter peroxidation by-product from omega-6 PUFA, did not change [START_REF] Calzada | Subgram daily supplementation with docosahexaenoic acid protects low-density lipoproteins from oxidation in healthy men[END_REF].

Conclusion

The long-chain omega-3 PUFA DHA and EPA, in particular DHA, are useful nutrients to protect against the athero-thrombotic risk associated with blood platelet reactivity. DHA effect at moderate concentrations, both in vitro and in vivo, might be related to reduction of oxidative stress (Figure 1). This would be especially useful in situations where the redox status is altered toward oxidation such as aging and diabetes. For clarity, this figure only relates with low and high doses of DHA (see text for details), and shows the variations in malondialdehyde (MDA), as a global marker of oxidative stress, and vitamin E, as the main antioxidant lipid soluble vitamin. In all DHA enrichment approaches, DHA was significantly increased in main platelet glycerophospholipids (PC and PE). This enrichment was higher after high doses compared to low doses.

Highlights

Figure 1 .

 1 Figure 1. Summary of results observed after DHA intake in humans and dose-related effects of DHA on human blood platelets.For clarity, this figure only relates with low and high doses of DHA (see text for details), and shows the variations in malondialdehyde (MDA), as a global marker of oxidative stress, and vitamin E, as the main antioxidant lipid soluble vitamin. In all DHA enrichment approaches, DHA was significantly increased in main platelet glycerophospholipids (PC and PE). This enrichment was higher after high doses compared to low doses.

  Docosahexaenoic acid exerts bimodal effects on blood platelet aggregation, oxidized-induced mononuclear cells apoptosis.Docosahexaenoic acid at low concentrations increase vitamin E whereas high concentrations tend induce oxidative stress.Low doses of docosahexaenoic acid down regulate platelet activation and oxidative stress in diabetic and elderly subjects. in vitro and ex vivo studies (elderly and healthy adults, diabetic patients)

Acknowledgements

The authors thank the current support of Inserm, Inra, and the Ministry of Education and Research, as well as that of a grant from the "Coeur & Artères" foundation.