Iterated local search

Iterated Local Search has many of the desirable features of a metaheuristic: it is simple, easy to implement, robust, and highly effective. The essential idea of Iterated Local Search lies in focusing the search not on the full space of solutions but on a smaller subspace defined by the solutions that are locally optimal for a given optimization engine. The success of Iterated Local Search lies in the biased sampling of this set of local optima. How effective this approach turns out to be depends mainly on the choice of the local search, the perturbations, and the acceptance criterion. So far, in spite of its conceptual simplicity, it has lead to a number of state-of-the-art results without the use of too much problem-specific knowledge. But with further work so that the different modules are well adapted to the problem at hand, Iterated Local Search can often become a competitive or even state of the artalgorithm. The purpose of this review is both to give a detailed description of this metaheuristic and to show where it stands in terms of performance.

Beyond Smith's rule: An optimal dynamic index, rule for single machine stochastic scheduling with convex holding costs

Most research on single machine scheduling has assumedthe linearity of job holding costs, which is arguablynot appropriate in some applications. This motivates ourstudy of a model for scheduling $n$ classes of stochasticjobs on a single machine, with the objective of minimizingthe total expected holding cost (discounted or undiscounted). We allow general holding cost rates that are separable,nondecreasing and convex on the number of jobs in eachclass. We formulate the problem as a linear program overa certain greedoid polytope, and establish that it issolved optimally by a dynamic (priority) index rule,whichextends the classical Smith's rule (1956) for the linearcase. Unlike Smith's indices, defined for each class, ournew indices are defined for each extended class, consistingof a class and a number of jobs in that class, and yieldan optimal dynamic index rule: work at each time on a jobwhose current extended class has larger index. We furthershow that the indices possess a decomposition property,as they are computed separately for each class, andinterpret them in economic terms as marginal expected cost rate reductions per unit of expected processing time.We establish the results by deploying a methodology recentlyintroduced by us [J. Niño-Mora (1999). "Restless bandits,partial conservation laws, and indexability. "Forthcomingin Advances in Applied Probability Vol. 33 No. 1, 2001],based on the satisfaction by performance measures of partialconservation laws (PCL) (which extend the generalizedconservation laws of Bertsimas and Niño-Mora (1996)):PCL provide a polyhedral framework for establishing theoptimality of index policies with special structure inscheduling problems under admissible objectives, which weapply to the model of concern.

Forced diuresis improves the diagnostic accuracy of 18F-FDG PET in abdominopelvic malignancies.

Our aim was to evaluate the role of forced diuresis in improving the diagnostic accuracy of abdominopelvic (18)F-FDG PET. METHODS: Thirty-two patients were enrolled. Besides the presence of known intravesical tumors or undefined renal lesions on the initial PET scan, the inclusion criterion was the appearance of indeterminate or equivocal (18)F-FDG foci that extended along the course of the urinary tract and could not confidently be separated from urinary activity. For each patient, a second abdominopelvic PET study was performed after intravenous injection of 0.5 mg of furosemide per kilogram of body weight (maximum, 40 mg) coupled with parenteral infusion of physiologic saline. RESULTS: Forced diuresis coupled with parenteral hydration eliminated any significant (18)F-FDG activity from the lower urinary tract in 31 (97%) of 32 patients after the bladder had been voided 3 successive times. Twelve intravesical lesions were visualized with outstanding clarity, whereas radiologic suspicion of locally recurrent bladder tumors was ruled out in 3 patients. Among 14 indeterminate or equivocal extravesical foci, 7 were deemed of no clinical value because they disappeared after furosemide challenge, whereas 7 persisting foci were proven to be true-positive PET findings. The performance of (18)F-FDG PET in characterizing 3 renal-space-occupying lesions could not be improved by our protocol. CONCLUSION: Furosemide challenge has the potential to noninvasively resolve the inherent (18)F-FDG contrast handicap in the lower urinary tract.

An European Organisation for Research and Treatment of Cancer phase I study of lapatinib and docetaxel as neoadjuvant treatment for Human Epidermal Growth Factor Receptor 2 (HER2) positive locally-advanced/inflammatory or large operable breast cancer.

BACKGROUND: Lapatinib is an effective anti-HER2 therapy in advanced breast cancer and docetaxel is one of the most active agents in breast cancer. Combining these agents in pre-treated patients with metastatic disease had previously proved challenging, so the primary objective of this study aimed to determine the maximum tolerated dose (MTD) in treatment-naive patients, by identifying acute dose-limiting toxicities (DLT) during cycle 1 in the first part of a phases 1-2 neoadjuvant European Organisation for Research and Treatment of Cancer (EORTC) trial. PATIENTS AND METHODS: Patients with large operable or locally-advanced HER2 positive breast cancer were treated with continuous lapatinib, and docetaxel every 21days for 4 cycles. Dose levels (DLs) were: 1000/75, 1250/75, 1000/85, 1250/85, 1000/100 and 1250/100 (mg/day)/(mg/m(2)). RESULTS: Twenty-one patients were included. Two DLTs occurred at dose level 5 (1000/100); one grade 4 neutropenia ⩾7days and one febrile neutropenia. A further 3 patients were therefore treated at the same dose with prophylactic granulocyte-colony stimulating factor (G-CSF), and 3 patients at dose level 6. No further DLTs were observed. CONCLUSIONS: Our recommended dose for phase II is lapatinib 1000mg/day and docetaxel 100mg/m(2) with G-CSF in HER2 positive non-metastatic breast cancer. The dose of lapatinib should have been 1250mg/day but we were mindful of the high rate of treatment discontinuation in GeparQuinto with lapatinib 1250mg/day combined with docetaxel. No grade 3-4 diarrhoea was observed. Pharmacodynamics analysis suggests that concomitant medications altering P-glycoprotein activity (in addition to lapatinib) can modify toxicity, including non-haematological toxicities. This needs verification in larger trials, where it may contribute to understanding the sources of variability in clinical toxicity and treatment discontinuation.

