Arezki Yanis Idres

Didier Tousch
email: didier.tousch@umontpellier.fr

Claudie Dhuyque-Mayer

Imane Hammad

Karen Lambert

Guillaume Cazals

Karine Portet

Karine Ferrare

Luc P R Bidel

Patrick Poucheret

An Original Asteraceae Based Infused Drink Prevents Metabolic Syndrome in Fructose-Rat Model

Keywords: metabolic syndrome, bitter Asteraceae, (Taraxacum officinaleW.) leaves, Arctium lappa L. roots, fructose-rat model, chlorogenic acid, chicoric acid

Metabolic syndrome (METS) is a complex disorder that predisposes an affected person to an increased risk of diabetes and cardiovascular disease. Bitter Asteraceae plants contain several compounds active against METS that can be used as an alternative preventive therapy. Our previous work showed that a natural chicory extract (NCRAE) containing chicoric acid (CRA) and chlorogenic acid (CGA) in a molar ratio of 70/30 exhibited an antioxidant, insulin sensitization and anti-hyperglycemic effect. The present study was designed to evaluate the preventive effects of an NCRAE-like extract against METS in a complementary natural pharmaco-therapeutic approach. An original Asteraceae infused drink containing the NCRAE CRA/CGA molecular ratio equivalent was prepared from dandelion (Taraxacum officinale L.) and burdock (Arctium lappa L.). The anti-METS effect of this drink was evaluated on the fructose-rat model for 8 weeks. Body weight, blood biochemistry, hepatic glucose-6phosphatase, arterial blood pressure glucose and insulin tolerance were evaluated after 8 weeks. Our results show that daily oral intake of the Asteraceae infused drink led to a reduction of body weight gain, hyperglycemia, hypertriglyceridemia, insulin resistance and hypertension. Moreover, rat-by-rat analysis of the insulinemia measures revealed two types of responders. One sub-group of subjects demonstrated normal insulinemia and the other subgroup demonstrated hyperinsulinemia. This hyperinsulinemia, associated with the inhibition of the glucose-6-phosphatase activity in the liver tissue, may suggest an insulin release caused by CGA. The present study suggests that this original infusion of dandelion leaves and burdock roots may be used as an adjuvant therapy to prevent metabolic syndrome.

Introduction

Metabolic syndrome (METS) is a cluster of biochemical abnormalities that increases the risk of type 2 diabetes and/or cardiovascular diseases [START_REF] Alberti | Harmonizing the Metabolic Syndrome: A Joint Interim Statement of the International Diabetes Federation Task Force on Epidemiology and Prevention; National Heart, Lung, and Blood Institute; American Heart Association; World Heart Federation; International Atherosclerosis Society; and International Association for the Study of Obesity[END_REF]. METS affects 20-30% of adult populations worldwide and reaches 50% of people over 60 years in the US [START_REF] Aguilar | Prevalence of the Metabolic Syndrome in the United States, 2003-2012[END_REF]. METS leads to insulin resistance via abdominal obesity, inflammation and oxidative stress. Abdominal obesity is caused by excessive energy storage in adipose tissue, leading to a multitude of metabolic disorders, including increased blood levels of free fatty acids, pro-inflammatory adipokines and reactive oxygen species (ROS). This last disorder disrupts the insulin signaling cascades and initiates a state of insulin resistance which may leads to type 2 diabetes [START_REF] Esser | Inflammation as a Link between Obesity, Metabolic Syndrome and Type 2 Diabetes[END_REF][START_REF] Johnson | The Inflammation Highway: Metabolism Accelerates Inflammatory Traffic in Obesity[END_REF][START_REF] Khodabandehloo | Molecular and Cellular Mechanisms Linking Inflammation to Insulin Resistance and _-Cell Dysfunction[END_REF].

The main management strategies for METS are based on lifestyle therapy including dietary changes and regular physical activity [START_REF] Giulio Marchesini | Lifestyle Modification in the Management of the Metabolic Syndrome: Achievements and Challenges[END_REF]. Often pharmacological therapy must be prescribed in order to act on one target: metformin treatment for its insulin sensitizing effect, Orlistat® as a gastric lipase inhibitor or beta-blockers and calcium channel blockers for hypertension [START_REF] Rask Larsen | The Pharmacological Management of Metabolic Syndrome[END_REF]. Actually, no chemical compound is currently known to act on the syndrome in its globality.

In this regard, plants with their great diversity of compounds, often pharmacologically active, have a good potential to be an alternative approach in METS care. A lot of substances have anti-inflammatory, anti-oxidative and anti-insulin resistance effects. Together, these three properties could break the pernicious circle of oxidative stress/inflammation and insulinresistance which sets up slowly with self-amplification [START_REF] Awwad | The Bitter Asteraceae: An Interesting Approach to Delay the Metabolic Syndrome Progression[END_REF].

Many bitter Asteraceae that are commonly consumed are particularly interesting because of their potential to prevent METS. These plants are rich in sesquiterpene lactones and hydroxycinnamic acid esters [START_REF] Awwad | The Bitter Asteraceae: An Interesting Approach to Delay the Metabolic Syndrome Progression[END_REF]. Many hydroxycinnamic acid esters such as transcaffeic acid (CA), trans-chlorogenic acid (CGA) and L-chicoric acid (CRA) are known for their pleiotropic biological activities both antioxidant [START_REF] Olayinka | Ameliorative Effect of Caffeic Acid on Capecitabine-Induced Hepatic and Renal Dysfunction: Involvement of the Antioxidant Defence System[END_REF][START_REF] Sato | In Vitro and in Vivo Antioxidant Properties of Chlorogenic Acid and Caffeic Acid[END_REF], anti-inflammatory [START_REF] Hwang | Anti-Inflammatory Effects of Chlorogenic Acid in Lipopolysaccharide-Stimulated RAW 264.7[END_REF][START_REF] Liu | Chicoric Acid Supplementation Prevents Systemic Inflammationinduced Memory Impairment and Amyloidogenesis via Inhibition of NF-_B[END_REF] and insulin sensitizing [START_REF] Ong | Anti-Diabetic and Anti-Lipidemic Effects of Chlorogenic Acid Are Mediated by Ampk Activation[END_REF][START_REF] Schlernitzauer | Chicoric Acid Is an Antioxidant Molecule That Stimulates AMP Kinase Pathway in L6 Myotubes and Extends Lifespan in Caenorhabditis Elegans[END_REF][START_REF] Tousch | Chicoric Acid, a New Compound Able to Enhance Insulin Release and Glucose Uptake[END_REF].

In a previous work by our research group, a root extract from Cichorium intybus (NCRAE) rich in chicoric acid (CRA) and chlorogenic acid (CGA) at a 70/30 molar ratio showed its capacity to induce, on in vitro model, an insulin sensitizing effect and a H2O2 protective effect in pretreatment in L6 muscular cells [START_REF] Tousch | Chicoric Acid, a New Compound Able to Enhance Insulin Release and Glucose Uptake[END_REF][START_REF] Azay-Milhau | Antihyperglycemic Effect of a Natural Chicoric Acid Extract of Chicory (Cichorium Intybus L.): A Comparative in Vitro Study with the Effects of Caffeic and Ferulic Acids[END_REF]. Additionally, in vivo experiments on streptozotocin diabetic rats have shown that NCRAE intraperitoneal administrations induced a clear anti-diabetic activity principally through an insulin-sensitizing effect. Moreover, the direct implication of CRA and CGA in the NCRAE anti-diabetic properties was demonstrated using a mixture of molecular standards of CRA and CGA (in the equivalent molar ratio of 70/30) which showed the same positive effects on streptozotocin diabetic rats [START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF].

The present study was designed to evaluate the preventive effects of a chronic oral administration NCRAE-like extract against insulin resistance and METS in the framework of a complementary natural pharmacotherapeutic approach.

In this context, an Asteraceae infused drink prepared by infusing dried dandelion (Taraxacum officinale F. H.Wigg) leaves and dried burdock (Arctium lappa L.) roots in water with a CRA/CGA molar ratio of 70/30, similar to the NCRAE ratio, was prepared and administered daily for 8 weeks to fructose-fed rats; a well-known animal model of METS. A comparison of the blood biochemistry, insulin and glucose tolerance parameters between the control cohort receiving a normal diet and the fructose cohorts supplemented or not with the infusion, allowed us to evaluate the infusion effect on METS. This article describes for the first time the effects of the CRA/CGA ratio after oral administration, thereby taking into account the impact of the intestinal barrier on CRA and CGA absorption.

An analysis rat-by-rat of the physiological parameters allowed us to compare the global animal responses to the Asteraceae infused drink diet. Some animals had a close NCRAE-like response whereas the others showed a predominant CGA effect. To confirm this fact, we evaluated the hepatic glucose-6 phosphatase (G6Pase) activities in liver tissues collected from the animals, since CGA is a well-known inhibitor of this enzyme [START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF].

Materials and Methods

Materials

Dried fragments of burdock root (Arctium lappa L.) and dandelion leaves (Taraxacum officinale F. H.Wigg) were purchased from a certified company: Nature valley (Maine-et-Loire; France).

Fructose, glucose, chlorogenic acid (trans-5-O-caffeoylquinic acid) and L-chicoric acid (2,3-O-di-O-caffeoyl-L-tartaric acid) standards were from Sigma-Aldrich (Saint-Louis, MO, USA), while Metformin, the glucometer Bayer Health Ascensia Contour (Ile de France, Paris), glucose indicator strips and insulin were obtained in a local pharmacy (Pharmacie des vignes, Montpellier, France).

Male Wistar genotype rats of five weeks old (_200g) were obtained from Janviers Labs (Le Genest-Saint-Isle, France).

