Robust discrete optimization and network flows

From MaRDI portal
Publication:1424278

DOI10.1007/s10107-003-0396-4zbMath1082.90067OpenAlexW2165775468WikidataQ61603113 ScholiaQ61603113MaRDI QIDQ1424278

Melvyn Sim, Dimitris J. Bertsimas

Publication date: 11 March 2004

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-003-0396-4




Related Items

Optimal path problems with second-order stochastic dominance constraintsRobust approach to restricted items selection problemOnline makespan minimization with budgeted uncertaintySingle-commodity robust network design with finite and hose demand setsEvacuation transportation planning under uncertainty: A robust optimization approachRobust and reliable forward-reverse logistics network design under demand uncertainty and facility disruptionsRobust combinatorial optimization with variable cost uncertaintyRobust optimization for interactive multiobjective programming with imprecise information applied to R\&D project portfolio selectionApproximate robust optimization for the connected facility location problemLot sizing with storage losses under demand uncertaintyOn robust maximum flow with polyhedral uncertainty setsPolynomial-time identification of robust network flows under uncertain arc failuresAlgorithms and uncertainty sets for data-driven robust shortest path problemsA VNS-LP algorithm for the robust dynamic maximal covering location problemOn the value of exposure and secrecy of defense system: first-mover advantage vs. robustnessHybrid robust and stochastic optimization for closed-loop supply chain network design using accelerated Benders decompositionBiobjective robust optimization over the efficient set for Pareto set reductionAdjustable robustness for multi-attribute project portfolio selectionMin-max-min robustness: a new approach to combinatorial optimization under uncertainty based on multiple solutionsPiecewise static policies for two-stage adjustable robust linear optimizationExact solution of the robust knapsack problemA trilevel programming approach for electric grid defense planningThe robust knapsack problem with queriesNetwork design in scarce data environment using moment-based distributionally robust optimizationA capacitated hub location problem under hose demand uncertaintyA decomposition based solution algorithm for U-type assembly line balancing with interval dataRobust optimization: lessons learned from aircraft routingDistributionally robust fixed interval scheduling on parallel identical machines under uncertain finishing timesA framework for secure IT operations in an uncertain and changing environmentBenders decomposition applied to a robust multiple allocation incomplete hub location problemThe robust (minmax regret) assembly line worker assignment and balancing problemRobust vehicle routing problem with hard time windows under demand and travel time uncertaintyA robust optimisation model and cutting planes for the planning of energy-efficient wireless networksRobust flows with losses and improvability in evacuation planningRobust energy-aware routing with redundancy eliminationA two-stage robust optimization approach for the mobile facility fleet sizing and routing problem under uncertaintyA stochastic algorithm for online bipartite resource allocation problemsStochastic semidefinite programming: a new paradigm for stochastic optimizationRobust combinatorial optimization with knapsack uncertaintyRobust delay-constrained routing in telecommunicationsApplication of robust optimization to automated test assemblyOn discrete optimization with orderingNew models for the robust shortest path problem: complexity, resolution and generalizationOSPF routing with optimal oblivious performance ratio under polyhedral demand uncertaintyA robust optimization approach to dispatching technicians under stochastic service timesRevisiting \(k\)-sum optimizationRestricted robust uniform matroid maximization under interval uncertaintySolving the robust two-stage capacitated facility location problem with uncertain transportation costsOn recoverable and two-stage robust selection problems with budgeted uncertaintyRobust goal programming using different robustness echelons via norm-based and ellipsoidal uncertainty setsA robust multi-trip vehicle routing problem of perishable products with intermediate depots and time windowsRisk models for the prize collecting Steiner tree problems with interval dataThe minmax regret gradual covering location problem on a network with incomplete information of demand weightsDeterministic risk control for cost-effective network connectionsTwo-stage minimax regret robust uncapacitated lot-sizing problems with demand uncertaintySupply chain network design under uncertainty: a comprehensive review and future research directionsOn 2-stage robust LP with RHS uncertainty: complexity results and applicationsCooperative maximum-flow problem under uncertainty in logistic networksA robust mean absolute deviation model for portfolio optimizationMinmax regret bottleneck problems with solution-induced interval uncertainty structurePossibilistic bottleneck combinatorial optimization problems with ill-known weightsReal-time management of berth allocation with stochastic arrival and handling timesRobust optimization of graph partitioning involving interval uncertaintyMin-ordering and max-ordering scalarization methods for multi-objective robust optimizationApplication of robust optimization to the Sawmill planning problemRisk-control approach for bottleneck transportation problem with randomness and fuzzinessCombinatorial optimization problems with uncertain costs and the OWA criterionAlmost robust discrete optimizationA decomposition approach for commodity pickup and delivery with time-windows under uncertaintyRobust combinatorial optimization under convex and discrete cost uncertaintyRobust balanced optimizationConstrained shortest path with uncertain transit timesRobust location transportation problems under uncertain demandsThreshold robustness in discrete facility location problems: a bi-objective approachMin-max regret robust optimization approach on interval data uncertaintyRobust optimization model for uncertain multiobjective linear programsPolymatroids and mean-risk minimization in discrete optimizationA robust approach to the chance-constrained knapsack problemMin-max-min robust combinatorial optimizationRecoverable robust knapsacks: the discrete scenario caseTwo-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hardAn \(s\)-\(t\) connection problem with adaptabilityRobust network optimization under polyhedral demand uncertainty is \(NP\)-hardRapidly computing robust minimum capacity s-t cuts: a case study in solving a sequence of maximum flow problemsLinear programming models for traffic engineering in 100\% survivable networks under combined IS-IS/OSPF and MPLS-TERobust optimization with simulated annealingRobust resource allocations in temporal networksTractable stochastic analysis in high dimensions via robust optimizationMulti-objective minmax robust combinatorial optimization with cardinality-constrained uncertaintySelected topics in robust convex optimizationSpeeding up column generation for robust wireless network planningOn the one-commodity pickup-and-delivery traveling salesman problem with stochastic demandsMin-max and min-max regret versions of combinatorial optimization problems: A surveyComputing and minimizing the relative regret in combinatorial optimization with interval dataRelaxed robust second-order-cone programmingA note on robustness tolerances for combinatorial optimization problemsRobust optimization - a comprehensive surveyRobustness in operational research and decision aiding: a multi-faceted issueInteger-programming software systemsSolving planning and design problems in the process industry using mixed integer and global optimizationOptimal multi-state partnerships for woody biomass co-firing incorporating a demand-response function for biomass procurementTwo-stage robust optimization problems with two-stage uncertaintyStability factor for robust balancing of simple assembly lines under uncertaintyOn the motion of substance in a channel of a network and human migrationDiscrete-time model for a motion of substance in a channel of a network with application to channels of human migrationStrategic bidding in price coupled regionsRecoverable robust representatives selection problems with discrete budgeted uncertaintyRobust assortment optimization under sequential product unavailabilityStatistical distributions connected to motion of substance in a channel of a networkRobust combinatorial optimization with locally budgeted uncertaintyA robust multi-objective model for managing the distribution of perishable products within a green closed-loop supply chainHybrid stochastic and robust optimization model for lot-sizing and scheduling problems under uncertaintiesOn safe tractable approximations of chance constraintsLexicographic \(\alpha \)-robustness: an alternative to min-max criteriaRobust risk managementStochastic optimization in supply chain networks: averaging robust solutionsGeneralized hose uncertainty in single-commodity robust network designJoint chance constrained shortest path problem with Copula theoryA tractable approach for designing piecewise affine policies in two-stage adjustable robust optimizationMixed uncertainty sets for robust combinatorial optimizationA robust \(p\)-center problem under pressure to locate shelters in wildfire contextA note on the nonexistence of oracle-polynomial algorithms for robust combinatorial optimizationMin-max-min robustness for combinatorial problems with discrete budgeted uncertaintyOn the adaptivity gap in two-stage robust linear optimization under uncertain packing constraintsConvexification of generalized network flow problemThe robust vehicle routing problem with time windows: solution by branch and price and cutAn improved Lagrangian relaxation algorithm for the robust generation self-scheduling problemRobust proactive project scheduling model for the stochastic discrete time/cost trade-off problemRobust optimization of fourth party logistics network design under disruptionsComplexity of strict robust integer minimum cost flow problems: an overview and further resultsA multiobjective route robust optimization model and algorithm for hazmat transportationProtection of flows under targeted attacksLarge-scale unit commitment under uncertainty: an updated literature surveyA perfect information lower bound for robust lot-sizing problemsRobust combinatorial optimization under budgeted-ellipsoidal uncertaintyTrade-off between robustness and cost for a storage loading problem: rule-based scenario generationRobust counterpart optimization for the redundancy allocation problem in series-parallel systems with component mixing under uncertaintyShortest path network problems with stochastic arc weightsNew algorithmic framework for conditional value at risk: application to stochastic fixed-charge transportationThe resource constrained shortest path problem with uncertain data: a robust formulation and optimal solution approachMinimizing the weighted sum of completion times under processing time uncertaintyRobust strategic planning for mobile medical units with steerable and unsteerable demandsMultiobjective optimization under uncertainty: a multiobjective robust (relative) regret approachRobust and sustainable supply chains under market uncertainties and different risk attitudes -- a case study of the German biodiesel marketDecision-dependent probabilities in stochastic programs with recoursePlanning solid waste collection with robust optimization: location-allocation, receptacle type, and service frequencyThe multi-band robust knapsack problem -- a dynamic programming approachComplexity results and exact algorithms for robust knapsack problemsA utility theory based interactive approach to robustness in linear optimizationThe study of the unidirectional quay crane scheduling problem: complexity and risk-aversionAnchored reactive and proactive solutions to the CPM-scheduling problemDifferent stakeholders' perspectives for a surgical case assignment problem: deterministic and robust approachesItinerary planning with time budget for risk-averse travelersRobust multicovers with budgeted uncertaintyA short note on the robust combinatorial optimization problems with cardinality constrained uncertaintyProduction planning in furniture settings via robust optimizationRobust portfolio selection for index trackingRobust budget allocation via continuous submodular functionsFacility location problems with uncertainty on the planeOracle-based algorithms for binary two-stage robust optimizationAdjustable robust balanced hub location problem with uncertain transportation costRobust flows over time: models and complexity resultsDistributionally robust discrete optimization with entropic Value-at-RiskRobust binary optimization using a safe tractable approximationExact lexicographic scheduling and approximate reschedulingA decomposition approach for optimal gas network extension with a finite set of demand scenariosMultiple kernel learning-aided robust optimization: learning algorithm, computational tractability, and usage in multi-stage decision-makingA vehicle routing problem with distribution uncertainty in deadlinesA robust optimization approach for the multi-mode resource-constrained project scheduling problemMaximum excess dominance: identifying impractical solutions in linear problems with interval coefficientsAddressing uncertainty in sugarcane harvest planning through a revised multi-choice goal programming modelPolyhedral approximation of ellipsoidal uncertainty sets via extended formulations: a computational case studyA comparison between the robust risk-aware and risk-seeking managers in R\&D portfolio managementA robust optimization model for multi-product two-stage capacitated production planning under uncertaintyA robust optimization approach for an integrated dynamic cellular manufacturing system and production planning with unreliable machinesA robust service selection method based on uncertain QoSRobust monotone submodular function maximizationThe complexity of computing a robust flowA robust data envelopment analysis model with different scenariosImpact of compressor failures on gas transmission network capabilityRobust optimization-based heuristic algorithm for the chance-constrained knapsack problem using submodularityThe gain of robustness for a storage loading problemA constrained multi-period robust portfolio model with behavioral factors and an interval semi-absolute deviationFaster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertaintyDesigning networks with resiliency to edge failures using two-stage robust optimizationThe ordered \(k\)-median problem: surrogate models and approximation algorithmsRobust minimum cost consensus model for multicriteria decision-making under uncertain circumstancesOn the motion of substance in a channel and growth of random networksThe continuous maximum capacity path interdiction problemRobust drone selective routing in humanitarian transportation network assessmentFormulations and algorithms for the recoverable \({\varGamma}\)-robust knapsack problemMultiskilled personnel assignment problem under uncertain demand: a benchmarking analysisWaste collection inventory routing with non-stationary stochastic demandsThe submodularity of two-stage stochastic maximum-weight independent set problemsRobust inventory problem with budgeted cumulative demand uncertaintyDerivative-free robust optimization for circuit designA robust omnichannel pricing and ordering optimization approach with return policies based on data-driven support vector clusteringRobust alternative fuel refueling station location problem with routing under decision-dependent flow uncertaintyThe robust crew pairing problem: model and solution methodologyLarge-scale unit commitment under uncertaintyRobust multi-period fleet allocation models for bike-sharing systemsRobust and reliable portfolio optimization formulation of a chance constrained problemThe recoverable robust spanning tree problem with interval costs is polynomially solvableΓ-robust linear complementarity problemsCover inequalities for robust knapsack sets-Application to the robust bandwidth packing problemRecoverable robust shortest path problemsConstant-Ratio Approximation for Robust Bin Packing with Budgeted UncertaintyOracle-Based Robust Optimization via Online LearningRobustness analysis in multi-objective mathematical programming using Monte Carlo simulationWeekly self-scheduling, forward contracting, and pool involvement for an electricity producer. An adaptive robust optimization approachAn efficient variable neighborhood search for solving a robust dynamic facility location problem in emergency service networkThe robust network loading problem with dynamic routingA robust optimization approach to wine grape harvesting schedulingAffinely Adjustable Robust Linear Complementarity ProblemsRobust multiperiod portfolio management in the presence of transaction costsRobust Monotone Submodular Function MaximizationHeuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack ProblemOn the approximability of adjustable robust convex optimization under uncertaintyCutting plane versus compact formulations for uncertain (integer) linear programsRobust Shift Scheduling in Call CentersNew discoveries of domination between traffic matricesOptimization under Decision-Dependent UncertaintyFortification Against Cascade Propagation Under UncertaintyModeling Defender-Attacker Problems as Robust Linear Programs with Mixed-Integer Uncertainty SetsOn the complexity of min-max-min robustness with two alternatives and budgeted uncertaintyExact approaches to the robust vehicle routing problem with time windows and multiple deliverymenThe last-mile delivery process with trucks and drones under uncertain energy consumptionRecoverable robust spanning tree problem under interval uncertainty representationsRobust recoverable and two-stage selection problemsAn approach to the distributionally robust shortest path problemA value function-based approach for robust surgery planningAn implementor-adversary approach for uncertain and time-correlated service times in the nurse-to-patient assignment problemMultistage robust discrete optimization via quantified integer programmingOptimal fleet deployment for electric vehicle sharing systems with the consideration of demand uncertaintyArc routing under uncertainty: introduction and literature reviewA robust optimization model for distribution network design under a mixed integer set of scenariosAn iterative security game for computing robust and adaptive network flowsRobust scheduling with budgeted uncertaintyProportional and maxmin fairness for the sensor location problem with chance constraintsRouting optimization with time windows under uncertaintyFuzzy and robust approach for decision-making in disaster situationsExact algorithms for the robust uncapacitated multiple allocation \(p\)-hub median problemRobust minimum cost flow problem under consistent flow constraintsA robust optimization model for dynamic market with uncertain production costSolving the bi-objective Robust Vehicle Routing Problem with uncertain costs and demandsA Priori and A Posteriori Aggregation Procedures to Reduce Model Size in MIP Mine Planning ModelsRobust recoverable 0-1 optimization problems under polyhedral uncertaintyThe Complexity of Bottleneck Labeled Graph ProblemsCombinatorial optimization problems with balanced regretUnnamed ItemDynamic Container Deployment: Two-Stage Robust Model, Complexity, and Computational ResultsMulti-objective outpatient scheduling in health centers considering resource constraints and service quality: a robust optimization approachA robust optimization approach for the unrelated parallel machine scheduling problemRobust maximum weighted independent-set problems on interval graphsA note on the Bertsimas \& Sim algorithm for robust combinatorial optimization problemsr-extreme signalling for congestion controlSolving two-stage robust optimization problems using a column-and-constraint generation methodBottleneck combinatorial optimization problems with uncertain costs and the OWA criterionApproximating Single Machine Scheduling with ScenariosA Brief Overview of Interdiction and Robust OptimizationScenario relaxation algorithm for finite scenario-based min-max regret and min-max relative regret robust optimizationLexicographicα-robustness: an application to the 1-median problemLinear programming with interval right hand sidesTractable approximations to robust conic optimization problemsExtending scope of robust optimization: comprehensive robust counterparts of uncertain problemsRobust game theoryRobust global optimization with polynomialsRobust optimization of contaminant sensor placement for community water systemsStrong formulations of robust mixed 0-1 programmingPersistence in discrete optimization under data uncertaintyA mean-variance model for the minimum cost flow problem with stochastic arc costsRobustness in Multi-criteria Decision AidingExtensions of labeling algorithms for multi‐objective uncertain shortest path problemsA note on issues of over-conservatism in robust optimization with cost uncertaintyTwo-stage network constrained robust unit commitment problemBulk-robust combinatorial optimizationUnnamed ItemRouting Optimization Under UncertaintyRobustness Concepts for Knapsack and Network Design Problems Under Data UncertaintyExpansion planning for waste-to-energy systems using waste forecast prediction setsA generalised likelihood uncertainty estimation mixed-integer programming model: Application to a water resource distribution networkGeneralized Bounded Rationality and Robust Multicommodity Network DesignA Practicable Robust Counterpart Formulation for Decomposable Functions: A Network Congestion Case StudyA discussion on the conservatism of robust linear optimization problemsTractable algorithms for chance-constrained combinatorial problemsA Dynamic Programming Approach for a Class of Robust Optimization ProblemsThe lexicographic α-robust knapsack problemRobust routing and optimal partitioning of a traffic demand polytopeModeling and Managing Uncertainty in Process Planning and SchedulingA Relative Robust Optimization Approach for Full Factorial Scenario Design of Data Uncertainty and AmbiguityOn Robust Lot Sizing Problems with Storage Deterioration, with Applications to Heat and Power CogenerationRobust Optimization for Electricity GenerationLagrangian Duality for Robust Problems with Decomposable Functions: The Case of a Robust Inventory ProblemThe most likely path on series-parallel networksRobust shortest path planning and semicontractive dynamic programmingBranch-Cut-and-Price for the Robust Capacitated Vehicle Routing Problem with Knapsack UncertaintyRobust Optimization for the Hazardous Materials Transportation Network Design ProblemA Mean-Risk Model for the Traffic Assignment Problem with Stochastic Travel TimesExact approaches for solving robust prize-collecting Steiner tree problemsRobust optimization for the hazardous materials transportation network design problemPacking a Knapsack of Unknown CapacityRobust network design: Formulations, valid inequalities, and computationsAffine recourse for the robust network design problem: Between static and dynamic routingBenders decomposition approach for the robust network design problem with flow bifurcationsSoft robust solutions to possibilistic optimization problemsExact methods for discrete \({\varGamma}\)-robust interdiction problems with an application to the bilevel knapsack problemOptimising the flight turnaround schedules: an improved sliding time windows approach based on MILP and CP modelsAffine routing for robust network designA robust biobjective optimization approach for operating a shared energy storage under price uncertaintyRobust Algorithms for TSP and Steiner TreeA fix‐and‐optimize heuristic for the minmax regret shortest path arborescence problem under interval uncertaintyA hierarchical supply chain model for the sugar–alcohol energy sector with robust optimization analysisRecycling inequalities for robust combinatorial optimization with budget uncertaintyMin-Sup-Min Robust Combinatorial Optimization with Few Recourse SolutionsA survey on bilevel optimization under uncertaintyRobust Fleet Sizing and Deployment for Industrial and Independent Bulk Ocean Shipping CompaniesData-driven robust optimization using deep neural networksA state-of-the-art survey on multi-scenario schedulingThe robust multi-plant capacitated lot-sizing problemA single representative min-max-min robust selection problem with alternatives and budgeted uncertaintyRisk‐averse optimization and resilient network flowsModeling the Emergency Service Network of Police Special Forces Units for High-Risk Law Enforcement OperationsSingle machine robust scheduling with budgeted uncertaintyRobust optimization for the electric vehicle pickup and delivery problem with time windows and uncertain demandsShort paper -- A note on robust combinatorial optimization with generalized interval uncertaintyComparative analysis of linear programming relaxations for the robust knapsack problemA branch and bound algorithm for robust binary optimization with budget uncertaintyRobust optimization for minimizing energy consumption of multicast transmissions in coded wireless packet networks under distance uncertaintyMean‐standard deviation model for minimum cost flow problemRobust transshipment problem under consistent flow constraintsOn the complexity of robust multi-stage problems with discrete recourseSchedule robustness in the periodic supply vessels planning problem with stochastic demand and travel timeRobust two-stage combinatorial optimization problems under discrete demand uncertainties and consistent selection constraintsOn Bilevel Optimization with Inexact FollowerSubmodularity in Conic Quadratic Mixed 0–1 OptimizationOnline First-Order Framework for Robust Convex OptimizationDeriving compact extended formulations via LP-based separation techniquesExact Algorithms for Distributionally β-Robust Machine Scheduling with Uncertain Processing TimesRapidly Solving an Online Sequence of Maximum Flow Problems with Extensions to Computing Robust Minimum CutsDeriving compact extended formulations via LP-based separation techniquesRobust Optimization in Non-Linear Regression for Speech and Video Quality Prediction in Mobile Multimedia NetworksThe complexity of bottleneck labeled graph problemsApproximation results for makespan minimization with budgeted uncertaintyOptimal Design for Multi-Item Auctions: A Robust Optimization ApproachApproximation algorithms for cost-robust discrete minimization problems based on their LP-relaxationsSequential Shortest Path Interdiction with Incomplete Information and Limited Feedback