The time-dependent rural postman problem: polyhedral results

The Chinese postman problem is a famous and classical problem in graph theory. This paper introduces a new variant of this problem, namely, the time-dependent rural postman problem, which is motivated by applications, involving scheduling with time-dependent processing time. We present an arc-path formulation for the problem with a constraint set that is divided into two parts. The first part is linear and has a strong combinatorial structure, which defines the polytope of the arc-path alternation sequence (APAS), while the second part is nonlinear and is closely related to time-dependent travel time. First, we investigate the facial structure of the APAS polytope and present several facet inequalities. Second, considering the travel and service time functions as piecewise functions, we linearize the nonlinear inequalities and propose several strong, valid inequalities. Finally, we propose a cutting plane algorithm and report numerical results on several randomly generated instances.     

The Traveling Salesman Problem with Draft Limits

In maritime transportation, routing decisions are sometimes affected by draft limits in ports. The draft of a ship is the distance between the waterline and the bottom of the ship and is a function of the load onboard. Draft limits in ports can thus prevent ships to enter these ports fully loaded and may impose a constraint on the sequence of visits made by a ship. This paper introduces the Traveling Salesman Problem with Draft Limits (TSPDL), which is to determine an optimal sequence of port visits under draft limit constraints. We present two mathematical formulations for the TSPDL, and suggest valid inequalities and strengthened bounds. We also introduce a set of instances based on TSPLIB. A branch-and-cut algorithm is applied on both formulations for all these instances. Computational results show that introducing draft limits make the problem much harder to solve. They also indicate that the proposed valid inequalities and strengthened bounds significantly reduce both the number of branch-and-bound nodes and the solution times.     

Open vehicle routing problem with demand uncertainty and its robust strategies

We investigate the open vehicle routing problem with uncertain demands, where the vehicles do not necessarily return to their original locations after delivering goods to customers. We firstly describe the customer’s demand as specific bounded uncertainty sets with expected demand value and nominal value, and propose the robust optimization model that aim at minimizing transportation costs and unsatisfied demands in the specific bounded uncertainty sets. We propose four robust strategies to cope with the uncertain demand and an improved differential evolution algorithm (IDE) to solve the robust optimization model. Then we analyze the performance of four different robust strategies by considering the extra costs and unmet demand. Finally, the computational experiments indicate that the robust optimization greatly avoid unmet demand while incurring a small extra cost and the optimal return strategy is the best strategy by balancing the trade-off the cost and unmet demand among different robust strategies.     

Generalization of the Nyquist robust stability margin and its application to systems with real affine parametric uncertainties

The critical direction theory for analysing the robust stability of uncertain feedback systems is generalized to include the case of non‐convex critical value sets, hence making the approach applicable for a much larger class of relevant systems. A redefinition of the critical perturbation radius is introduced, leading to the formulation of a Nyquist robust stability measure that preserves all the properties of the previous theory. The generalized theory is applied to the case of rational systems with an affine uncertainty structure where the uncertain parameters belong to a real rectangular polytope. Necessary and sufficient conditions for robust stability are developed in terms of the feasibility of a tractable linear‐equality problem subject to a set of linear inequalities, leading ultimately to a computable Nyquist robust stability margin. A systematic and numerically tractable algorithm is proposed for computing the critical perturbation radius needed for the calculation of the stability margin, and the approach is illustrated via examples. Copyright © 2001 John Wiley & Sons, Ltd.     

An LMI condition for the robust stability of uncertaincontinuous-time linear systems

A new sufficient condition for the robust stability of continuous-time uncertain linear systems with convex bounded uncertainties is proposed in this note. The results are based on linear matrix inequalities (LMIs) formulated at the vertices of the uncertainty polytope, which provide a parameter dependent Lyapunov function that assures the stability of any matrix inside the uncertainty domain. With the aid of numerical procedures based on unidimensional search and the LMIs feasibility tests, a simple and constructive way to compute robust stability domains can be established     