New ideas need new space

We develop a setting with weak intellectual property rights, where firms' boundaries, location and knowledge spillovers are endogenous. We have two main results. The first one is that, if communication costs increase with distance, entrepreneurs concerned about information leakage have a benefit from locating away from the industry center: distance is an obstacle to collusive trades between members andnon-members. The second result is that we identify a trade-off for the entrepreneur between owning a facility (controlling all its characteristics) and sharing a facility with a {\it non-member} (an agent not involved in production), therefore losing control over some of its characteristics. We focus on ``location" as the relevant characteristic of the facility, but location can be used as a spatial metaphor for other relevant characteristics of the facility. For theentrepreneur, sharing the facility with non-members implies that the latter, as co-owners, know the location (even if they do not have access to it). Knowledge of the location for the co-owners facilitates collusion with employees, what increases leakage. The model yields a benefit for new plants from spatial dispersion (locating at the periphery of the industry), particularly so for new plants of new firms.We relate this result with recent empirical findings on the dynamics of industry location.

A dynamic choice model of hybrid behavior in the attribute-space

This paper presents a dynamic choice model in the attributespace considering rational consumers that discount the future. In lightof the evidence of several state-dependence patterns, the model isfurther extended by considering a utility function that allows for thedifferent types of behavior described in the literature: pure inertia,pure variety seeking and hybrid. The model presents a stationaryconsumption pattern that can be inertial, where the consumer only buysone product, or a variety-seeking one, where the consumer buys severalproducts simultane-ously. Under the inverted-U marginal utilityassumption, the consumer behaves inertial among the existing brands forseveral periods, and eventually, once the stationary levels areapproached, the consumer turns to a variety-seeking behavior. An empiricalanalysis is run using a scanner database for fabric softener andsignificant evidence of hybrid behavior for most attributes is found,which supports the functional form considered in the theory.

Hybrid consumption paths in the attribute space: A model and application with scanner data

This paper presents and estimates a dynamic choice model in the attribute space considering rational consumers. In light of the evidence of several state-dependence patterns, the standard attribute-based model is extended by considering a general utility function where pure inertia and pure variety-seeking behaviors can be explained in the model as particular linear cases. The dynamics of the model are fully characterized by standard dynamic programming techniques. The model presents a stationary consumption pattern that can be inertial, where the consumer only buys one product, or a variety-seeking one, where the consumer shifts among varied products.We run some simulations to analyze the consumption paths out of the steady state. Underthe hybrid utility assumption, the consumer behaves inertially among the unfamiliar brandsfor several periods, eventually switching to a variety-seeking behavior when the stationary levels are approached. An empirical analysis is run using scanner databases for three different product categories: fabric softener, saltine cracker, and catsup. Non-linear specifications provide the best fit of the data, as hybrid functional forms are found in all the product categories for most attributes and segments. These results reveal the statistical superiority of the non-linear structure and confirm the gradual trend to seek variety as the level of familiarity with the purchased items increases.

Concomitant Cisplatin and Hyperfractionated Radiotherapy in Locally Advanced Head and Neck Cancer: Ten-year Follow-up of a Randomized Phase III Trial (SAKK 10/94)

Purpose/Objective(s): To analyze the long-term outcome of treatment with concomitant cisplatin and hyperfractionated radiotherapy in locally advanced head and neck cancer compared with hyperfractionated radiotherapy alone.Materials/Methods: From July 1994 to July 2000 a total of 224 patients with squamous cell carcinoma of the head and neck were randomized to either hyperfractionated radiotherapy (median dose 74.4 Gy; 1.2 Gy twice daily) or the same radiotherapy combined with two cycles of concomitant cisplatin (20mg/m2 for 5 consecutive days of weeks 1 and 5). The primary endpoint was time to any treatment failure; secondary endpoints were locoregional failure, metastatic failure, overall survival, and late toxicity assessed according to RTOG criteria. The trial was registered at the National Institutes of Health (www.clinicaltrials.gov; identifier number: NCT00002654).Results: Median follow-up was 9.5 years (range, 0.1 - 15.4 years). Median time to any treatment failure was not significantly different between treatment arms (p = 0.19). Locoregional control (p\0.05), distant metastasis-free survival (p = 0.02) and cancer specific survival (p = 0.03) were significantly improved in the combined treatment arm, with no difference in late toxicity between treatment arms. However, overall survival was not significantly different (p = 0.19). Conclusions: After long-term follow-up combined treatment with cisplatin and hyperfractionated, radiotherapy maintained an improved locoregional control, distant metastasis-free survival, and cancer specific survival as compared to hyperfractionated radiotherapy alone with no difference in late toxicity.Author Disclosure: P. Ghadjar, None; M. Simcock, None; G. Studer, None; A.S. Allal, None; M. Ozsahin, None; J. Bernier, None; M. To¨ pfer, None; F. Zimmermann, None; C. Glanzmann, None; D.M. Aebersold, None.