Methods

Infused Drink Preparation

A preliminary step allowed us to optimize the amount of plants to mix in order to obtain the proper CGA/CRA ratio equivalent to NCRAE [START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF]. The dried leaves and root fragments were immersed in equal parts (w/w) in boiling water for 3 min, followed by a 30 min rest without stirring. The resulting infused drink was then filtered and stored at 4°C in the dark.

Chemical Analysis by HPCL and LC-MS

The infused drink was analyzed by HPLC using an Agilent 1200 series (Agilent, Santa Clara, CA, USA) equipped with a Nova-pak HR C18 250 mm x 4.6 mm x 5 m column (Waters Corps, Milford, CT, USA) and coupled with a DAD detector. The column thermostat was set to 25°C, and the samples were injected automatically with an autosampler from the same manufacturer and with the volume programmed at 20 L. The gradient was set with two phases. Phase A was composed of acetic acid 1%. Phase B was composed of acetonitrile. The program was as follows: time 0 was 100% A; from 0 to 15 min 40% A and 60% B; from 15 to 18 min 20% A and 80% B; from 18 to 25 min 100% A. The amount of CRA and CGA were quantified using a chromatographic peak area at 326 nm.

The chemical composition of the infused drink was characterized by LC-MS using a Synapt G2-S high-definition mass spectrometry system (Waters Corp., Milford, MA, USA) equipped with an electrospray ionization source, to characterize the elemental composition of parent and fragment ions according to the procedure previously described [START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF].

To characterize the elemental composition of the parent and fragment ions according to the procedure previously described [START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF], the chemical composition of the infused drink was characterized by LC-MS using a Synapt G2-S high-definition mass spectrometry system (Waters Corp., Milford, MA, USA) equipped with an electrospray ionization source. Chromatographic separation was carried out at a flow rate of 0.4 mL min -1 on the Acquity H-Class ultrahigh performance liquid chromatography (UPLC) system (Waters Corp., Milford, MA, USA), equipped with a Kinetex C18 100 A column (100 x 2.1 mm, 2.6 m beads) from Phenomenex (Le Pecq, France). The mobile phase consisted of permuted water (solvent A) and acetonitrile (solvent B), both phases acidified by 0.1% (v/v) formic acid. Mass spectra were acquired in the negative ionization mode with a capillary voltage of 3 kV. Tandem mass spectra were acquired in the Fast-DDA (Data Directed Analysis) mode so that the two most abundant ions in the full scan MS would trigger tandem mass spectrometry (MS2). The TOF mass analyzer was calibrated using phosphoric acid in 1/1 (v/v) acetonitrile/H2O from 50 to 1500 m/z to obtain mass accuracy within 3 ppm. The Synapt parameters were optimized using the CGA standard as follows: the sample cone was set at 20 V, the source temperature and desolvation temperature were set at 120 and 600 °C, respectively. Each sample was processed with MassLynx (V4.1) software.

Peaks obtained are listed in Table 1 in the order of elution, with their parent ion and their fragments. Their molecular formulas were assessed using MassLynx 4.2 software, and its monoisotopic mass-to-charge ratio were compared to the theoretical one. The three main hydroxycinnamic acid esters (CA, CRA, CGA) were unequivocally identified on the basis of their concordance with retention times, UV absorbance spectra, the mass-to-charge ratio of the parent ions, and MS2 fragment proportions to pure authentic standards. Other peaks were tentatively assigned based on bibliographic data [START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF]. The compound abundance of each hydroxycinnamic acid ester was compared among samples using the absorbance peak area.

In Vivo Experiment

Experimental Procedure

