A randomized concave programming method for choice network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing froman offer set, have recently become popular in assortment optimization and revenue management.The dynamic program for these models is intractable and approximated by a deterministiclinear program called the CDLP which has an exponential number of columns. However, whenthe segment consideration sets overlap, the CDLP is difficult to solve. Column generationhas been proposed but finding an entering column has been shown to be NP-hard. In thispaper we propose a new approach called SDCP to solving CDLP based on segments and theirconsideration sets. SDCP is a relaxation of CDLP and hence forms a looser upper bound onthe dynamic program but coincides with CDLP for the case of non-overlapping segments. Ifthe number of elements in a consideration set for a segment is not very large (SDCP) can beapplied to any discrete-choice model of consumer behavior. We tighten the SDCP bound by(i) simulations, called the randomized concave programming (RCP) method, and (ii) by addingcuts to a recent compact formulation of the problem for a latent multinomial-choice model ofdemand (SBLP+). This latter approach turns out to be very effective, essentially obtainingCDLP value, and excellent revenue performance in simulations, even for overlapping segments.By formulating the problem as a separation problem, we give insight into why CDLP is easyfor the MNL with non-overlapping considerations sets and why generalizations of MNL posedifficulties. We perform numerical simulations to determine the revenue performance of all themethods on reference data sets in the literature.

A tractable consideration set structure for network revenue management

Models incorporating more realistic models of customer behavior, as customers choosing from an offerset, have recently become popular in assortment optimization and revenue management. The dynamicprogram for these models is intractable and approximated by a deterministic linear program called theCDLP which has an exponential number of columns. When there are products that are being consideredfor purchase by more than one customer segment, CDLP is difficult to solve since column generationis known to be NP-hard. However, recent research indicates that a formulation based on segments withcuts imposing consistency (SDCP+) is tractable and approximates the CDLP value very closely. In thispaper we investigate the structure of the consideration sets that make the two formulations exactly equal.We show that if the segment consideration sets follow a tree structure, CDLP = SDCP+. We give acounterexample to show that cycles can induce a gap between the CDLP and the SDCP+ relaxation.We derive two classes of valid inequalities called flow and synchronization inequalities to further improve(SDCP+), based on cycles in the consideration set structure. We give a numeric study showing theperformance of these cycle-based cuts.

A new compact linear programming formulation for choice network revenue management

The choice network revenue management model incorporates customer purchase behavioras a function of the offered products, and is the appropriate model for airline and hotel networkrevenue management, dynamic sales of bundles, and dynamic assortment optimization.The optimization problem is a stochastic dynamic program and is intractable. A certainty-equivalencerelaxation of the dynamic program, called the choice deterministic linear program(CDLP) is usually used to generate dyamic controls. Recently, a compact linear programmingformulation of this linear program was given for the multi-segment multinomial-logit (MNL)model of customer choice with non-overlapping consideration sets. Our objective is to obtaina tighter bound than this formulation while retaining the appealing properties of a compactlinear programming representation. To this end, it is natural to consider the affine relaxationof the dynamic program. We first show that the affine relaxation is NP-complete even for asingle-segment MNL model. Nevertheless, by analyzing the affine relaxation we derive a newcompact linear program that approximates the dynamic programming value function betterthan CDLP, provably between the CDLP value and the affine relaxation, and often comingclose to the latter in our numerical experiments. When the segment consideration sets overlap,we show that some strong equalities called product cuts developed for the CDLP remain validfor our new formulation. Finally we perform extensive numerical comparisons on the variousbounds to evaluate their performance.

Posterior quadrantic epilepsy surgery: technical variants, surgical anatomy, and case series.

OBJECTIVE: Patients with intractable epilepsy due to extensive lesions involving the posterior quadrant (temporal, parietal, and occipital lobes) form a small subset of epilepsy surgery. This study was done with a view to analyze our experience with this group of patients and to define the changes in the surgical technique over the last 15 years. We also describe the microsurgical technique of the different surgical variants used, along with their functional neuroanatomy. METHODS: In this series there were 13 patients with a median age of 17 years. All patients had extensive presurgical evaluation that provided concordant evidence localizing the lesion and seizure focus to the posterior quadrant. The objective of the surgery was to eliminate the effect of the epileptogenic tissue and preserve motor and sensory functions. RESULTS: During the course of this study period of 15 years, the surgical procedure performed evolved toward incorporating more techniques of disconnection and minimizing resection. Three technical variants were thus utilized in this series, namely, (i) anatomical posterior quadrantectomy (APQ), (ii) functional posterior quadrantectomy (FPQ), and (iii) periinsular posterior quadrantectomy (PIPQ). After a median follow-up period of 6 years, 12/13 patients had Engel's Class I seizure outcome. CONCLUSION: The results of surgery for posterior quadrantic epilepsy have yielded excellent seizure outcomes in 92% of the patients in the series with no mortality or major morbidity. The incorporation of disconnective techniques in multilobar surgery has maintained the excellent results obtained earlier with resective surgery.

