-
作者：Hadjar, A; Marcotte, O; Soumis, F
作者单位：Universite de Montreal; Polytechnique Montreal; University of Quebec; University of Quebec Montreal
摘要：We consider the multiple depot vehicle scheduling problem (MDVSP) and propose a branch-and-bound algorithm for solving, it that combines column generation, variable fixing, and cutting planes. We show that the solutions of the linear relaxation of the MDVSP contain many odd cycles. We derive a class of valid inequalities by extending the notion of odd cycle and describe a lifting procedure for these inequalities. We prove that the lifted inequalities represent, under certain conditions, facets...
-
作者：Bertsimas, D; Thiele, A
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Lehigh University
摘要：We propose a general methodology based on robust optimization to address the problem of optimally controlling a supply chain subject to stochastic demand in discrete time. This problem has been studied in the past using dynamic programming, which suffers from dimensionality problems and assumes full knowledge of the demand distribution. The proposed approach takes into account the uncertainty of the demand in the supply chain without assuming a specific distribution, while remaining highly tra...
-
作者：Ding, Q; Kouvelis, P; Milner, JM
作者单位：Singapore Management University; Washington University (WUSTL); University of Toronto
摘要：In a multiple-customer-class model of demand fulfillment for a single item, we consider the use of dynamic price discounts to encourage backlogging of demand for customer classes denied immediate service. Customers are assumed to arrive over several stages in a period, and customer classes are distinguished by their contractual price and sensitivity to discounts. Through dynamic programming we determine the optimal discounts to offer, assuming a linear model for the sensitivity of customers to...
-
作者：Babonneau, F; du Merle, O; Vial, JP
作者单位：University of Geneva
摘要：In this paper, we propose to solve the linear multicommodity flow problem using a partial Lagrangian relaxation. The relaxation is restricted to the set of arcs that are likely to be saturated at the optimum. This set is itself approximated by an active set strategy. The partial Lagrangian dual is solved with Proximal-ACCPM, a variant of the analytic center cutting-plane method. The new approach makes it possible to solve huge problems when few arcs are saturated at the optimum, as appears to ...