The animals (Wistar rats) were kept in a temperature-controlled room (20-22 °C) with a 12-h darkness-light cycle. They were accommodated three per cage where they were fed with a standard A04 SAFE-Augy-France diet and water ad libitum. The experiments were carried out in accordance with the rules of ethics and animal welfare. The experimental protocol has been approved by the Languedoc-Roussillon ethics committee (Authorization n APAFIS#2386-20200101409859 v3).

After an acclimatization period of one week, the animals were randomly divided into a control cohort (Control) (n = 6) receiving a conventional diet and into three fructose groups receiving 10% (w/v) fructose/water to induce an experimental METS [START_REF] Dhuique-Mayer | Preventive Action of Retinoids in Metabolic Syndrome/Type 2 Diabetic Rats Fed with Citrus Functional Food Enriched in-Cryptoxanthin[END_REF]. The fructose groups differed according to the treatment: the untreated fructose group (Fructose-NT) (n = 6), the fructose group treated with the Asteraceae infused-drink (500 mg.kg -1 .daily -1 ) (n = 8) (Fructose-AT) and the fructose group treated with metformin (100 mg.kg -1 .daily -1 ) (n = 6) (Fructose-MT) as drug control.

Weight Evolution

After random affectation of rat to the various groups, the animals' weight was measured each week throughout the experiment.

Glycemia, Insulinemia and Triglyceride Levels

The plasma glucose level (mg.dL -1 ) was measured using the BIOLABO colorimetric glucose assay kit, ref. 80009 (Maizy, France). The plasma insulin level (ng.mL -1 ) was determined using the rodent insulin ELISA kit purchased from ALPCO (Eurobio-Ingen, les Ullis, France). The plasma triglycerides (TG) level was analyzed using the BIOLABO kit ref.

90406-90416-(Maizy, Aisne, France).

Oral Glucose Tolerance Test (OGTT)

The OGTT was carried out after 8 weeks. After a 5 h fasting period, a glucose solution was administered orally (3 g.kg -1 ). Blood was taken from the caudal vein of the rats at different times (0, 15, 30, 60, 120 and 180 min). Glycemia was determined using a glucometer (Accu Chek Guide, Roche, Switzerland) which was calibrated before each use with a control solution (Accu-Chek Ref 07748906).

Insulin Tolerance Test (ITT)

The ITT was carried out at 8 weeks. After a 5 h fasting period, insulin (0.5 IU.kg -1 ) was administered by intra-peritoneal injection and blood was taken from the caudal vein of the rats at different times (0, 15, 30, 60 and 120 min). The blood glucose level was determined using the glucometer.

Blood Pressure Measurement

Rats were taken out from the animal room and brought into a quiet separate laboratory. The method used was the indirect measurement of systolic blood pressure (tail cuff) without external preheating. The equipment (Harvard Apparatus, Les Ullis, France) included animal holders, a manual scanner, a pulse amplifier, a tail cuff, and a central unit for digital recording. Ambient temperature was stabilized at 30 °C. Animals were conditioned to this assay procedure to obtain readings. Systolic blood pressure was measured in conscious animals and theme an of five readings was considered as systolic blood pressure measurement.

In Vitro Experiment

Microsome Purification

At the end of the 8-week experiment, the rats were euthanized, and the liver was taken and stored at -80 °C. The liver (1 g) was delicately ground in a potting vessel containing a lysis buffer (250 mM sucrose; 50 mg.mL DNase I; 1 mM MgCl2; 4 mM HEPES; Protease inhibitor 4 M (Pepstatin, Aprotinin, PMSF)). The ground livers were centrifuged at 10,000 x g for 10 min at 4 °C. The recovered supernatant was lysed in nitrogen (55 bar, 15 min with agitation) and then placed on a sucrose gradient (0.8 to 2.0 M) and centrifuged at 25,000 x g for 16 h at 4 °C. The different fractions were recovered independently, and the proteins content were assayed with a Bradford reagent. The fractions with the highest G6pase activity were used for the experiment.

Glucose-6-Phosphatase Activity

The glucose-6-phosphatase activities were obtained using the protocol previously described [START_REF] Azay-Milhau | Antihyperglycemic Effect of a Natural Chicoric Acid Extract of Chicory (Cichorium Intybus L.): A Comparative in Vitro Study with the Effects of Caffeic and Ferulic Acids[END_REF][START_REF] Daniele | Phosphatidylinositol 3-Kinase Translocates onto Liver Endoplasmic Reticulum and May Account for the Inhibition of Glucose-6-Phosphatase during Refeeding[END_REF] with some modifications. Briefly, 2 g of microsomal suspension were incubated for 30 min in 20 mM glucose 6 phosphate buffer (20 mM glucose-6-phosphate; 250 mM sucrose; 500 mM HEPES). The reaction was stopped, and Pi was determined by the addition of a malachite green reagent (1 part 4.2% ammonium molybdate in 3 parts 0.2% malachite green; 5 mol/L H2SO4 and 0.1% Tween 20). After 20 min incubation at room temperature, the optical density was measured at 660 nm. A calibration curve with different NaH2PO4 concentration was established. Results were expressed as n moles of inorganic phosphate produced in 1 h for 2 _g of protein measured. Chlorogenic acid (50 g mL -1 ) was used as a positive control to verify membrane integrity.

Statistical Analysis

Data are expressed as means +/-S.E.M. and were analyzed using the XLSTAT Premium software by Addinsoft. One-way ANOVA was performed for data followed by Fisher's LSD posthoc test for multiple comparisons. A value of p < 0.05 was considered as statistically significant.

Results

Chemical Composition Analysis of the Asteraceae Infused-Drink by LC-MS

The chemical analysis of this infused-drink (Table 1) revealed the presence of three caffeoyltartaric acid esters (P2, P8 and P9), originating from the Taraxacum fraction. Peak 8 co-eluted with the L-chicoric acid standard and had both a similar absorbance spectrum and a similar fragmentation pattern. Peak 9 had at least the same fragmentation pattern and may correspond to one of its diastereoisomers, already described in literature [START_REF] Jaiswal | How to Identify and Discriminate between the Methyl Quinates of Chlorogenic Acids by Liquid Chromatography-Tandem Mass Spectrometry[END_REF][START_REF] Schütz | Characterization of Phenolic Acids and Flavonoids in Dandelion (Taraxacum Officinale WEB. Ex WIGG.) Root and Herb by High-Performance Liquid Chromatography/Electrospray Ionization Mass Spectrometry: Phenolic Acids and Flavonoids in Dandelion Root and Herb[END_REF]. The infused drink contained a large amount of chlorogenic acid (trans-5-O-caffeoylquinic acid) and 10 additional caffeoylquinic acid esters in a lower proportion. Based on their 326-nm-absorbance integrals, we deduced that the molar ratio of CGA to the total of CRA isomers was approximately equivalent to (30/70).

Since flavonoids and sesquiterpenes are known to have potential anti-hyperglycemic bioactivities, we tried to identify them in our infused drink. We observed that immersing parts of plants in boiling water for 3 min followed by a rest of 30 min without stirring was not long enough to extract flavonoids of Taraxacum officinale (quercetin diglycosides and trigycosides, luteolin diglycosides, chrysoeriol diglycosides), listed in [START_REF] Schütz | Characterization of Phenolic Acids and Flavonoids in Dandelion (Taraxacum Officinale WEB. Ex WIGG.) Root and Herb by High-Performance Liquid Chromatography/Electrospray Ionization Mass Spectrometry: Phenolic Acids and Flavonoids in Dandelion Root and Herb[END_REF][START_REF] Dias | Nutritional Composition, Antioxidant Activity and Phenolic Compounds ofWild Taraxacum Sect[END_REF], of Arctium lappa (quercetin rhamnoside, quercetin-3-O-glucuronide and quercetin-3-O-vicianoside), listed in [START_REF] Lim | Edible Medicinal and Non Medicinal Plants[END_REF][START_REF] Wang | Arctium Species Secondary Metabolites Chemodiversity and Bioactivities[END_REF]. By contrast, these flavonoids were present in methanolic extracts of the same powdered sample (data not shown). We also verified that the sesquiterpenes of Taraxacum officinale leaves described by [START_REF] Esatbeyoglu | Sesquiterpene Lactone Composition and Cellular Nrf2 Induction of Taraxacum Officinale Leaves and Roots and Taraxinic Acid b-D -Glucopyranosyl Ester[END_REF] i.e., taraxacolide esters and taraxinic acid derivatives, were not extracted. Similarly, sesquiterpenes of Arctium lappa previously isolated from shoots [START_REF] Wang | Arctium Species Secondary Metabolites Chemodiversity and Bioactivities[END_REF], were not found in our extract. The extraction medium was not enough apolar for extracting flavonoids and sesquiterpenes of the two species. In conclusion, this infused drink was mainly composed of L-chicoric acid, 1,5-O-dicaffeoyl-4-O-malonylquinic acid and chlorogenic acid, associated with minor caffeoylquinic acid isomers.

In Vivo Experiment

Animal Weight Evolution

Weight evolution over the 8 weeks of the experiment was slightly elevated (not statistically significant) for fructose-NT rats versus control rats. Metformin treatment did not modify the evolution (Figure 1A). In contrast, the chronic Asteraceae infused drink induced a significant decrease in body weight starting at the fourth week. This effect was maintained at the eighth week (p < 0.05).

At the eighth week (Figure 1B), the Fructose-NT rats had a higher body weight (489 +/-15.2 g) than the control rats (463+/-8.8 g). The daily Asteraceae infused drink induced a significant decrease (p < 0.05) in body weight of the Fructose-AT (443+/-12.9 g) rats when compared to Fructose-NT. Metformin treatment in fructose rats led to a nonsignificant decrease in weight (481 +/-19.2 g) compared to the Fructose-NT rats.

Biological Parameters

Glycemia (Figure 2A): At the eighth week, the fructose beverage induced a clear hyperglycemia (155 mg.dL -1 +/-8.6) compared to control rats (121 +/-5.5 mg.dL -1 ) (p < 0.05). The daily administration of the Asteraceae infused drink or metformin reduced significantly (p < 0.05) the fructose induced hyperglycemia to be significant in Fructose-AT (123 +/-4.9 mg. dL -1 ) and in Fructose-MT (134 +/-10 mg.dL -1 ). Glycemia correction was clearer in the Fructose-AT rats group. Insulinemia (Figure 2B): At the eighth week, fructose administration significantly increased (p < 0.05) the plasma insulin level at 2.8+/-0.35 ng.mL -1 in Fructose-NT rats versus 1.08 +/-0.15 ng.mL -1 for control rats. Metformin treatment significantly decreased fructose induced hyperinsulinemia to 1.86 +/-0.31 ng.mL -1 (p < 0.05). Surprisingly, the fructose hyperinsulinemia was not reduced by the Asteraceae infused drink (2.9+/-0.40 ng.mL -1 ). Triglyceridemia (Figure 2C): After 8 weeks, the fructose beverage provoked a hypertriglyceridemia (p < 0.05) in fructose-NT rats (117+/-12.5mg.dL -1 ) versus (52+/-7.6mg.dL -1 ) for control rats. The hyper-triglyceridemia was reversed in fructose-MT rats (67 +/-12.8 mg. dL 1 ). With the Asteraceae infused drink, a significant decrease was also observed (87 +/-8.1 mg.dL -1 ) (p < 0.05) but less than with the metformin treatment.

Oral Glucose Tolerance Test (OGTT)

At the eighth week of the experiment, an oral glucose intake provoked in rats a hyperglycemic peak after 15 min for all groups. This glucose peak level is significantly (p < 0.05) higher in fructose rats (184 +/-8.0 mg.dL -1 ) compared to the control (159 +/-2.1 mg.dL -1 ). Chronic metformin administration or Asteraceae infused drink intake in fructose rats significantly (p < 0.05) reduced the hyperglycemic peak to values close to normal (158+/-6.9 mg.dL -1 and 165+/-3.7 mg.dL -1 , respectively) (Figure 3A). The return to basal glycemic values was slower for fructose rats when compared to control rats. Treatment with Asteraceae and metformin allowed a faster return to the basal blood glucose value.

Insulin Tolerance Test (ITT)

At the eighth week of the experiment, an intraperitoneal injection of insulin induced a clear decrease in glycemia in control rats (Figure 3B). Blood glucose level decreased from 105 +/-3.3 mg.dL -1 to 75+/-1.5 mg.dL -1 at 30 min and then gradually rose back to basal value. In fructose treated rats (Fructose-NT), an insulin load induced a smaller reduction in blood glucose reaching 86.6 +/-6.7 mg.dL -1 at 30 min, a rapid return to normal blood glucose was observed. In metformin treated rats (Fructose-MT), the drop of glycemia after insulin load was similar to the values observed with the control rats (80 +/-1.9 mg.dL -1 ). As for the daily treatment by the Asteraceae infused -drink, ITT was characterized by a drastic fall in glycemia, reaching 68 +/-4.8 mg.dL -1 at 30 min. This hypoglycemia lasted after the 120 min endpoint.

Arterial systolic blood pressure (SBP) measured at the eighth week of the experiment (Figure 4) showed, as expected, a statistically significant elevation for the Fructose-NT group when compared with the control group of animals. Fructose-MT rats, treated with metformin, demonstrated a significant decrease of SBP when compared to the Fructose-NT group. This observation validated the assay since metformin was used in an internal standard in this assay. Similarly, the Fructose-AT group's SBP was significantly decreased to a statistically similar level than the Fructose-MT group. Neither group reached the full correction of SBP as they remained slightly above the Control group. Different letters show significant differences at (p<0.05).

Specific Rat-by-Rat Analysis of Results Obtained with Asteraceae Infused Drink

The analysis of insulinemia of fructose rats treated by the Asteraceae infused-drink revealed the identification of two subgroups: the first with a clear hyperinsulinemia, subgroup-HI (n = 5), the second subgroup with normal insulinemia, subgroup-NI (n = 3) (Figure 5A). Consequently, ITTs were different: hypoglycemia in HI rats was more important and persistent than in NI rats (Figure 6). The final number of animals per subgroups was lower than the initial complete Fructose-AT cohort, which was n = 8. So, it will be necessary to confirm this result with a more important animal's cohort in our future investigations. Nonetheless, the differential insulinemia between the two subgroups is sufficiently significant to consider this tendency. Glucose-6-phosphatase activity of hepatic microsomal fraction was clearly reduced (p < 0.05) in all rats treated by the Asteraceae infused drink. However, in HI rats this activity was significantly lower than the one observed in NI rats (Figure 5B).

Discussion

The present study demonstrated that a supplementation with plant extract from dandelion leaves and burdock roots rich in hydroxycinnamic acid esters, particularly in CGA and CRA in a 70/30 molar ratio, could prevent METS induced by fructose in rats. The infusion of the dried parts of plants allowed us to obtain essentially the hydroxycinnamic acid esters content without the sesquiterpene lactones. After eight weeks of the fructose diet, rats developed a cluster of METS abnormalities including hyperglycemia, hyperinsulinemia, hypertriglyceridemia, insulin resistance demonstrated by OGTT and ITT, as well as hypertension. Our results are in agreement with previous results published by several authors that used the fructose diet induced METS [START_REF] Hwang | Anti-Inflammatory Effects of Chlorogenic Acid in Lipopolysaccharide-Stimulated RAW 264.7[END_REF][START_REF] Dupas | Progressive Induction of Type 2 Diabetes: Effects of a Reality-Like Fructose Enriched Diet in YoungWistar Rats[END_REF][START_REF] Mamikutty | The Establishment of Metabolic Syndrome Model by Induction of Fructose Drinking Water in Male Wistar Rats[END_REF]. Metformin was used as a positive control to prevent hyperglycemia, hyperinsulinemia, and hypertension through its insulinsensitizing effect. We also observed a triglyceridemia modulation as previously shown [START_REF] Kannappan | Insulin Sensitizing Actions of Fenugreek Seed Polyphenols, Quercetin & Metformin in a Rat Model[END_REF][START_REF] Anurag | Metformin Improves Lipid Metabolism and Attenuates Lipid Peroxidation in High Fructose-Fed Rats[END_REF]. A slight (not statistically significant) body weight gain was recorded. The daily Asteraceae infused drink prevented most disorders induced by fructose, including hypertension, but with the exception of hyperinsulinemia. Moreover, a clear decrease in body weight gain was observed which is of interest in the management of obesity associated to METS. This result could be explained by the fact that dandelion is known for its ability to reduce adipogenesis and lipid accumulation [START_REF] Gonzales-Castejon | Reduction of adipogenesis and lipid accumulation by Taraxacum officinale (Dandelion) extracts in 3T3L1 adipocytes: An in vitro study[END_REF] as well as, additionally, its diuretic virtue which may also contribute to limit weight gain [START_REF] Schlernitzauer | Chicoric Acid Is an Antioxidant Molecule That Stimulates AMP Kinase Pathway in L6 Myotubes and Extends Lifespan in Caenorhabditis Elegans[END_REF][START_REF] Clare | The Diuretic Effect in Human Subjects of an Extract of Taraxacum Officinale Folium over a Single Day[END_REF][START_REF] Lim | Edible Medicinal And Non-Medicinal Plants[END_REF][START_REF] Hook | Evaluation of Dandelion for Diuretic Activity and Variation in Potassium Content[END_REF]. The hyperinsulinemia observed in animals without insulin resistance correlated to a strong ITT response suggesting a stimulation of insulin release by the Asteraceae infusion-drink. We have previously shown that NCRAE (CRA/CGA) is able to increase insulin secretion and CGA alone is described as a marked insulin secretion stimulator [START_REF] Tousch | Chicoric Acid, a New Compound Able to Enhance Insulin Release and Glucose Uptake[END_REF][START_REF] Sanchez | Potential of the Chlorogenic Acid as Multitarget Agent: Insulin-Secretagogue and PPAR  Dual Agonist[END_REF]. This last result suggested the need for a rat-byrat analysis. This more specific analysis allowed us to distinguish two subgroups of responders in animals supplemented with the Asteraceae infused drink. Although the numbers of animals by cohort are low due to the group splitting after completion of the experiment, the marked trend allowed us to distinguish two subgroups: the first is characterized by hyperinsulinemia and strong ITT (n = 5) in contrast with the second subgroup demonstrating normal insulinemia and normal ITT (n = 3). In accordance with the literature, regarding the first subgroup-HI, we can consider that the results recorded may be based on CGA effects. In contrast, we revealed a clear decrease of hyper-insulinemia for the second subgroup-NI suggesting a more complex response involving potential synergic actions of the two caffeic acid derivatives leading to an insulin sensitization effect and a slight insulin secretion stimulation in accordance with the NCRAE effect [START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF]. To test the hypothesis of a predominant CGA effect in the subgroup-HI, we investigated the hepatic microsomal G6Pase activities as a specific CGA target. CGA has been recognized as a hepatic G6Pase inhibitor [START_REF] Cho | Chlorogenic Acid Exhibits Anti-Obesity Property and Improves Lipid Metabolism in High-Fat Diet-Induced-Obese Mice[END_REF][START_REF] Arion | Chlorogenic Acid and Hydroxynitrobenzaldehyde: New Inhibitors of Hepatic Glucose 6-Phosphatase[END_REF][START_REF] Hemmerle | Chlorogenic Acid and Synthetic Chlorogenic Acid Derivatives: Novel Inhibitors of Hepatic Glucose-6-Phosphate Translocase[END_REF]. We observed a normal hepatic G6Pase activity exactly similar to an NCRAE-like effect previously reported [START_REF] Azay-Milhau | Antihyperglycemic Effect of a Natural Chicoric Acid Extract of Chicory (Cichorium Intybus L.): A Comparative in Vitro Study with the Effects of Caffeic and Ferulic Acids[END_REF][START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF] in the subgroup-NI (normal insulinemia) whereas in subgroup-HI (hyperinsulinemia), a significant decrease in hepatic G6Pase activity was observed. The existence of these two subgroups might be explained by an inter-individual disparity of CGA and CRA bioavailability. In fact, if CGA bioavailability is largely discussed [START_REF] Lafay | Chlorogenic Acid Is Absorbed in Its Intact Form in the Stomach of Rats[END_REF][START_REF] Lu | Chlorogenic Acid: A Comprehensive Review of the Dietary Sources, Processing Effects, Bioavailability, Beneficial Properties, Mechanisms of Action, and Future Directions[END_REF][START_REF] Stalmach | Bioavailability of Chlorogenic Acids Following Acute Ingestion of Coffee by Humans with an Ileostomy[END_REF][START_REF] Xiao | Chicoric Acid Prevents Obesity by Attenuating Hepatic Steatosis, Inflammation and Oxidative Stress in High-Fat Diet-Fed Mice[END_REF], there is little data available on CRA bioavailability. Nonetheless, the hyper-insulinemia CGA-like effect can be considered as beneficial due to its hypoglycemic action.

In addition to the overall data obtained in the present assay, it should be mentioned that the original infused drink containing NCRAEs and its CRA/CGA molecular ratio are providing high protection against oxidative stress. This potential was demonstrated to be associated with antidiabetic effects [START_REF] Azay-Milhau | Antihyperglycemic Effect of a Natural Chicoric Acid Extract of Chicory (Cichorium Intybus L.): A Comparative in Vitro Study with the Effects of Caffeic and Ferulic Acids[END_REF][START_REF] Ferrare | Increase in Insulin Sensitivity by the Association of Chicoric Acid and Chlorogenic Acid Contained in a Natural Chicoric Acid Extract (NCRAE) of Chicory (Cichorium Intybus L.) for an Antidiabetic Effect[END_REF] and thereby contribute to the beneficial effects recorded in the present study on METS.

Conclusions

In conclusion our original Asteraceae infused drink processed from dandelion leaves and burdock roots extracts did demonstrate beneficial properties to prevent METS. The molar ratio 70/30 was confirmed to be efficient in inducing the observed biological effects in vivo. A combined influence on insulin secretion and a potential reduction of adiposity may have contributed to the overall bioactivity. As well, the extended hypoglycemia recorded during the ITT challenge suggested an elevated insulin sensitizing effect. This study opens the way to other perspectives (1) an in depth molecular and metabolomics exploration of synergistic action of the CRA-CGA couple on insulin secretion, insulin sensitivity and antioxidant signaling pathways and (2) by a clinical trial on METS patients with obesity and elevated risk of cardiovascular disease.

Finally, this experiment also highlights the complexity of the response when a mix of compounds are used. These last effects could be correlated to the bioavaibility of each compound in the infusion. Therefore, it will be important, in our future studies, to investigate the complex interplays between compounds bioavailability and their combined bioactivities in natural plant extracts.

Figure 1 .

 1 Figure 1. Weight of animals during the experimentation.

Figure 2 .

 2 Figure 2. Biochemical parameters evaluated at the end of the experiment (week 8).

Figure 3 .

 3 Figure 3. Tests of glucose and insulin tolerance at the end of experiment.

Figure 4 .

 4 Figure 4. Systolic arterial blood pressure at the end of the experiment (week 8).

Figure 5 .

 5 Figure 5. Specific analysis of the two subgroups of the Asteraceae infused drink.

Figure 6 .

 6 Figure 6. Specific analysis of the two subgroups of Asteraceae infused drink.

Acknowledgments:

We sincerely thank Gérard Ribes for consenting to give us precious scientific advice and his help to the redaction of this publication.

Funding:

This research received no external funding.

Institutional Review Board Statement:

All animal procedures were performed in accordance with the Guidelines for Care and Use of Laboratory animals of the University of Montpellier, of the European Union and according to the guidelines of the national institute of Health (National Institutes of Health, 1985). All experiments were approved by the Animal Ethic Committee entitled "Comite d'Ethique pour l'Experimentation Animale" of the University of Montpellier (France) with the agreement of the French Ministry of Agriculture, Agrifood systems and Forestry as well as the French Ministry of Education, Universities and Research. The national experiment approval number was:23868-202001301409859v.

Data Availability Statement:

Data is contained within the article.

Informed Consent Statement:

Not applicable.

Conflicts of Interest:

The authors declare no conflict of interest.


Alexandre D Jesus
email: ajesus@dei.uc.pt

Luís Paquete
email: paquete@dei.uc.pt

Bilel Derbel
email: bilel.derbel@univ-lille.fr

Arnaud Liefooghe
email: arnaud.liefooghe@univ-lille.fr

On the Design and Anytime Performance of Indicator-based Branch and Bound for Multi-objective Combinatorial Optimization

Keywords: Computing methodologies → Search methodologies, • Theory of computation → Branch-and-bound, • Mathematics of computing → Combinatorial algorithms, Multi-objective combinatorial optimization, Search methodologies, Branch and bound, Indicator-based approaches

In this article, we propose an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization that uses a best-first search strategy. In particular, assuming maximizing objectives, the next node to be processed is chosen with respect to the quality of its upper bound. This quality is given by a binary quality indicator, such as the binary hypervolume or the 𝜀-indicator, with respect to the archive of solutions maintained by the branch and bound algorithm. Although the I-BB will eventually identify the efficient set, we are particularly interested in analyzing its anytime behavior as a heuristic. Our experimental results, conducted on a multi-objective knapsack problem with 2, 3, 5, and 7 objectives, indicate that the I-BB can often outperform the naive depth-first and breadth-first search strategies, both in terms of runtime and anytime performance. The improvement is especially significant when the branching order for the decision variables is random, which suggests that the I-BB is particularly relevant when more favorable (problem-dependent) branching orders are not available.

INTRODUCTION

Multi-objective combinatorial optimization (MOCO) deals with the optimization of 𝑚 objective functions over a combinatorial solution space. Given the often conflicting nature of the objectives, there may not exist a single optimal solution under the notion of Pareto efficiency, but rather many efficient solutions that describe the tradeoffs between the objectives. Although MOCO problems are known to be NP-hard and the efficient set may be exponentially large [START_REF] Ehrgott | Multicriteria Optimization[END_REF], there are nonetheless problem instances for which the efficient set can be computed in a feasible amount of time [START_REF] Rui Figueira | Easy to Say They Are Hard, but Hard to See They Are Easy-Towards a Categorization of Tractable Multiobjective Combinatorial Optimization Problems[END_REF]. As such, it is desirable to have approaches that can both (i) find the efficient set given enough time and (ii) return an approximate solution set when interrupted before completion.

Multi-objective branch and bound algorithms [START_REF] Przybylski | Multi-Objective Branch and Bound[END_REF][START_REF] Visée | Two-Phases Method and Branch and Bound Procedures to Solve the Bi-Objective Knapsack Problem[END_REF] implicitly traverse the complete solution space of a problem while maintaining an archive of the best solutions found. As such, branch and bound algorithms can be seen as both exact and heuristic algorithms depending on whether or not they are executed to completion. A key aspect of a branch and bound approach is to split the original problem into several subproblems at each branching step. Each subproblem consists of assigning values to solution components, given that some other components are already fixed. Assuming maximization, an upper bound for each subproblem is used to show whether the corresponding subproblem contains potential efficient solutions for the original problem. If not, then it is not worthwhile solving that subproblem. Of particular interest to us is to understand which subproblem to choose such that it leads to better performance for MOCO problems both in terms of runtime and anytime behavior. We argue that this selection should be based on the quality of the upper bound with respect to the archive. Up to our knowledge, the idea of using the quality of the upper bound to guide the search of the branch and bound algorithm has not been considered in multi-objective optimization. It has, however, been used in single-objective optimization, e.g. [START_REF] Van-Dat | Constrained Two-Dimensional Cutting Stock Problems a Best-First Branch-and-Bound Algorithm[END_REF].

In this work, we propose using a binary indicator to measure the quality of the upper bound with respect to the archive maintained by the branch and bound. This leads to a new family of branch and bound algorithms for MOCO, namely, indicator-based branch and bound (I-BB). We remark that, in addition to the possible improvements discussed in the previous paragraph, the use of a quality indicator in a multi-objective search technique gives the decision maker a chance to control the search, since an indicator can, for example, be designed or parameterized to benefit regions of the objective space that are considered to be more relevant.

The use of quality indicators to guide the search strategy is commonly used by multi-objective evolutionary and heuristic approaches. Notably, IBEA [START_REF] Zitzler | Indicator-Based Selection in Multiobjective Search[END_REF] is a general indicator-based evolutionary algorithm that uses a quality indicator to remove the least promising solutions from a population during the selection process of the evolutionary approach. SMS-EMOA [START_REF] Beume | SMS-EMOA: Multiobjective Selection Based on Dominated Hypervolume[END_REF] is an evolutionary algorithm that combines ideas from other evolutionary algorithms, such as NSGA-II [START_REF] Deb | A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[END_REF], and that considers the hypervolume quality indicator [START_REF] Zitzler | Multiobjective Optimization Using Evolutionary Algorithms -A Comparative Case Study[END_REF] to remove the least promising solution from the population during selection. HypE [START_REF] Bader | HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization[END_REF] is an evolutionary algorithm that similarly uses the hypervolume indicator to remove solutions from the population in the selection step, but that considers a Monte Carlo simulation to approximate the hypervolume due to its increasing computational cost with respect to the number of objectives. SPAM [START_REF] Zitzler | On Set-Based Multiobjective Optimization[END_REF] is a heuristic resembling a hill climber that considers a heuristic mutation to the archive of solutions that makes use of a quality indicator to remove the least promising solutions. In [START_REF] Dubois-Lacoste | Anytime Pareto Local Search[END_REF] the authors consider a Pareto local search [START_REF] Paquete | On Local Optima in Multiobjective Combinatorial Optimization Problems[END_REF] variant that uses a quality indicator to select the next solution for processing. However, to our knowledge, a quality indicator has never been used to guide the search of exact algorithms such as branch and bound.

To study the performance of the proposed I-BB approach we analyze its impact on the total runtime of the algorithm, as well as on its anytime behavior in terms of the quality of the archive as a function of CPU time. To measure the quality of an approximate solution set we consider the hypervolume quality indicator [START_REF] Zitzler | Multiobjective Optimization Using Evolutionary Algorithms -A Comparative Case Study[END_REF]. To measure the quality of an upper bound with respect to the archive we consider two binary quality indicators: the binary hypervolume quality indicator [START_REF] Zitzler | Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications[END_REF], and the 𝜀-indicator [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF]. For the empirical study we consider the multi-objective binary knapsack problem with 2, 3, 5, and 7 objectives. Our results indicate that the I-BB approach can often improve, or match, the performance of more naïve branch and bound approaches, especially when considering a random branching order.

The rest of this paper is organized as follows. In Section 2 we introduce the necessary definitions related to multi-objective optimization, quality indicators, and anytime performance. In Section 3 we introduce the proposed I-BB approach under a more general branch and bound framework for MOCO. In Section 4 we present the multi-objective binary knapsack problem and discuss the implementation details of the I-BB algorithm for this problem. In Section 5 we present the results of our empirical study. To conclude, in Section 6 we give a summary of the work and discuss possible directions for the future.

BACKGROUND

In the following we introduce the necessary definitions related to multi-objective optimization and anytime performance.

Concepts and Notation for MOCO

Assuming, without loss of generality, that all objective functions are to be maximized, a MOCO problem can be defined by: argmax

𝑥 ∈𝑋 𝑓 (𝑥) = (𝑓 1 (𝑥), 𝑓 2 (𝑥), . . . , 𝑓 𝑚 (𝑥)) (1)
where 𝑥 denotes a solution, 𝑋 denotes the set of all feasible solutions, and 𝑓 𝑖 (𝑥) → R denotes the 𝑖th objective function to be maximized. Given two objective vectors 𝑦, 𝑦 ′ ∈ R 𝑚 we say that 𝑦 weakly dominates 𝑦 ′ iff 𝑦 𝑖 ≥ 𝑦 ′ 𝑖 for every 𝑖 ∈ {1, 2, . . . , 𝑚}. This relation is denoted by 𝑦 ≥ 𝑦 ′ . Moreover, we say that 𝑦 dominates 𝑦 ′ iff 𝑦 ≥ 𝑦 ′ and 𝑦 ′ ≱ 𝑦. This relation is denoted by 𝑦 > 𝑦 ′ . Then two objective vectors 𝑦, 𝑦 ′ ∈ R 𝑚 are said to be incomparable or mutually nondominated iff 𝑦 ≯ 𝑦 ′ and 𝑦 ′ ≯ 𝑦, i.e. iff neither weakly dominates the other. We describe two solutions 𝑥, 𝑥 ′ ∈ 𝑋 with respect to the relations that hold for their objective vectors, e.g. we say that 𝑥 dominates 𝑥 ′ iff 𝑓 (𝑥) > 𝑓 (𝑥 ′ ). The efficient set to a MOCO problem is given by the set of all solutions that are not dominated by any other feasible solution. A set of mutually non-dominated feasible solutions is called an approximate solution set.

We extend the relations above to sets of vectors in the objective space [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF]. Given two sets 𝐴, 𝐵 ⊂ R 𝑚 we say that 𝐴 weakly dominates 𝐵, denoted by 𝐴 ≥ 𝐵, iff every 𝑏 ∈ 𝐵 is weakly dominated by an objective vector 𝑎 ∈ 𝐴, formally:

𝐴 ≥ 𝐵 ⇐⇒ ∀𝑏 ∈ 𝐵 ∃𝑎 ∈ 𝐴 s.t. 𝑎 ≥ 𝑏
We say that 𝐴 dominates 𝐵, denoted by 𝐴 > 𝐵 iff every 𝑏 ∈ 𝐵 is dominated by an objective vector 𝑎 ∈ 𝐴, formally: 𝐴 > 𝐵 ⇐⇒ ∀𝑏 ∈ 𝐵 ∃𝑎 ∈ 𝐴 s.t. 𝑎 > 𝑏 And we say that 𝐴 and 𝐵 are incomparable iff 𝐴 ≱ 𝐵 and 𝐵 ≱ 𝐴.

Several quality indicators have been proposed to quantify the quality of approximate solution sets as a scalar value. These can be useful, for example, to distinguish between approximate solution sets that are incomparable in terms of dominance. One such indicator is the hypervolume quality indicator [START_REF] Zitzler | Multiobjective Optimization Using Evolutionary Algorithms -A Comparative Case Study[END_REF], which corresponds to the multi-dimensional area dominated by the objective vectors of a solution set with respect to a given reference point in the objective space. Formally, for a set 𝐴 ⊂ R 𝑚 and a reference point 𝑟 ∈ R 𝑚 , the hypervolume is defined by:

𝐻 (𝐴, 𝑟 ) = 𝜆 𝑞 ∈ R 𝑚 | ∃ 𝑎 ∈ 𝐴 : 𝑟 ≥ 𝑞 ≥ 𝑎 ( 2
)
where 𝜆 is the Lebesgue measure. We also consider the binary hypervolume quality indicator [START_REF] Zitzler | Evolutionary Algorithms for Multiobjective Optimization: Methods and Applications[END_REF], which corresponds to the multidimensional area dominated by a set but not by another, that is:

𝐻 (𝐴, 𝐵, 𝑟 ) = 𝐻 (𝐴 ∪ 𝐵, 𝑟 ) -𝐻 (𝐵, 𝑟 ) (3)
We also consider the multiplicative 𝜀-indicator [START_REF] Zitzler | Performance Assessment of Multiobjective Optimizers: An Analysis and Review[END_REF], which, given two solution sets, corresponds to the minimum factor by which every objective vector of the former has to be multiplied such that it weakly dominates the latter. Formally, given two sets 𝐴, 𝐵 ⊂ R 𝑚 , the multiplicative 𝜀-indicator is given by:

𝐸 (𝐴, 𝐵) = max 𝑎 ∈𝐴 min 𝑏 ∈𝐵 max 𝑖 ∈ {1,...,𝑚 } 𝑏 𝑖 𝑎 𝑖 (4)
An important characteristic of these quality indicators is that they are compatible with the weak dominance relation between solution sets. In particular, if for two sets 𝐴, 𝐵 ⊂ R 𝑚 it holds that 𝐴 ≥ 𝐵, then it also holds that 𝐻 (𝐴, 𝑟 ) ≥ 𝐻 (𝐵, 𝑟 ) for a given reference point 𝑟 , and that 𝐻 (𝐴, 𝑅, 𝑟 ) ≥ 𝐻 (𝐵, 𝑅, 𝑟 ) and 𝐸 (𝐴, 𝑅) ≤ 𝐸 (𝐵, 𝑅) for a given reference set 𝑅 ⊂ R 𝑚 . A relevant implication is that when adding solutions to a set the quality returned by these indicators improves monotonically, under the assumption that the reference point and/or reference set for the binary indicators are unchanged.

Anytime Behavior

To analyze the anytime performance of a run 𝜔 of an algorithm that keeps a solution archive we consider the performance trace 𝑄 𝜔 (𝑡) → R + that describes the trade-off between the quality of the archive and the execution time 𝑡 ∈ R + . For this work, we consider the archive quality in terms of the unary hypervolume indicator defined in Equation 2, and execution time in terms of CPU time.

For analyzing the performance over multiple runs Ω we consider the performance profile [START_REF] Grunert Da Fonseca | Inferential Performance Assessment of Stochastic Optimisers and the Attainment Function[END_REF][START_REF] Holger | Stochastic Local Search: Foundations & Applications[END_REF][START_REF] Jesus | Algorithm Selection of Anytime Algorithms[END_REF] given by:

𝑃 Ω (𝑡, 𝑞) = 1 |Ω| ∑ 𝜔 ∈Ω 𝐼 {𝑄 𝜔 (𝑡) ≥ 𝑞} (5)
that denotes the probability of a run of the algorithm having an archive of quality greater or equal to 𝑞 ∈ R at time 𝑡 ∈ R + .

To measure the anytime quality of multiple independents runs Ω of an algorithm we aggregate those runs into a performance profile and compute the quality measure given by its bi-dimensional integral [START_REF] Jesus | Algorithm Selection of Anytime Algorithms[END_REF][START_REF] López | Automatically Improving the Anytime Behaviour of Optimisation Algorithms[END_REF], that is:

∫ ∞ 0 ∫ 𝑡 0 𝑃 Ω (𝑡, 𝑞) 𝑑𝑡 𝑑𝑞 (6)
where 𝑡 denotes the timeout for the runs.

INDICATOR-BASED BRANCH AND BOUND

Branch and bound algorithms implicitly visit all feasible solutions. They recursively divide the solution space into subspaces, each of which encapsulates a subproblem of the original problem. For the purpose of this work we consider that each subproblem gives rise to a lower and an upper bound [START_REF] Ehrgott | Bounds and Bound Sets for Biobjective Combinatorial Optimization Problems[END_REF][START_REF] Przybylski | Multi-Objective Branch and Bound[END_REF]. The lower bound corresponds to a set of feasible and mutually non-dominated solutions that are weakly dominated by the efficient solutions to the subproblem. The upper bound corresponds to a set of mutually non-dominated objective vectors that weakly dominates the efficient set to the subproblem. Note that the branch and bound algorithm does not require the use of a lower bound since the solutions of a lower bound are eventually visited by the algorithm. However, finding the lower bound solutions earlier and adding them to the archive can improve the anytime performance of the branch and bound and lead to more pruning, which may impact the runtime of the algorithm. This can often outweigh the computational cost of calculating the lower bound and lead to a better runtime.

The subspace division in a branch and bound algorithm is commonly represented as a dynamically generated search tree where each node corresponds to a partial solution, e.g. a solution where some decision variables have been set but not others, and a leaf

MOCO Branch and Bound Framework

Algorithm 1 defines the general framework for branch and bound algorithms for MOCO that we will consider in this work. It describes an eager branch and bound design, meaning that the computation of lower and upper bounds of a node occurs as soon as that node is identified. By contrast, a lazy design only computes the bounds of a node once that node is needed, i.e. when it is selected for processing or when its upper bound is needed for node selection.

In our preliminary experiments, the eager design had generally better runtime and anytime performance, and it also demanded less memory. As such, we choose to discard the lazy design for this work, and note that other approaches in the literature often use an eager design as well [START_REF] Lukata | Solving Multi-Objective Knapsack Problem by a Branch-and-Bound Procedure[END_REF][START_REF] Przybylski | Multi-Objective Branch and Bound[END_REF][START_REF] Visée | Two-Phases Method and Branch and Bound Procedures to Solve the Bi-Objective Knapsack Problem[END_REF]. We remark that 𝑆 in Algorithm 1 corresponds to the archive maintained by the branch and bound algorithm.

Node Selection

Two common strategies for selecting the next node to be explored are the depth-first selection (DFS) [START_REF] Lukata | Solving Multi-Objective Knapsack Problem by a Branch-and-Bound Procedure[END_REF][START_REF] Visée | Two-Phases Method and Branch and Bound Procedures to Solve the Bi-Objective Knapsack Problem[END_REF] and the breadth-first selection (BFS) [START_REF] Visée | Two-Phases Method and Branch and Bound Procedures to Solve the Bi-Objective Knapsack Problem[END_REF] strategies. Both can be trivially implemented within the framework of Algorithm 1 with a Last In First Out (LIFO) queue and a First In First Out (FIFO) queue respectively. We remark, that the BFS approach often suffers from memory issues since it needs to keep a large amount of nodes in memory. On the other hand, the DFS can easily get stuck deep in the tree, exploring solutions that do not improve the quality of the archive significantly. Nonetheless, both approaches can have good performance if the subspace division order leads to optimal, or close to optimal, solutions early on. Unfortunately, such orderings may not be available for every problem or it may not always be clear which order is the best since it can depend on the problem instance being solved [START_REF] Cerqueus | On Branching Heuristics for the Bi-Objective 0/1 Unidimensional Knapsack Problem[END_REF]. A third strategy is the best-first selection (BeFS), which corresponds to finding the most promising node in the queue. In single-objective optimization this could, for example, correspond to finding the node with the highest upper bound, since it suggests that searching in that direction will lead to a solution with a better objective value. A similar idea would be to select the node that may lead to a greater improvement in the quality of the archive. Note that, finding better solutions early, may not only lead to a better anytime performance, but also to an improvement in the overall runtime of the algorithm since other nodes can be pruned sooner.

In this work, we propose an indicator-based branch and bound (I-BB) approach, which considers the use of quality indicators for the BeFS strategy. In our approach, we consider that the "quality" of a node is given by the quality of its upper bound with respect to the archive. To measure this quality we can consider any binary quality indicator that measures the quality of a solution set with respect to another, such as the binary hypervolume indicator and the 𝜀-indicator discussed in Section 2. Formally, given a queue 𝑄 of branch and bound nodes, the archive 𝑆, and assuming a maximizing binary quality indicator 𝐼 (𝐴, 𝐵) → R with 𝐴, 𝐵 ⊂ R 𝑚 that denotes the quality of a set of objective vectors 𝐴 with respect to a solution set 𝐵, we define the selectNode(Q) function for Algorithm 1 by:

selectNode(𝑄) = argmax node ∈𝑄 𝐼 (𝑈 (node), {𝑓 (𝑥) : 𝑥 ∈ 𝑆 }) (7)
where 𝑈 (node) denotes the upper bound of a node. As an example, consider Figure 1 that illustrates the upper bound of two distinct nodes and the calculation of the binary hypervolume indicator for each. We recall that all efficient solutions to the subproblem are weakly dominated by the upper bound. By selecting the node whose upper bound gives the best value of binary hypervolume indicator, in this case the topmost figure, we hope to find a solution that provides a more substantial contribution to the archive.

Unfortunately, the BeFS strategy may also suffer from memory issues like the BFS strategy. Another issue is that if the computation of the binary quality indicator is costly, as is the case for the binary hypervolume indicator with an increasing number of objectives, having a large amount of nodes in the queue can lead to a long selection time. Some implementation details, like caching previously computed values, can help mitigate such issues, but they may not be sufficient. As such, we also consider a Best-Depth-First Selection (BeDFS) strategy, which only evaluates the nodes that are in the deepest level of the search tree.

Other Aspects

There are two other key aspects for the implementation of a branch and bound approach not discussed here: how the solution space is divided, i.e. how branching occurs; and the computation of the bounds. Since defining these aspects heavily depends on the problem being solved, they are discussed in the following section for the considered multi-objective binary knapsack problem.

I-BB FOR MULTI-OBJECTIVE KNAPSACK

To validate our approach we conduct an empirical study on the multi-objective binary knapsack problem. In this section, we describe the problem and instances considered for the study, as well as the branch and bound implementation details for this problem.

Problem

For this study we consider the multi-objective binary knapsack problem, which can be defined as follows:

argmax 𝑥 ∈ {0,1} 𝑛 𝑛 ∑ 𝑖=1 𝑥 𝑖 𝑣 1 𝑖 , . . . , 𝑛 ∑ 𝑖=1 𝑥 𝑖 𝑣 𝑚 𝑖 (8) s.t. 𝑛 ∑ 𝑖=1 𝑥 𝑖 𝑐 𝑖 ≤ 𝐶 ( 9
)
where 𝑛 is the number of items for the knapsack problem, 𝑣 𝑗 𝑖 ∈ Z + denotes the value associated with item 𝑖 ∈ {1, . . . , 𝑛} for objective function 𝑗 ∈ {1, . . . , 𝑚}, 𝑐 𝑖 ∈ Z + denotes the cost of item 𝑖, and 𝐶 ∈ Z + denotes the overall cost constraint.

We consider benchmark instances [START_REF] Bazgan | Solving Efficiently the 0-1 Multi-Objective Knapsack Problem[END_REF] with item values for the objective functions 𝑣 𝑗 𝑖 and item cost values 𝑐 𝑖 randomly generated following a uniform distribution in the range [START_REF] Bader | HypE: An Algorithm for Fast Hypervolume-Based Many-Objective Optimization[END_REF]1000]. Moreover, the cost constraint is set to half of the sum of all the costs, that is:

𝐶 = 1 2 𝑛 ∑ 𝑖=1 𝑐 𝑖 (10)

I-BB Implementation Details

In the following sections we describe the implementation details of the branch and bound algorithm with respect to branching, branching order, bounds computation and selection strategy.

4.2.1

Branching. We consider a dichotomic branching at each node, where the root node corresponds to the empty knapsack, i.e. no decision variable is set. Then, a branching operation corresponds to setting the next unset decision variable to either 0 or 1. Note that there is an exponential number of nodes with respect to the problem size. We also considered a politomic branching that sets the 𝑘 next unset decision variables to 0, and the 𝑘 + 1 unset decision variable to 1. However, our preliminary results showed that it rarely achieved better runtime or anytime performance. As such, we choose to focus on the dichotomic branching.

Branching order.

For the considered branching variants, we need to define the order in which the decision variables are set. One possibility is to consider a random order, which in our empirical analysis is given by the default (random) ordering of the items. Another possibility is to sort the decision variables beforehand according to a given ordering criteria. Importantly, our implementation of the DFS and BFS selection strategies processes first the children whose earlier variables are set to 1. As such, this ordering criterion should order the decision variables such that the first variables are more likely to be set to 1 in efficient solutions. In this work, we consider the rank sum order O sum order [START_REF] Bazgan | Solving Efficiently the 0-1 Multi-Objective Knapsack Problem[END_REF], which is denoted by the increasing order of the sums of the ranks for items 𝑖 = {1, . . . , 𝑛} given by the orders O 𝑗 = 𝑣 𝑗 𝑖 /𝑐 𝑖 for each objective 𝑗 = {1, . . . , 𝑚}. Preliminary results comparing the O sum , O max [START_REF] Bazgan | Solving Efficiently the 0-1 Multi-Objective Knapsack Problem[END_REF], and O min [START_REF] Bazgan | Solving Efficiently the 0-1 Multi-Objective Knapsack Problem[END_REF] orders, showed better anytime behavior for the former. For other possible orders, we refer to [START_REF] Cerqueus | On Branching Heuristics for the Bi-Objective 0/1 Unidimensional Knapsack Problem[END_REF] where various branching orders and heuristics are analyzed.