On bounds for network revenue management

The Network Revenue Management problem can be formulated as a stochastic dynamic programming problem (DP or the\optimal" solution V *) whose exact solution is computationally intractable. Consequently, a number of heuristics have been proposed in the literature, the most popular of which are the deterministic linear programming (DLP) model, and a simulation based method, the randomized linear programming (RLP) model. Both methods give upper bounds on the optimal solution value (DLP and PHLP respectively). These bounds are used to provide control values that can be used in practice to make accept/deny decisions for booking requests. Recently Adelman [1] and Topaloglu [18] have proposed alternate upper bounds, the affine relaxation (AR) bound and the Lagrangian relaxation (LR) bound respectively, and showed that their bounds are tighter than the DLP bound. Tight bounds are of great interest as it appears from empirical studies and practical experience that models that give tighter bounds also lead to better controls (better in the sense that they lead to more revenue). In this paper we give tightened versions of three bounds, calling themsAR (strong Affine Relaxation), sLR (strong Lagrangian Relaxation) and sPHLP (strong Perfect Hindsight LP), and show relations between them. Speciffically, we show that the sPHLP bound is tighter than sLR bound and sAR bound is tighter than the LR bound. The techniques for deriving the sLR and sPHLP bounds can potentially be applied to other instances of weakly-coupled dynamic programming.

An enhanced concave program relaxation for choice network revenue management

The network choice revenue management problem models customers as choosing from an offer-set, andthe firm decides the best subset to offer at any given moment to maximize expected revenue. The resultingdynamic program for the firm is intractable and approximated by a deterministic linear programcalled the CDLP which has an exponential number of columns. However, under the choice-set paradigmwhen the segment consideration sets overlap, the CDLP is difficult to solve. Column generation has beenproposed but finding an entering column has been shown to be NP-hard. In this paper, starting with aconcave program formulation based on segment-level consideration sets called SDCP, we add a class ofconstraints called product constraints, that project onto subsets of intersections. In addition we proposea natural direct tightening of the SDCP called ?SDCP, and compare the performance of both methodson the benchmark data sets in the literature. Both the product constraints and the ?SDCP method arevery simple and easy to implement and are applicable to the case of overlapping segment considerationsets. In our computational testing on the benchmark data sets in the literature, SDCP with productconstraints achieves the CDLP value at a fraction of the CPU time taken by column generation and webelieve is a very promising approach for quickly approximating CDLP when segment consideration setsoverlap and the consideration sets themselves are relatively small.

Previous microvascular decompression decreases the chances of pain free in patients treated with Gamma Knife radiosurgery for TIC

Object: The authors sought to establish whether the safety-efficacy of Gamma Knife radiosurgery (GKRS) as a second treatment for intractable trigeminal neuralgia (ITN) are influenced by prior microvascular decompression (MVD) which remains, for some of the authors, the reference technique. Methods: Between July 1992 and November 2010, 737 patients have been operated with GKRS for ITN and prospectively evaluated in Timone University Hospital in Marseille, France. Among these, 54 patients had a previous MVD history. Radiosurgery using a Gamma Knife (model B or C or Perfexion) was performed relying on both MR and CT targeting. A single 4 mm isocenter was positioned in the cisternal portion of the trigeminal nerve at a median distance of 7.6 mm (range 3.9- 11.9) anteriorly to the emergence of the nerve (retrogasserian target). A median maximum dose of 85 Gy (range 70-90) was delivered. Are further analyzed only 45 patients with previous MVD and a follow-up longer than one year (the patients with megadolichobasilar artery compression and multiple sclerosis were excluded). Results: The median age in this series was 56.75 years (range 28.09-82.39). The median follow-up period was 39.48 months (range 14.10-144.65). All the patients had a past history of surgery, with at least one previous failed MVD, but also a radiofrequency lesion (RFL) in 16 (35.6%) patients, balloon microcompression in 7 (15.6%) patients and glycerol rhizotomy in 1 case (2.2%). Thirty-five patients (77.8%) were initially pain free in a median time of 14 days (range 0, 180). Patients from this group had less probability of being pain free compared to our global population of essential trigeminal neuralgia without previous MVD history (p=0.010, hazard ratio of 0.64). Their probability of remaining pain free at 3, 5, 7 and 10 years was 66.5%, 59.1%, 59.1% and 44.3%, respectively. Twelve patients (34.3%) initially pain free experienced a recurrence with a median delay of 31.21 months (range 3.40-89.93). The hypoesthesia actuarial rate at 1 year was 9.1% and remained stable till 12 years with a median delay of onset of 8 months (range 8-8). Conclusions: Retrogasserian GKRS proofed to be safe and effective on the long-term basis even after failed previous MVD. Even if the initial result of pain free was of only 77.8%, the toxicity was low with only 9.1% hypoesthesia. No patient reported a bothersome hypoesthesia. The probability of maintaining pain relief in long-term was of 44.3% at 10 years.

On the complexity of rationalizing behavior

We study the complexity of rationalizing choice behavior. We do so by analyzing two polar cases, and a number of intermediate ones. In our most structured case, that is where choice behavior is defined in universal choice domains and satisfies the "weak axiom of revealed preference," finding the complete preorder rationalizing choice behavior is a simple matter. In the polar case, where no restriction whatsoever is imposed, either on choice behavior or on choice domain, finding the complete preordersthat rationalize behavior turns out to be intractable. We show that the task of finding the rationalizing complete preorders is equivalent to a graph problem. This allows the search for existing algorithms in the graph theory literature, for the rationalization of choice.

Lumboperitoneal shunting for pseudotumor cerebri.

To clarify the appropriate role of lumboperitoneal (LP) shunting in the surgical management of pseudotumor cerebri (PTC), we retrospectively analyzed the clinical data from 30 patients who underwent this procedure. We found LP shunting to be an effective means of acutely lowering intracranial pressure. Symptoms of increased intracranial pressure improved in 82% of patients. Among 14 eyes with impaired visual acuity, 10 (71%) improved by at least two lines. Worsening of vision occurred in only one eye. Of 28 eyes with abnormal Goldmann perimetry, 18 (64%) improved and none worsened. The incidence of serious complications was low. The major drawback of LP shunting was the need for frequent revisions in a few patients. The reason for poor shunt tolerance in certain individuals is unclear. In PTC, LP shunting should be considered as the first surgical procedure for patients with severe visual loss at presentation or with intractable headache (with or without visual loss). After shunting it is important to identify patients who are shunt intolerant.

Prenatal brain atrophy due to a giant vein of Galen malformation.

We report a full-term newborn girl with a giant vein of Galen malformation and extreme cerebral atrophy of prenatal origin. She presented on the 3rd day of life with intractable congestive heart failure. The diagnosis of the vascular malformation was confirmed by ultrasound and magnetic resonance imaging.

Céphalées pharmacorésistantes: nouvelles approches du casse-tête [Drug-resistant headache: is it the end?].

Chronic primary headache often cause significant interference with function and quality of life despite acute and preventive medicines. New treatments are emerging for pharmacologically intractable cluster headache and migraine. Occipital nerve stimulation in chronic cluster headache and botulinum toxin in chronic migraine represent the most promising therapies.

Intrathecal administration of Ziconotide: does single-shot injection predict efficacy?

Introduction: Though a trial of intrathecal (IT) therapy should always be performed before implantation of a definitive intrathecal pump, there is no agreement as to how this test should be performed. Ziconotide is trialed in most of cases with continuous IT administration using implanted catheters. Unlike other intrathecal drugs, there is little experience with single bolus IT injections of ziconotide. The aim of the study is to assess the feasibility of single-shot IT trialing with ziconotide. Patients and methods: Eleven consecutive patients with chronic neuropathic intractable pain were trialed with a single IT bolus of 2.5 mcg of ziconotide. Pain and side effects are monitored for at least 72 hours after the injection. Depending on the response, a second injection is given a week later, with either the same dose (if VAS decreased ≥50% without side effects), a higher dose of 3.75 mcg (if VAS decreased <50% without side effects) or a lower dose of 1.25 mcg (if VAS decreased ≥50% but with side effects). If VAS decreased less than 50% and side effects occurred, no further injection was performed. When VAS decreased >50% without side effects after the first or the second dose, the result is confirmed by one more injection of the same dose one week later. The trial is considered positive if two successive injections provide a VAS decreased more than 50% without side effects. Results: Eleven patients (6 females and 5 males) were included. Nine patients experienced modest or no pain relief. Four of these had significant side effects (dizziness, nausea, vomiting or abdominal pain) and had no further injection. In the others 5, one patient retired from study and four received a second injection of 3.75 mcg. The trial was negative in all 5 cases because of side effects (dizziness, drowsiness, weakness, muscle cramps), the pain decreased in only 2 patients. Two patients experienced profound pain relief with an IT injection of 2.5 mcg. One patient had no side effects and the other had dizziness and drowsiness that disappeared with an injection of 1.25 mcg. Pain relief without adverse effects was confirmed with the second injection. The trial was considered positive for those two patients. Discussion and conclusion: The response rate of 18% (2/11) is consistent with the success rate of a continuous infusion trialing with an implanted catheter. Single-shot injection of ziconotide may therefore predict efficacy.

Intrathecal drug delivery systems for cancer pain

Introduction: A substantial number of patients with cancer suffer considerable pain at some point during their disease, and approximately 25% of cancer patients die in pain. In cases of uncontrolled pain or intolerable side effects, intrathecal drug delivery system (IDDS) is a recognised management option. Indeed, IDDS offer rapid and effective pain relief with less drug side effects compared to oral or parenteral administration. The aim of this study is to retrospectively review our series of cancer patients treated with IDDS. Method: Data was extracted from the institutional neuromodulation registry. Patients with cancer pain treated with IDDS from 01.01.1997 to 30.12.2009 were analysed for subjective improvement, changes in pain intensity (VAS) and survival time after implantation. Measurements were available for a decreasing number of patients as time since baseline increased. Results: During the studied period, 78 patients were implanted with IDDS for cancer pain. The mean survival time was 11.1 months (median: 3.8 months) and 14 patients (18%) were still alive at the end of the studied period. Subjective improvement was graded between 55 and 83% during the first year. Mean VAS during the first year remained lower than VAS at baseline. Discussion: IDDS has been shown to be cost-effective in several studies. Although initial costs of implantation are high, the cost benefits favour analgesia with implanted intrathecal pumps over epidural external systems after 3 to 6 months in cancer patients. Improved survival has been associated with IDDS and in this series both the mean and median survival times were above the cut-off value of three months. The mean subjective improvement was above 50% during the whole first year, suggesting a good efficacy of the treatment, a finding that is consistent with the results from other groups. Changes in pain intensity are difficult to interpret in the context of rapidly progressive disease such as in terminal cancer. However, mean VAS from 1 thru12 months were lower than baseline, suggesting improved pain control with IDDS, or at least a stabilisation of the pain symptoms. Conclusion: Our retrospective series suggests IDDS is effective in intractable cancer pain and we believe it should be considered even in terminally ill patients with limited life expectancies.

ABCtoolbox: a versatile toolkit for approximate Bayesian computations.

BACKGROUND: The estimation of demographic parameters from genetic data often requires the computation of likelihoods. However, the likelihood function is computationally intractable for many realistic evolutionary models, and the use of Bayesian inference has therefore been limited to very simple models. The situation changed recently with the advent of Approximate Bayesian Computation (ABC) algorithms allowing one to obtain parameter posterior distributions based on simulations not requiring likelihood computations. RESULTS: Here we present ABCtoolbox, a series of open source programs to perform Approximate Bayesian Computations (ABC). It implements various ABC algorithms including rejection sampling, MCMC without likelihood, a Particle-based sampler and ABC-GLM. ABCtoolbox is bundled with, but not limited to, a program that allows parameter inference in a population genetics context and the simultaneous use of different types of markers with different ploidy levels. In addition, ABCtoolbox can also interact with most simulation and summary statistics computation programs. The usability of the ABCtoolbox is demonstrated by inferring the evolutionary history of two evolutionary lineages of Microtus arvalis. Using nuclear microsatellites and mitochondrial sequence data in the same estimation procedure enabled us to infer sex-specific population sizes and migration rates and to find that males show smaller population sizes but much higher levels of migration than females. CONCLUSION: ABCtoolbox allows a user to perform all the necessary steps of a full ABC analysis, from parameter sampling from prior distributions, data simulations, computation of summary statistics, estimation of posterior distributions, model choice, validation of the estimation procedure, and visualization of the results.

Indications, perspectives et limites de la stimulation électrique épidurale en cas d'artériopathie périphérique ou coronarienne [Indications, limits and future of epidural spinal cord electrical stimulation for coronary and peripheral artery disease]

The electrical stimulation of the dorsal columns of the spinal cord exerts a dual analgesic and vasodilatory effect on ischemic tissues. It is increasingly considered a valuable method to treat severe and otherwise intractable coronary and peripheral artery disease. The quality of the results depends from both a strict selection of the patients by vascular specialists and the frequency and quality of the follow-up controls. However the indications, limits, mode of action and results of spinal cord stimulation are still poorly understood. This article, based on a personal experience of 164 implantations for peripheral and coronary artery disease, aims to draw attention to this technique and to provide information on recent and future developments.