基于风险的考虑成本和允许等待的车辆运输调度问题研究

本文同时考虑了成本约束和允许等待情形,研究了最小化风险的车辆运输调度问题,其中运输风险是随时间不同而变化的,即研究在时间依赖网络中基于风险的有约束的运输路径选择问题,以及在选定路径的顶点上决定的出发和等待时间的综合问题。建立了相应的混合整数规划模型,设计了相应的算法,并分析了算法复杂性,最后通过算例验证了该算法的有效性和可行性。     

Bi-objective multi-resource scheduling problem for emergency relief operations

Abstract

Resource scheduling for emergency relief operations is complex as it has many constraints. However, an effective allocation and sequencing of resources are crucial for the minimization of the completion times in emergency relief operations. Despite the importance of such decisions, only a few mathematical models of emergency relief operations have been studied. This article presents a bi-objective mixed integer programming (MIP) that helps to minimize both the total weighted time of completion of the demand points and the makespan of the total emergency relief operation. A two-phase method is developed to solve the bi-objective MIP problem. Additionally, a case study of hospital network in the Melbourne metropolitan area is used to evaluate the model. The results indicate that the model can successfully support the decisions required in the optimal resource scheduling of emergency relief operations.     

Integer programming formulations of statistical classification problems

A series of approaches is presented to formulate statistical classification problems using integer programming. The formulations attempt to maximize the number of observations that can be properly classified and utilize single function, multiple function and hierarchical multiple function approaches to the problems. The formulations are tested using standard software on a sample problem and new approaches are compared to those of other authors. As the solution of such problems gives rise to various awkward features in an integer programming framework, it is demonstrated that new approaches to formulation will not be completely successful in avoiding the difficulties of existing methods, but demonstrate certain gains.     

Multiobjective investment planning under uncertainty

In this paper we consider the relevance of various planning methods and decision criteria to multiobjective investment planning under uncertainty. Assuming that a natural reaction to uncertainty is to operate so as to leave open as many good options as possible (as opposed to maximizing subjective expected utility) we argue that the planning process should concentrate on analyzing the effects of the initial decision, and that for this exercise the classical methods of mixed integer programming are inappropriate. We demonstrate how the technique of dynamic programming can be extended to take account of multiple objectives and use dynamic programming as a framework in which we analyze the robustness of an initial decision in the face of various types of uncertainty. In so doing we also analyze the risks involved in both the planning and decision making functions.     

An Optimization‐Based Framework for the Identification of Vulnerabilities in Electric Power Grids Exposed to Natural Hazards

This article proposes a novel mathematical optimization framework for the identification of the vulnerabilities of electric power infrastructure systems (which is a paramount example of critical infrastructure) due to natural hazards. In this framework, the potential impacts of a specific natural hazard on an infrastructure are first evaluated in terms of failure and recovery probabilities of system components. Then, these are fed into a bi‐level attacker–defender interdiction model to determine the critical components whose failures lead to the largest system functionality loss. The proposed framework bridges the gap between the difficulties of accurately predicting the hazard information in classical probability‐based analyses and the over conservatism of the pure attacker–defender interdiction models. Mathematically, the proposed model configures a bi‐level max‐min mixed integer linear programming (MILP) that is challenging to solve. For its solution, the problem is casted into an equivalent one‐level MILP that can be solved by efficient global solvers. The approach is applied to a case study concerning the vulnerability identification of the georeferenced RTS24 test system under simulated wind storms. The numerical results demonstrate the effectiveness of the proposed framework for identifying critical locations under multiple hazard events and, thus, for providing a useful tool to help decisionmakers in making more‐informed prehazard preparation decisions.     

The supplier selection problem with quantity discounts and truckload shipping

To minimize procurement expenditures both purchasing and transportation costs need to be considered. We study a procurement setting in which a company needs to purchase a number of products from a set of suppliers to satisfy customer demand. The suppliers offer total quantity discounts and transportation costs are based on truckload shipping rates. The goal is to select a set of suppliers so as to satisfy product demand at minimal total costs. The resulting optimization problem is strongly NP-hard. We develop integer programming based heuristics to solve the problem. Extensive computational experiments demonstrate the efficacy of the proposed heuristics and provide insight into the impact of instance characteristics on effective procurement strategies.     

A Lagrangian relaxation approach for the multiple sequence alignment problem