Lower and upper bound.

In the following we describe the procedure used to compute the lower and upper bounds of a node. Briefly, for a given partial solution we compute a number of feasible extensions that correspond to feasible solutions to the knapsack problem. These feasible extensions are first used to populate the lower bound of a node. Although the lower bound is not required for the branch and bound algorithm, having a diverse lower bound, whose solutions are then added to the archive, can allow the algorithm to prune nodes earlier, which often results in an improved anytime behavior and runtime. Moreover, these feasible extensions are then used to compute the upper bound of a node which is fundamental for branch and bound approaches.

Consider a node whose partial solution is given by 𝑥 such that the first 𝑘 ≤ 𝑛 decision variables are set to either 0 or 1, and the remaining variables have not been set yet. Assume that this partial solution is feasible with respect to the cost constraint, i.e. 𝑘 𝑖=1 𝑥 𝑖 𝑐 𝑖 ≤ 𝐶. Then, an extension for each objective 𝑗 can be obtained by Dantzig's greedy algorithm [START_REF] Dantzig | Discrete-Variable Extremum Problems[END_REF]. In particular, assume that the items from 𝑘 + 1 to 𝑛 are sorted in increasing order of the ratio 𝑣 𝑗 𝑖 /𝑐 𝑖 for an objective 𝑗. Then an extension for that objective function is given by adding all items from 𝑘 + 1 up to, but not including, 𝑏 such that adding item 𝑏 would break the cost constraint. The corresponding objective vector is given by