The challenge of equality constraints in robust design optimization: examination and new approach

In recent years, robust design optimization (RDO) has emerged as a significant area of research. The focus of RDO is to obtain a design that minimizes the effects of uncertainty on product reliability and performance. The effectiveness of the resulting solution in RDO highly depends on how the objective function and the constraints are formulated to account for uncertainties. Inequality constraint and objective function formulations under uncertainty have been studied extensively in the literature. However, the approaches for formulating equality constraints in the RDO literature are in a state of disharmony. Moreover, we observe that these approaches are generally applicable only to certain special cases of equality constraints. There is a need for a systematic approach for handling equality constraints in RDO, which is the motivation for this research. In this paper, we examine critical issues pertinent to formulating equality constraints in RDO. Equality constraints in RDO can be classified as belonging to two classes: (1) those that cannot be satisfied, because of the uncertainty inherently present in the RDO problem, and (2) those that must be satisfied, regardless of the uncertainty present in the problem. In this paper, we propose a linearization- based approach to classify equality constraints into the above two classes, and propose respective formulation methods. The theoretical developments presented in this paper are illustrated with the help of two numerical examples.     

New strategy for robust stability analysis of discrete-time uncertain systems

In this paper, a new robust stability analysis approach is developed for uncertain discrete-time linear time-invariant systems with polytopic or affine parameter-dependent uncertainty models. The proposed approach is based on a combination of a branch-and-bound like strategy with linear matrix inequality (LMI) based analysis formulations. Two sufficient conditions are considered, one for the robust stability of the uncertain system and other one for the contrary situation. If both sufficient conditions fail to characterize the polytope, then it is iteratively subdivided into subpolytopes until some one proves to be unstable or all ones are verified to be robustly stable. The polytope subdivision is implemented by means of a specially developed simplex subdivision algorithm. Exhaustive numerical tests prove the efficiency of the proposed approach when compared with the most recent LMI-based formulations.     

New Approach to Robust$ cal D$-Stability Analysis of Linear Time-Invariant Systems With Polytope-Bounded Uncertainty

This note presents a new approach to robust$ cal D$-stability analysis of linear time-invariant systems with polytope-bounded uncertainty. The proposed approach combines sufficient conditions for robust$ cal D$-stability in terms of feasibility problems with linear matrix inequalities (LMI) constraints and a new polytope partition technique. If the initial polytope does not attain the robust$ cal D$-stability sufficient condition, the polytope is successively subdivided until all subpolytopes attain the sufficient condition, in the case of robustly$ cal D$-stable uncertain system, or it is found a subpolytope vertex that does not attain the regional pole-placement constraints, in the case of an uncertain system that is not robustly$ cal D$-stable. It is presented a new general format polytope partition technique that allows the implementation of the proposed approach. The efficiency of the proposed approach is verified by means of illustrative examples and three different LMI-based analysis formulations.     

A two-stage robust optimization approach for the mobile facility fleet sizing and routing problem under uncertainty

We propose a two-stage robust optimization model for the mobile facility fleet sizing and routing problem with demand uncertainty. A two-level cutting plane based method is developed, which includes an algorithm to generate problem-specific lower bound inequalities in the outer level, and a hybrid algorithm in the inner level that combines heuristic and exact methods to solve the recourse problem. Numerical tests show that the design and operation from the proposed method outperforms other solution approaches. The efficiency of the proposed solution algorithm in identifying the optimal solution is quantified and the robustness of the proposed model is demonstrated for varying degrees of uncertainty in demand.     

Robust optimization framework for cardinality constrained portfolio problem

One of the primary concerns on any asset allocation problem is to maintain a limited number of assets from the market. The problem becomes more complicated when the return of all risky assets are subject to uncertainty. In this paper, we propose a new portfolio modeling approach with uncertain data and it is also analyzed using different robust optimization techniques. The proposed formulations are solved using genetic algorithm. The implementation of the proposed method is examined on variety of well known benchmark data sets.     