We present a branch-and-bound (bb) algorithm for the multiple sequence alignment problem (MSA), one of the most important problems in computational biology. The upper bound at each bb node is based on a Lagrangian relaxation of an integer linear programming formulation for MSA. Dualizing certain inequalities, the Lagrangian subproblem becomes a pairwise alignment problem, which can be solved efficiently by a dynamic programming approach. Due to a reformulation w.r.t. additionally introduced variables prior to relaxation we improve the convergence rate dramatically while at the same time being able to solve the Lagrangian problem efficiently. Our experiments show that our implementation, although preliminary, outperforms all exact algorithms for the multiple sequence alignment problem. Furthermore, the quality of the alignments is among the best computed so far.     

Approximate Generalizations and Computational Experiments

In this paper I demonstrate how one can generalize finitely many examples to statements about (infinite) classes of economic models. If there exist upper bounds on the number of connected components of one‐dimensional linear subsets of the set of parameters for which a conjecture is true, one can conclude that it is correct for all parameter values in the class considered, except for a small residual set, once one has verified the conjecture for a predetermined finite set of points. I show how to apply this insight to computational experiments and spell out assumptions on the economic fundamentals that ensure that the necessary bounds on the number of connected components exist. I argue that these methods can be fruitfully utilized in applied general equilibrium analysis. I provide general assumptions on preferences and production sets that ensure that economic conjectures define sets with a bounded number of connected components. Using the theoretical results, I give an example of how one can explore qualitative and quantitative implications of general equilibrium models using computational experiments. Finally, I show how random algorithms can be used for generalizing examples in high‐dimensional problems.     

A Heuristic Algorithm for the Capacitated Multiple Supplier Inventory Grouping Problem

This paper presents and solves a model for the multiple supplier inventory grouping problem, which involves the minimization of logistics costs for a firm that has multiple suppliers with capacity limitations. The costs included in the model are purchasing, transportation, ordering, and inventory holding, while the firm's objective is to determine the optimal flows and groups of commodities from each supplier. We present an algorithm, which combines subgradient optimization and a primal heuristic, to quickly solve the multiple supplier inventory grouping problem. Our algorithm is tested extensively on problems of various sizes and structures, and its performance is compared to that of OSL, a state-of-the-art integer programming code. The computational results indicate that our approach is extremely efficient for solving the multiple supplier inventory grouping problem.     

A robust branch-and-cut approach for the minimum-energy symmetric network connectivity problem

This paper considers the minimum-energy symmetric network connectivity problem (MESNC) in wireless sensor networks. The aim of the MESNC is to assign transmission power to each sensor node such that the resulting network, using only bidirectional links, is connected and the total energy consumption is minimized. We first present two new models of this problem and then propose new branch-and-cut algorithms. Based on an existing formulation, we present the first model by introducing additional constraints. These additional constraints allow us to relax certain binary variables to continuous ones and thus to reduce significantly the number of binary variables. Our second model strengthens the first one by adding an exponential number of lifted directed-connectivity constraints. We present two branch-and-cut procedures based on these proposed improvements. The computational results are reported and show that our approaches, using the proposed formulations, can efficiently solve instances with up to 120 nodes, which significantly improve our ability to solve much larger instances in comparison with other exact algorithms in the literature.     

Using branch-and-price approach to solve the directed network design problem with relays

We present node-arc and arc-path formulations, and develop a branch-and-price approach for the directed network design problem with relays (DNDR). The DNDR problem can be used to model many network design problems in transportation, service, and telecommunication system, where relay points are necessary. The DNDR problem consists of introducing a subset of arcs and locating relays on a subset of nodes such that in the resulting network, the total cost (arc cost plus relay cost) is minimized, and there exists a directed path linking the origin and destination of each commodity, in which the distances between the origin and the first relay, any two consecutive relays, and the last relay and the destination do not exceed a predefined distance limit. With the node-arc formulation, we can directly solve small DNDR instances using mixed integer programming solver. With the arc-path formulation, we design a branch-and-price approach, which is a variant of branch-and-bound with bounds provided by solving linear programs using column generation at each node of the branch-and-bound tree. We design two methods to efficiently price out columns and present computational results on a set of 290 generated instances. Results demonstrate that our proposed branch-and-price approach is a computationally efficient procedure for solving the DNDR problem.     

A comparative study of formulations for a cross-dock door assignment problem

A cross docking facility is a type of warehouse in supply chain management that allows orders to be prepared with or without going through the phase of storing products in the warehouse and subsequently selecting them for delivery. The goods are unloaded from incoming trucks called origins on inbound doors of a cross-docking facility platform and, using a handling device inside the platform such as a forklift, immediately transferred to outbound doors to be loaded into outgoing trucks named destinations or delivery trucks for distribution to customers. Contrary to a traditional warehouse, goods are unloaded and loaded without placing them in temporary storage inside the cross-docking facility. The goal of the cross-docking assignment problem (CDAP) is to assign origins to inbound doors and destinations to outbound doors so that the total cost inside the cross-dock platform is minimized. To the best of our knowledge, there are only three mixed integer programming (MIP) formulations of the CDAP in the literature. We propose eight new MIP models and demonstrate the mathematical equivalence of all 11 models, together with rigorously proving some of their properties. In order to detect which of these 11 models is best, we conduct an extensive comparative analysis on benchmark instances from the literature, which discloses that the best model is one proposed in this paper for the first time.     