ℓ 𝑗 = 𝑘 ∑ 𝑖=1 𝑥 𝑖 𝑣 1 𝑖 + 𝑏 ∑ 𝑖=𝑘+1 𝑣 1 𝑖 , . . . , 𝑘 ∑ 𝑖=1 𝑥 𝑖 𝑣 𝑚 𝑖 + 𝑏 ∑ 𝑖=𝑘+1 𝑣 𝑚 𝑖 ( 11
)
In addition, to refine the lower bound with a more balanced tradeoff among the objectives, we consider the extension that is found with Dantzig's greedy algorithm [START_REF] Dantzig | Discrete-Variable Extremum Problems[END_REF] for the items from 𝑘 + 1 to 𝑛 sorted by the ratio (𝑣 1 𝑖 + . . . + 𝑣 𝑚 𝑖 )/𝑐 𝑖 . The objective vector of this extension is denoted by ℓ sum . The topmost illustration in Figure 2 shows the objective vectors ℓ 1 , ℓ 2 , and ℓ sum for two objectives. Since these extensions correspond to feasible solutions to the knapsack problem they are included in the lower bound of the node. Also, since the branching orders considered are fixed, we can precompute all the necessary orders for Dantzig's greedy algorithm.

𝑓 1 𝑓 2 𝑦 𝑙 1 𝑙 2 𝑙 sum 𝑓 1 𝑓 2 𝑢 1 𝑢 2 𝑦 𝑢 Figure 2:
Illustration of the image of the lower bound (top) in the objective space {ℓ 1 , ℓ 2 , ℓ 𝑤 } for a node with partial objective vector 𝑦, and the corresponding upper bound (bottom) given by {𝑢}.