Heuristics for the robust vehicle routing problem with time windows

Uncertainty is frequently present in logistics and transportation, where vehicle routing problems play a crucial role. However, due to the complexity inherent in dealing with uncertainty, most research has been devoted to deterministic problems. This paper considers a robust version of the vehicle routing problem with hard time windows, in which travel times are uncertain. A budget polytope uncertainty set describes the travel times, to limit the maximum number of sailing legs that can be delayed. This makes sure that improbable scenarios are not considered, while making sure that solutions are immune to delays on a given number of sailing legs. Existing exact methods are only able to solve small instances of the problem and can be computationally demanding. With the aim of solving large instances with reduced running times, this paper proposes an efficient heuristic based on adaptive large neighborhood search. The computational study performed on instances with different uncertainty levels compares and analyzes the performance of four versions of the heuristic and shows how good quality solutions can be obtained within short computational times.     

A Computational Study of a Cutting Plane Algorithm for University Course Timetabling

In this paper, we describe a case-study where a Branch-and-Cut algorithm yields the “optimal” solution of a real-world timetabling problem of University courses (University Course Timetabling problem). The problem is formulated as a Set Packing problem with side constraints. To tighten the initial formulation, we utilize well-known valid inequalities of the Set Packing polytope, namely Clique and Lifted Odd-Hole inequalities. We also analyze the combinatorial properties of the problem to introduce new families of cutting planes that are not valid for the Set Packing polytope, and their separation algorithms. These cutting planes turned out to be very effective to yield the optimal solution of a set of real-world instances with up to 69 courses, 59 teachers, and 15 rooms.     

A discrete time exact solution approach for a complex hybrid flow-shop scheduling problem with limited-wait constraints

We study a real-world complex hybrid flow-shop scheduling problem arising from a bio-process industry. There are a variety of constraints to be taken into account, in particular zero intermediate capacity and limited waiting time between processing stages. We propose an exact solution approach for this optimization problem, based on a discrete time representation and a mixed-integer linear programming formulation. The proposed solution algorithm makes use of a new family of valid inequalities exploiting the fact that a limited waiting time is imposed on jobs between two successive production stages. The results of our computational experiments confirm that the proposed method produces good feasible schedules for industrial instances.     

A branch-and-cut algorithm for quadratic assignment problems based on linearizations

The quadratic assignment problem (QAP) is one of the hardest combinatorial optimization problems known. Exact solution attempts proposed for instances of size larger than 15 have been generally unsuccessful even though successful implementations have been reported on some test problems from the QAPLIB up to size 36. In this study, we focus on the Koopmans–Beckmann formulation and exploit the structure of the flow and distance matrices based on a flow-based linearization technique that we propose. We present two new IP formulations based on the flow-based linearization technique that require fewer variables and yield stronger lower bounds than existing formulations. We strengthen the formulations with valid inequalities and report computational experience with a branch-and-cut algorithm. The proposed method performs quite well on QAPLIB instances for which certain metrics (indices) that we proposed that are related to the degree of difficulty of solving the problem are relatively high (?0.3$?0.3$). Many of the well-known instances up to size 25 from the QAPLIB (e.g. nug24, chr25a) are in this class and solved in a matter of days on a single PC using the proposed algorithm.     

A less conservative LMI condition for the robust stability of discrete-time uncertain systems

In this paper, a less conservative condition for the robust stability of uncertain discrete-time linear systems is proposed. The uncertain parameters, assumed to be time-invariant, are supposed to belong to convex bounded domains (polytope type uncertainty). The stability condition is formulated in terms of a set of linear matrix inequalities involving only the vertices of the polytope domain. A simple and numerically efficient feasibility test provides a set of Lyapunov matrices whose convex combination can be used to assess the stability of any dynamic matrix inside the uncertainty domain. Examples illustrate the results.     

A comparative study of formulations and solution methods for the discrete ordered p-median problem