Mixed integer (0–1) fractional programming for decision support in paper production industry

This paper presents an effective and efficient method for solving a special class of mixed integer fractional programming (FP) problems. We take a classical reformulation approach for continuous FP as a starting point and extend it for solving a more general class of mixed integer (0–1) fractional programming problems.To stress the practical relevance of the research we focus on a real-life application in paper production industry. The constantly advancing physical knowledge of large scale pulp and paper production did have a substantial impact on an existing DSS in which mixed integer (0–1) fractional programming is introduced. We show that the motivation to solve a real-life fractional programming problem can provide the basis for a new approach in a new context that has an added value of its own, even outside the given application area. We describe the main characteristics of the DSS, the necessity to develop a non-iterative solution procedure and demonstrate both the effectiveness and efficiency of the proposed approach from practical data sets.     

On dual power assignment optimization for biconnectivity

Topology control is an important technology of wireless ad hoc networks to achieve energy efficiency and fault tolerance. In this paper, we study the dual power assignment problem for 2-edge connectivity and 2-vertex connectivity in the symmetric graphical model which is a combinatorial optimization problem from topology control technology.The problem is arisen from the following origin. In a wireless ad hoc network where each node can switch its transmission power between high-level and low-level, how can we establish a fault-tolerantly connected network topology in the most energy-efficient way? Specifically, the objective is to minimize the number of nodes assigned with high power and yet achieve 2-edge connectivity or 2-vertex connectivity.We addressed these optimization problems (2-edge connectivity and 2-vertex connectivity version) under the general graph model in (Wang et al. in Theor. Comput. Sci., 2008). In this paper, we propose a novel approximation algorithm, called Candidate Set Filtering algorithm, to compute nearly-optimal solutions. Specifically, our algorithm can achieve 3.67-approximation ratio for both 2-edge connectivity and 2-vertex connectivity, which improves the existing 4-approximation algorithms for these two cases.     

An access network design problem with end-to-end QoS constraints

In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.     

The three-dimensional matching problem in Kalmanson matrices

We investigate the computational complexity of several special cases of the three-dimensional matching problem where the costs are decomposable and determined by a so-called Kalmanson matrix. For the minimization version we develop an efficient polynomial time algorithm that is based on dynamic programming. For the maximization version, we show that there is a universally optimal matching (whose structure is independent of the particular Kalmanson matrix).     

Optimal mixed-model sequencing for balanced assembly lines

This paper describes an algorithm for solving optimally, the mixed-model sequencing problem when assembly line stations are balanced for each model. An optimal sequence is obtained with the minimization of the overall assembly line length for zero station idle time.The algorithm incorporates two basic steps. The first involves a search procedure that generates all cycle sequences; i.e. sequences having identical ‘start’ and ‘finish’ positions and whose work content can be executed within a defined station length. The second step uses integer programming (IP) to determine the number and combination of the various cycle sequences, such that the production demand is satisfied.     

TECHNICAL NOTE: A SIMPLE MODEL FOR OPTIMIZING THE SINGLE MACHINE EARLY/TARDY PROBLEM WITH SEQUENCE-DEPENDENT SETUPS

A simple mixed integer programming model for the N job/single machine scheduling problem with possibly sequence-dependent setup times, differing earliness/tardiness cost penalties, and variable due dates is proposed and evaluated for computational efficiency. Results indicated that the computational effort required to reach optimality rose with the number of jobs to be scheduled and with decreased variance in due dates. Though computational effort was significant for the largest problems solved, the model remained viable for optimizing research scale problems.     

Vendor Selection with Bundling: A Comment*

In a recent article by Rosenthal, Zydiak, and Chaudhry (1995), a mixed integer linear programming model was introduced to solve the vendor selection problem for the case in which the vendor can sell items individually or as part of a bundle. Each vendor offered only one type of bundle, and the buyer could purchase at most one bundle per vendor. The model employed n(m+ 1) binary variables, where n is the number of vendors and m is the number of products they sell. The existing model can lead to a purchasing paradox: it may force the buyer to pay more to receive less. We suggest a reformulation of the same problem that (i) eliminates this paradox and reveals a more cost-effective purchasing strategy; (ii) uses only n integer variables and significantly reduces the computational workload; and (iii) permits the buyer to purchase more than one bundle per vendor.