For the upper bound of a node, we consider non-feasible extensions to the ℓ 𝑗 objective vectors. In particular, for each vector ℓ 𝑗 we add the fractional part of the item that violates the constraint, to the 𝑗-th objective value, formally:

𝑢 𝑗 = ℓ 𝑗 𝑗 + 𝐶 𝑗 𝑣 𝑗 𝑏
𝑐 𝑏 [START_REF] Grunert Da Fonseca | Inferential Performance Assessment of Stochastic Optimisers and the Attainment Function[END_REF] where 𝐶 𝑗 is the residual cost of ℓ 𝑗 . An upper bound to the node is then given by the objective vector:

𝑢 = (𝑢 1 , . . . , 𝑢 𝑚 ) (13)
This upper bound is illustrated in Figure 2. A similar upper bound was considered in [START_REF] Lukata | Solving Multi-Objective Knapsack Problem by a Branch-and-Bound Procedure[END_REF].

Selection strategies.

For this study we consider the DFS, BFS, BeFS and BeDFS selection strategies described in Section 3. Moreover, for the latter two we consider two different binary quality indicators: the binary hypervolume indicator, and the 𝜀-indicator described in Section 2.

Since our upper bound is given by a single objective vector 𝑢, the binary hypervolume computation can be formulated as a hypervolume contribution calculation:

𝐻 (𝐴, 𝑢, 𝑟 ) = 𝐻 (𝐴 ∪ {𝑢}, 𝑟 ) -𝐻 (𝐴, 𝑟 ) (14)
For two objectives the hypervolume contribution can be calculated in 𝑂 (log 𝜇), where 𝜇 is the number of solutions in the archive, if the objective vectors of the archive solutions are kept sorted by one of the objective values and data pertaining to the hypervolume calculation with a dimension sweep is kept for each node. For three objectives, it can be calculated in 𝑂 (𝜇) with the HV3D + -U algorithm [START_REF] Andreia | Computing and Updating Hypervolume Contributions in Up to Four Dimensions[END_REF] if the objective vectors of the archive solutions are stored in the data structure of the HV3D + algorithm. For 4 or more objectives, we use the WFG algorithm [START_REF] While | A Fast Way of Calculating Exact Hypervolumes[END_REF], with the sorting and slicing improvements discussed in that work, which computes the hypervolume contribution in 𝑂 (𝜇 𝑚/2 log 𝜇) for 𝑚 objectives.

To compute the 𝜀-indicator we maintain the maximum values for each objective among all solutions in the archive. Then, the 𝜀-indicator for a set with a single objective vector can be found in 𝑂 (𝑚) by dividing the maximum value for each objective by the corresponding value of the objective vector whose quality we are measuring. As such, calculating the 𝜀-indicator is expected to be much faster than calculating the hypervolume contribution, which should be particularly noticeable for a high number of objectives.

