On the strength of recursive McCormick relaxations for binary polynomial optimization

Recursive McCormick relaxations are among the most popular convexification techniques for binary polynomial optimization. It is well-understood that both the quality and the size of these relaxations depend on the recursive sequence and finding an optimal sequence amounts to solving a difficult combinatorial optimization problem. We prove that any recursive McCormick relaxation is implied by the extended flower relaxation, a linear programming relaxation, which for binary polynomial optimization problems with fixed degree can be solved in strongly polynomial time.     

Optimization of Optimal Power Flow Problems

Optimal power flow problems arise in the context of the optimization and secure exploitation of electrical power in alternating current (AC) networks. This optimization problem evaluates the flow on each line and to ensure that they are under line thermal limits. To improve the reliability of the power supply, a secure network is necessary, i.e., it has to be able to cope with some contingencies. Nowadays high performance solution methods, that are based on nonlinear programming algorithms, search for an optimal state while considering certain contingencies. According to the number of contingencies the problem size increases linearly. As the base case can already be large-scaled, the optimization time computation increases quickly. Parallelization seems to be a good way to solve quickly this kind of problem. This paper considers the minimization of an objective function and at least two constraints at each node. This optimization problem is solved by IPOPT, an interior point method, coupled with ADOL-C, an algorithmic differentiation tool, and MA27, a linear solver. Several results on employed parallelizing strategies will be discussed. (© 2011 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Managing pharmaceuticals delivery service using a hybrid particle swarm intelligence approach

Medicines or drugs have unique characteristics of short life cycle, small size, light weight, restrictive distribution time and the need of temperature and humidity control (selected items only). Thus, logistics companies often use different types of vehicles with different carrying capacities, and considering fixed and variable costs in service delivery, which make the vehicle assignment and route optimization more complicated. In this study, we formulate the problem to a multi-type vehicle assignment and mixed integer programming route optimization model with fixed fleet size under the constraints of distribution time and carrying capacity. Given non-deterministic polynomial hard and optimal algorithm can only be used to solve small-size problem, a hybrid particle swarm intelligence (PSI) heuristic approach, which adopts the crossover and mutation operators from genetic algorithm and 2-opt local search strategy, is proposed to solve the problem. We also adapt a principle based on cost network and Dijkstra’s algorithm for vehicle scheduling to balance the distribution time limit and the high loading rate. We verify the relative performance of the proposed method against several known optimal or heuristic solutions using a standard data set for heterogeneous fleet vehicle routing problem. Additionally, we compare the relative performance of our proposed Hybrid PSI algorithm with two intelligent-based algorithms, Hybrid Population Heuristic algorithm and Improved Genetic Algorithm, using a real-world data set to illustrate the practical and validity of the model and algorithm.

     

A Dual Active-Set Algorithm for Regularized Monotonic Regression

Monotonic (isotonic) regression is a powerful tool used for solving a wide range of important applied problems. One of its features, which poses a limitation on its use in some areas, is that it produces a piecewise constant fitted response. For smoothing the fitted response, we introduce a regularization term in the monotonic regression, formulated as a least distance problem with monotonicity constraints. The resulting smoothed monotonic regression is a convex quadratic optimization problem. We focus on the case, where the set of observations is completely (linearly) ordered. Our smoothed pool-adjacent-violators algorithm is designed for solving the regularized problem. It belongs to the class of dual active-set algorithms. We prove that it converges to the optimal solution in a finite number of iterations that does not exceed the problem size. One of its advantages is that the active set is progressively enlarging by including one or, typically, more constraints per iteration. This resulted in solving large-scale test problems in a few iterations, whereas the size of that problems was prohibitively too large for the conventional quadratic optimization solvers. Although the complexity of our algorithm grows quadratically with the problem size, we found its running time to grow almost linearly in our computational experiments.     

Multi-horizon stochastic programming

Infrastructure-planning models are challenging because of their combination of different time scales: while planning and building the infrastructure involves strategic decisions with time horizons of many years, one needs an operational time scale to get a proper picture of the infrastructure’s performance and profitability. In addition, both the strategic and operational levels are typically subject to significant uncertainty, which has to be taken into account. This combination of uncertainties on two different time scales creates problems for the traditional multistage stochastic-programming formulation of the problem due to the exponential growth in model size. In this paper, we present an alternative formulation of the problem that combines the two time scales, using what we call a multi-horizon approach, and illustrate it on a stylized optimization model. We show that the new approach drastically reduces the model size compared to the traditional formulation and present two real-life applications from energy planning.     

An Optimization Model to Determine Master Designs and Runs for Advertisement Printing

In this paper we consider a common optimization problem faced by a printing company while designing masters for advertisement material. A printing company may receive from various customers, advertisements for their products and services and their demand is for a specified number of copies to be printed. In a particular case, the printer receives these orders to be delivered next week from the customers, until the Thursday of a week. By Monday the printed copies have to be delivered to the customers. These advertisement items of the various customers are to be printed on large sheets of papers of specified standard sizes. The size is called a k-up if k items can be printed on one sheet. It is a given constraint that only items of the same size can be loaded on a master. This constraint results in a decomposition of the original problem of designing masters into many sub-problems, one for each size. The objective is to minimize the number of masters required while meeting the requirements of the customers. We formulate this optimization problem mathematically, discuss the computational issues and present some heuristic approaches for solving the problem.     

New mixed integer-programming model for the pickup-and-delivery problem with transshipment

In recent years, many important real-world applications are studied as “rich” vehicle routing problems that are variants and generalizations of the well-known vehicle routing problem. In this paper we address the pickup-and-delivery version of this problem and consider further generalization by allowing transshipment in the network. Moreover, we allow heterogenous vehicles and flexible fleet size. We describe mixed integer-programming formulations for the problem with and without time windows for services. The number of constraints and variables in the models are bounded by polynomial size of the problem. We discuss several problem variants that are either captured by our models or can be easily captured through simple modifications. Computational work gave promising results and confirms that transshipment in network can indeed enhance optimization.     

Iterative estimation maximization for stochastic linear programs with conditional value-at-risk constraints

We present a new algorithm, iterative estimation maximization (IEM), for stochastic linear programs with conditional value-at-risk constraints. IEM iteratively constructs a sequence of linear optimization problems, and solves them sequentially to find the optimal solution. The size of the problem that IEM solves in each iteration is unaffected by the size of random sample points, which makes it extremely efficient for real-world, large-scale problems. We prove the convergence of IEM, and give a lower bound on the number of sample points required to probabilistically bound the solution error. We also present computational performance on large problem instances and a financial portfolio optimization example using an S&P 500 data set.     

On optimal operating conditions for a data processing system: A stochastic approach

In this paper, we consider the problem of determining optimal operating conditions for a data processing system. The system is burned‐in for a fixed burn‐in time before it is put into field operation and, in field operation, it has a work size and follows an age‐replacement policy. Assuming that the underlying lifetime distribution of the system has a bathtub‐shaped failure rate function, the properties of optimal burn‐in time, optimal work size and optimal age‐replacement policy will be derived. It can be seen that this model is a generalization of those considered in the previous works, and it yields a better optimal operating conditions. This paper presents an analytical method for three‐dimensional optimization problem. An algorithm for determining optimal operating conditions is also given. Copyright © 2007 John Wiley & Sons, Ltd.     

Robust optimization approximation for joint chance constrained optimization problem

Chance constraint is widely used for modeling solution reliability in optimization problems with uncertainty. Due to the difficulties in checking the feasibility of the probabilistic constraint and the non-convexity of the feasible region, chance constrained problems are generally solved through approximations. Joint chance constrained problem enforces that several constraints are satisfied simultaneously and it is more complicated than individual chance constrained problem. This work investigates the tractable robust optimization approximation framework for solving the joint chance constrained problem. Various robust counterpart optimization formulations are derived based on different types of uncertainty set. To improve the quality of robust optimization approximation, a two-layer algorithm is proposed. The inner layer optimizes over the size of the uncertainty set, and the outer layer optimizes over the parameter t which is used for the indicator function upper bounding. Numerical studies demonstrate that the proposed method can lead to solutions close to the true solution of a joint chance constrained problem.     

Pricing European Options in a Discrete Time Model for the Limit Order Book

In this paper we build a discrete time model for the structure of the limit order book, so that the price per share depends on the size of the transaction. We deduce the value of a portfolio when the investor trades using market orders and a bank account with different interest rates for lending and borrowing. We also deduce conditions to rule out arbitrage and solve the problem of pricing and hedging an European call option with physical delivery. It is shown that contrary to the perfectly liquid setting, the price of a European call is not given by an expectation, but can be expressed as an optimization problem on a set of equivalent probability measures.

     

A systematic two phase approach for the nurse rostering problem

Nurse rostering is an NP-hard combinatorial problem which makes it extremely difficult to efficiently solve real life problems due to their size and complexity. Usually real problem instances have complicated work rules related to safety and quality of service issues in addition to rules about quality of life of the personnel. For the aforementioned reasons computer supported scheduling and rescheduling for the particular problem is indispensable. The specifications of the problem addressed were defined by the First International Nurse Rostering Competition (INRC2010) sponsored by the leading conference in the Automated Timetabling domain, PATAT-2010. Since the competition imposed quality and time constraint requirements, the problem instances were partitioned into sub-problems of manageable computational size and were then solved sequentially using Integer Mathematical Programming. A two phase strategy was implemented where in the first phase the workload for each nurse and for each day of the week was decided while in the second phase the specific daily shifts were assigned. In addition, local optimization techniques for searching across combinations of nurses’ partial schedules were also applied. This sequence is repeated several times depending on the available computational time. The results of our approach and the submitted software produced excellent solutions for both the known and the hidden problem instances, which in respect gave our team the first position in all tracks of the INRC-2010 competition.     

A Heuristic for Purchasing of Sheet Metal Decisions Based on Mathematical Programming

An operational research project at the Oskarshamn plant of Saab Scania AB Truckdivision Sweden is reported. The decision problem concerns the product mix of sheet metal purchased. A mathematical model that approximates the real-world problem is derived, the solution of which includes a p-median problem. This optimization problem is solved using Lagrangean relaxation and a subgradient optimization procedure. Numerical results for problems of real-world size and structure are reported and indicate satisfactory efficiency.     

On the cardinality of the Pareto set in bicriteria shortest path problems

Computing shortest paths with two or more conflicting optimization criteria is a fundamental problem in transportation and logistics. We study the problem of finding all Pareto-optimal solutions for the multi-criteria single-source shortest-path problem with nonnegative edge lengths. The standard approaches are generalizations of label-setting (Dijkstra) and label-correcting algorithms, in which the distance labels are multi-dimensional and more than one distance label is maintained for each node. The crucial parameter for the run time and space consumption is the total number of Pareto optima. In general, this value can be exponentially large in the input size. However, in various practical applications one can observe that the input data has certain characteristics, which may lead to a much smaller number—small enough to make the problem efficiently tractable from a practical viewpoint. For typical characteristics which occur in various applications we study in this paper whether we can bound the size of the Pareto set to a polynomial size or not. These characteristics are also evaluated (1) on a concrete application scenario (computing the set of best train connections in view of travel time, fare, and number of train changes) and (2) on a simplified randomized model. It will turn out that the number of Pareto optima on each visited node is restricted by a small constant in our concrete application, and that the size of the Pareto set is much smaller than our worst case bounds in the randomized model. A preliminary short version of this paper appeared in the Proceedings of the 5th Workshop on Algorithm Engineering (WAE 2001), LNCS 2141, Springer Verlag, pp. 185–197 (2001) under the title “Pareto shortest paths is often feasible in practice.”     

考虑员工学习效应的MTO/MOS指派模型及算法研究

订单式生产(MTO)人工作业系统(MOS)是我国中小制造企业广泛采用的生产系统模式。在MTO/MOS中,一线员工生产技能对生产绩效具有直接的影响。随着重复操作次数的增多,员工的生产效率不断提高,即产生学习效应。本文考虑员工学习效应来优化一线员工的配置,强调员工初始技能和学习能力的个体差异对完工期的影响,以期缩小理论研究与生产实践之间的差距。本文首先提出一个基于员工初始技能、员工的学习能力、工艺难度和订单批量的员工技能动态变化函数。然后,以最小化完工期为目标,建立一个优化模型。由于员工指派问题属于“完全NP-Hard”问题,为了求解本文所提出模型,本文提出Bootstrap方法对问题进行求解。最后,基于一个算例分析,验证该模型及算法的有效性。     

A study of exponential neighborhoods for the Travelling Salesman Problem and for the Quadratic Assignment Problem

This paper deals with exponential neighborhoods for combinatorial optimization problems. Exponential neighborhoods are large sets of feasible solutions whose size grows exponentially with the input length. We are especially interested in exponential neighborhoods over which the TSP (respectively, the QAP) can be solved in polynomial time, and we investigate combinatorial and algorithmical questions related to such neighborhoods.?First, we perform a careful study of exponential neighborhoods for the TSP. We investigate neighborhoods that can be defined in a simple way via assignments, matchings in bipartite graphs, partial orders, trees and other combinatorial structures. We identify several properties of these combinatorial structures that lead to polynomial time optimization algorithms, and we also provide variants that slightly violate these properties and lead to NP-complete optimization problems. Whereas it is relatively easy to find exponential neighborhoods over which the TSP can be solved in polynomial time, the corresponding situation for the QAP looks pretty hopeless: Every exponential neighborhood that is considered in this paper provably leads to an NP-complete optimization problem for the QAP. Received: September 5, 1997 / Accepted: November 15, 1999?Published online February 23, 2000     

Optimization for discretized switched systems

Switching time optimization is a crucial topic in the optimal control of hybrid systems. Since it is rare that such problems can be solved analytically, the use of numerical discretization schemes for the integration of state and adjoint systems is indispensable. Thus, in this contribution, the switching time optimization problem is studied in a discretized formulation directly from the beginning. An analysis of the discretized problem reveals that smoothness of the original (continuous time) problem is lost, i.e. the problem will in general become nondifferentiable in discrete time. This has to be taken into account when deriving an adjoint-based formula for the optimization of the discretized problem. A hybrid double pendulum example is used for illustration of the results. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A note on submodular set cover on matroids

We consider a problem related to the submodular set cover on polymatroids, when the ground set is the family of independent sets of a matroid. The achievement here is getting a strongly polynomial running time with respect to the ground set of the matroid even though the family of independent sets has exponential size. We also address the optimization problem of the maximization of submodular set functions on the independent sets of a matroid.     

Rescheduling unrelated parallel machines with total flow time and total disruption cost criteria

In this paper, we consider a rescheduling problem where a set of jobs has already been assigned to unrelated parallel machines. When a disruption occurs on one of the machines, the affected jobs are rescheduled, considering the efficiency and the schedule deviation measures. The efficiency measure is the total flow time, and the schedule deviation measure is the total disruption cost caused by the differences between the initial and current schedules. We provide polynomial-time solution methods to the following hierarchical optimization problems: minimizing total disruption cost among the minimum total flow time schedules and minimizing total flow time among the minimum total disruption cost schedules. We propose exponential-time algorithms to generate all efficient solutions and to minimize a specified function of the measures. Our extensive computational tests on large size problem instances have revealed that our optimization algorithm finds the best solution by generating only a small portion of all efficient solutions.     

Solving a Network Design Problem

Industrial optimization applications must be “robust” i.e., they must provide good solutions to problem instances of different size and numerical characteristics, and continue to work well when side constraints are added. This paper presents a case study that addresses this requirement and its consequences on the applicability of different optimization techniques. An extensive benchmark suite, built on real network design data, is used to test multiple algorithms for robustness against variations in problem size, numerical characteristics, and side constraints. The experimental results illustrate the performance discrepancies that have occurred and how some have been corrected. In the end, the results suggest that we shall remain very humble when assessing the adequacy of a given algorithm for a given problem, and that a new generation of public optimization benchmark suites is needed for the academic community to attack the issue of algorithm robustness as it is encountered in industrial settings.