This paper presents several new formulations for the Discrete Ordered Median Problem (DOMP) based on its similarity with some scheduling problems. Some of the new formulations present a considerably smaller number of constraints to define the problem with respect to some previously known formulations. Furthermore, the lower bounds provided by their linear relaxations improve the ones obtained with previous formulations in the literature even when strengthening is not applied. We also present a polyhedral study of the assignment polytope of our tightest formulation showing its proximity to the convex hull of the integer solutions of the problem. Several resolution approaches, among which we mention a branch and cut algorithm, are compared. Extensive computational results on two families of instances, namely randomly generated and from Beasley's OR-library, show the power of our methods for solving DOMP.     

Solving an integrated employee timetabling and job-shop scheduling problem via hybrid branch-and-bound

We propose exact hybrid methods based on integer linear programming (ILP) and constraint programming (CP) for an integrated employee timetabling and job-shop scheduling problem. Each method we investigate uses a CP formulation associated with an LP relaxation. Under a CP framework, the LP relaxation is integrated into a global constraint using in addition reduced cost-based filtering techniques. We propose two CP formulations of the problem yielding two different LP relaxations. The first formulation is based on a direct representation of the problem. The second formulation is based on a decomposition in intervals of the possible operation starting times. We show the theoretical interest of the decomposition-based representation compared to the direct representation through the analysis of dominant schedules. Computational experiments on a set of randomly generated instances confirm the superiority of the decomposition-based representation. In both cases, the hybrid methods outperform pure CP for employee cost minimization while it is not the case for makespan minimization. The experiments also investigate the interest of the proposed integrated method compared to a sequential approach and show its potential for multiobjective optimization.     

The Nyquist robust sensitivity margin for uncertain closed‐loop systems

The Nyquist robust sensitivity margin is proposed as a new scalar indicator of robust stability that also provides a meaningful quantitative assessment of the worst sensitivity realized by the uncertain closed loop. After formulating and discussing in detail the underlying optimization problem required for the calculation of the margin, the approach is applied to the characterization of the robust stability of a closed‐loop featuring a linear system with an affine uncertainty structure and a parametric uncertainty set described by a real rectangular polytope. The capabilities of the methodology are illustrated through examples, which include an approach for quantifying alternative robustness margins, such as a parametric stability margin. The computational algorithm is systematic and can be carried out with high numerical precision. Copyright © 2005 John Wiley & Sons, Ltd.     

Emergency transportation planning in disaster relief supply chain management: a cooperative fuzzy optimization approach

Emergency transportation is the most important part of disaster relief supply chain operations, and its planning problem always involves multiple objectives, complex constraints, and inherent uncertainty. Based on the analysis of several natural disaster that occurred in China since 2007, we propose a multi-objective fuzzy optimization problem of emergency transportation planning in disaster relief supply chains, which takes into consideration three transportation modes: air, rail, and road. To cope with the uncertainty, we employ three correlated fuzzy ranking criteria, and define the β dominance relation for evaluating the solutions of the problem. To efficiently solve the problem, we develop a cooperative optimization method that divides the integrated problem into a set of subcomponents, evolves the sub-solutions concurrently, and brings together the sub-solutions to construct complete solutions. The proposed method is effective, scalable, and robust, and thus contributes greatly to the performance of emergency transportation planning in disaster management.     

Robust multiperiod portfolio management in the presence of transaction costs

We study the viability of different robust optimization approaches to multiperiod portfolio selection. Robust optimization models treat future asset returns as uncertain coefficients in an optimization problem, and map the level of risk aversion of the investor to the level of tolerance of the total error in asset return forecasts. We suggest robust optimization formulations of the multiperiod portfolio optimization problem that are linear and computationally efficient. The linearity of the optimization problems is an advantage when complex additional requirements need to be imposed on the portfolio structure, e.g., limitations on positions in certain assets or tax constraints. We compare the performance of our robust formulations to the performance of the traditional single period mean-variance formulation frequently employed in the financial industry.