Note that the value of the quality indicator for the nodes in the queue can be cached and kept in a priority queue. For a BeFS approach we need to keep a priority queue with all the nodes, whereas for BeDFS we would need a priority queue for each level of the search tree. However, for a dichotomic branching, the BeDFS strategy does not need to keep the values cached since after selecting the best node for a level there is only one node left.

Unfortunately, if the archive maintained by the branch and bound changes, then the cached values may need to be updated, and the priority queue recomputed, which can be detrimental to the performance of the algorithm if it happens frequently. For the BeFS strategy, our preliminary experiments suggest that changes to the maximum objective values were relatively rare. As such, for the 𝜀-indicator BeFS we find it is best to keep the nodes in the priority queue at all times. For the binary hypervolume indicator we see that once the branch and bound reaches a relatively stable state where updates to the archive are rare, then it is worth keeping the items in a priority queue. However, when the archive is being regularly updated, recomputing the priority queue is detrimental to the performance of the algorithm. To balance both scenarios, we build and maintain a priority queue after the algorithm makes 10 consecutive calls to the selection methodology without updating the priority queue. However, if a solution is added to the archive, we discard the priority queue and rely on looping over all values of a vector to find the most promising node. The value 10 was chosen empirically during preliminary testing. Finally, to avoid unnecessary quality indicator computations when a priority queue is not used, we only recompute the quality indicator of the nodes whose previously cached value was better than the current best.

EMPIRICAL STUDY

Our empirical study focuses on comparing the performance of the various selection strategies described in the previous section with regards to two aspects of performance: the runtime of the approach, i.e. the time it takes to identify the efficient set, and its anytime quality, i.e. the quality of the archive at any given time.

To summarize, we consider the following alternatives for the implementation of the branch and bound approaches: The algorithms were implemented in C++20, compiled with GCC 10.2.0, and the experiments were carried out in parallel, one per thread, on a machine with two Intel(R) Xeon(R) Silver 4210R processors. The algorithms had a timeout of 300 seconds and an 8Gb memory limit. The results shown below use instances of sizes 𝑛 ∈ {10, 15, 20, 25, 30, 35, 40, 45, 50, 100, 200}, number of objectives 𝑚 ∈ {2, 3, 5, 7}. For each combination of these parameters 10 instances were independently generated.

Runtime Analysis

Figure 3 shows the results of the average runtime for instances with a varying number of objectives, variables, and branching order. The runtime values are only shown for cases where the algorithms found the efficient set in all 10 generated instances for that particular combination of parameters. The results for two objectives (far left) suggest that the DFS strategy has the worst runtime performance for the default order, and that the BFS and the hypervolume BeFS strategies have the worst runtime performance for the rank sum order. As the number of objectives increases we can see that the runtime performance of the hypervolume BeFS and BeDFS strategies worsens substantially. This is to be expected due to the increasing complexity of the binary hypervolume calculation. We see that the 𝜀-indicator BeFS and BeDFS approaches do not have this issue and that they often show the best, or second best, runtime. It is also worth noting that the runtime for the random order is generally similar to that of the rank sum order, and in fact a better runtime can be observed for some instances with 5 and 7 objectives.

Anytime Analysis

Figure 4 shows the anytime performance traces, with respect to the normalized hypervolume and CPU time, for instances of size 𝑛 = 100 and 2, 3, 5, and 7 objectives. Note that no approach obtained the efficient set for the given time and memory limits. The hypervolume is normalized with respect to the minimum and maximum values computed for each instance during the execution of the branch and bound approaches, such that the minimum hypervolume considered for an instance is given by the hypervolume of the lower bound of the empty knapsack. For 2 objectives, we can see that the I-BB strategies, in particular the hypervolume BeFS strategy, show a very good anytime behavior. Moreover, we can see that for the default (random) order the I-BB strategies generally obtain the best anytime performance. By contrast, for the rank sum order, we see that the DFS strategy shows the overall best anytime performance. However, the results suggest that the I-BB BeFS strategies can surpass the DFS strategy when given enough time, as is the case for 2 and 3 objectives. The performance of the hypervolume based I-BB strategies shows a better anytime performance than the 𝜀-indicator based I-BB strategies for 2 objectives, similar anytime performance for 3 objectives, and worse performance for 5 and 7 objectives. This is consistent with the increased complexity of the binary hypervolume indicator. Note that for 2 and 3 objectives the hypervolume based I-BB approaches for a default order have an anytime performance that is similar to the best anytime performance for a good branching order. For 5 and 7 objectives the results are not as good but still promising. The results were consistent for all tested instances with problem size 𝑛 = 100.

Table 1 shows the ratio of instances for which a given selection strategy had the best anytime quality as given by Equation 6, e.g. a ratio of 0.6 means that for 60% of the tested instances the given approach had the best anytime quality. Note that the I-BB strategies are always the best for the default (random) branching order. For 2 and 3 objectives we see that the hypervolume based I-BB approaches more often have the best anytime quality, whereas for 5 and 7 objectives the 𝜀-indicator based I-BB approaches are better.

Interestingly, the hypervolume based I-BB is capable of achieving a better anytime quality than its 𝜀-indicator counterpart for 5 and 7 objectives when 𝑛 = 200. This suggests that the 𝜀-indicator based I-BB is not suited for increasing the quality of the archive in terms of hypervolume for large problem sizes.

CONCLUSIONS

In this article, we proposed an indicator-based branch and bound (I-BB) approach for multi-objective combinatorial optimization and analyzed it both in terms of runtime and anytime, i.e. heuristic, behavior. Our empirical results showed very promising results in terms of anytime performance, in particular when considering a random ordering of the decision variables. Moreover, the results indicated that the binary hypervolume I-BB had a good anytime performance for a small number of objectives, but that the 𝜀-indicator I-BB showed better performance for a larger number of objectives.

The results also highlighted some weaknesses of the I-BB that are worth investigating in the future. In particular, we note that the I-BB approach cannot always match the anytime behavior of a simple DFS strategy when considering a good branching order, particularly for larger problem sizes. However, a good branching order might not always be available, or may be difficult to design for new problem classes. Nonetheless, we see that the quality of the archive for the I-BB BeDFS strategies tends to quickly improve in the early stages of the search process but then stagnates, whereas for the BeFS strategies the quality is not as good initially but keeps improving throughout the search. As such, one possibility to improve the performance of our I-BB approach could be to consider a hybrid selection strategy that combines both the BeFS and BeDFS strategies. Another possibility would be to consider the use of heuristic approaches to approximately solve some of the subproblems, in particular those where the solutions found are only expected to marginally improve the quality of the solution archive. Moreover, it would be interesting to study different settings in terms of quality indicators and bound definitions. Finally, it would be relevant to study the performance of I-BB for other problem classes, particularly real-world problems, and to compare it against state-of-the-art heuristics, including multi-objective local search and evolutionary algorithms.

𝑓 1 𝑓 2 𝑢 𝑓 1 𝑓 2 𝑢Figure 1 :

 12121 Figure 1: Illustration of the binary hypervolume indicator (in gray) for the upper bound {𝑢} of two distinct nodes.

•

  Branching: Dichotomic; • Branching order: Random (Default) or Rank Sum; • Selection strategy: DFS, BFS, 𝜀-indicator BeFS, 𝜀-indicator BeDFS, Hypervolume BeFS, or Hypervolume BeDFS.

Figure 3 :

 3 Figure3: Runtime averages for varying number of objectives, variables, branching orders, and selection strategies. For each combination, the results are not shown if at least one instance did not finish within the 300 seconds timeout.

Figure 4 :

 4 Figure 4: Anytime performance trace of the branch and bound approaches for instances with varying number of objectives, and problem size 𝑛 = 100.

Algorithm 1 :

 1 Eager branch-and-bound Input : Root node 𝑟 Output : Solution set 𝑆

	9	end
	10	end
	11 end
	12 return 𝑆

1 𝑆 ← getLowerBound(r) 2 𝑄 ← {𝑟 } 3 while 𝑄 ≠ ∅ do 4 node ← selectNode(𝑄) 5 for branch ∈ getBranches(node) do 6 if 𝑆 ≯ getUpperBound(branch) then 7 𝑆 ← 𝑆 ∪ getLowerBound(branch) 8

𝑄 ← 𝑄 ∪ {branch} corresponds to a complete solution. Initially this tree contains only the root node, i.e. the original solution space. A node of the search tree is then processed at each iteration of the branch and bound algorithm. This involves three main tasks: selecting the node to process, computing the bounds, and branching from that node, i.e. further subdividing the solution space if possible.

ACKNOWLEDGMENTS

This work was partially supported by the PICS project MOCO-SEARCH co-funded by the French National Center for Scientific Research (CNRS) and the Portuguese Foundation for Science and Technology (FCT). The first author further acknowledges the FCT for Ph.D. studentship SFRH/BD/132275/2017 co-funded by the European Social Fund and by the State Budget of the Portuguese Ministry of Education and Science. This work was partially funded by national funds through the FCT within the scope of the project CISUC -UID/CEC/00326/2020 and by the European Social Fund, through the Regional Operational Program Centro 2020.

For the rank sum branching order, we see that the DFS strategy often shows the best anytime quality, as expected from the previous results. Still, we see that the I-BB approaches can sometimes have better anytime performance for smaller problem sizes. Further analysis of the instances with problem size 𝑛 = 200, where our I-BB approach was never able to get the best anytime performance, suggests that if given enough time (and memory) the I-BB BeFS approaches would surpass the quality obtained by the DFS strategy.