A polyhedral approach to a production planning problem

Production planning in manufacturing industries is concerned with the determination of the production quantities (lot sizes) of some items over a time horizon, in order to satisfy the demand with minimum cost, subject to some production constraints. In general, production planning problems become harder when different types of constraints are present, such as capacity constraints, minimum lot sizes, changeover times, among others. Models incorporating some of these constraints yield, in general, NP-hard problems. We consider a single-machine, multi-item lot-sizing problem, with those difficult characteristics. There is a natural mixed integer programming formulation for this problem. However, the bounds given by linear relaxation are in general weak, so solving this problem by LP based branch and bound is inefficient. In order to improve the LP bounds, we strengthen the formulation by adding cutting planes. Several families of valid inequalities for the set of feasible solutions are derived, and the corresponding separation problems are addressed. The result is a branch and cut algorithm, which is able to solve some real life instances with 5 items and up to 36 periods. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal distribution strategies with cyclic demands

This paper deals with the problem of finding the optimal assignment of given periodical demands over a planning horizon, so that a suitable objective function will be minimized. All deliveries are concentrated into one time unit for each of their time periods and they are located by the central decision maker in order to satisfy given constraints. The objective function considered is the minimization of the capacity of the production center which must satisfy the demands.     

Multi-item lot size determination and scheduling under capacity constraints

This paper deals with the planning of a production group, which has to produce several products. For each product there is a delivery plan covering several periods. Moreover, there are capacity constraints. Such a situation requires integrated optimization of lot sizes and lot scheduling. Since exact solution of the problem is in general not feasible, we will present a non exact approach which gives quite good results in some practical cases and might be a good starting point in other cases.     

An exact algorithm for solving a capacitated location-routing problem

In location-routing problems, the objective is to locate one or many depots within a set of sites (representing customer locations or cities) and to construct delivery routes from the selected depot or depots to the remaining sites at least system cost. The objective function is the sum of depot operating costs, vehicle acquisition costs and routing costs. This paper considers one such problem in which a weight is assigned to each site and where sites are to be visited by vehicles having a given capacity. The solution must be such that the sum of the weights of sites visited on any given route does not exceed the capacity of the visiting vehicle. The formulation of an integer linear program for this problem involves degree constraints, generalized subtour elimination constraints, and chain barring constraints. An exact algorithm, using initial relaxation of most of the problem constraints, is presented which is capable of solving problems with up to twenty sites within a reasonable number of iterations.     

On the approximability of adjustable robust convex optimization under uncertainty

In this paper, we consider adjustable robust versions of convex optimization problems with uncertain constraints and objectives and show that under fairly general assumptions, a static robust solution provides a good approximation for these adjustable robust problems. An adjustable robust optimization problem is usually intractable since it requires to compute a solution for all possible realizations of uncertain parameters, while an optimal static solution can be computed efficiently in most cases if the corresponding deterministic problem is tractable. The performance of the optimal static robust solution is related to a fundamental geometric property, namely, the symmetry of the uncertainty set. Our work allows for the constraint and objective function coefficients to be uncertain and for the constraints and objective functions to be convex, thereby providing significant extensions of the results in Bertsimas and Goyal (Math Oper Res 35:284–305, 2010) and Bertsimas et al. (Math Oper Res 36: 24–54, 2011b) where only linear objective and linear constraints were considered. The models in this paper encompass a wide variety of problems in revenue management, resource allocation under uncertainty, scheduling problems with uncertain processing times, semidefinite optimization among many others. To the best of our knowledge, these are the first approximation bounds for adjustable robust convex optimization problems in such generality.     

A lexicographic minimax algorithm for multiperiod resource allocation

Resource allocation problems are typically formulated as mathematical programs with some special structure that facilitates the development of efficient algorithms. We consider a multiperiod problem in which excess resources in one period can be used in subsequent periods. The objective minimizes lexicographically the nonincreasingly sorted vector of weighted deviations of cumulative activity levels from cumulative demands. To this end, we first develop a new minimax algorithm that minimizes the largest weighted deviation among all cumulative activity levels. The minimax algorithm handles resource constraints, ordering constraints, and lower and upper bounds. At each iteration, it fixes certain variables at their lower bounds, and sets groups of other variables equal to each other as long as no lower bounds are violated. The algorithm takes advantage of the problem's special structure; e.g., each term in the objective is a linear decreasing function of only one variable. This algorithm solves large problems very fast, orders of magnitude faster than well known linear programming packages. (The latter are, of course, not designed to solve such minimax problems efficiently.) The lexicographic procedure repeatedly employs the minimax algorithm described above to solve problems, each of the same format but with smaller dimension.     

Interior‐point methods and preconditioning for PDE‐constrained optimization problems involving sparsity terms

Partial differential equation (PDE)–constrained optimization problems with control or state constraints are challenging from an analytical and numerical perspective. The combination of these constraints with a sparsity‐promoting L¹ term within the objective function requires sophisticated optimization methods. We propose the use of an interior‐point scheme applied to a smoothed reformulation of the discretized problem and illustrate that such a scheme exhibits robust performance with respect to parameter changes. To increase the potency of this method, we introduce fast and efficient preconditioners that enable us to solve problems from a number of PDE applications in low iteration numbers and CPU times, even when the parameters involved are altered dramatically.     

Computational complexity of convoy movement planning problems

Convoy movement planning problems arise in a number of important logistical contexts, including military planning, railroad optimization and automated guided vehicle routing. In the convoy movement problem (CMP), a set of convoys, with specified origins and destinations, are to be routed with the objective of minimizing either makespan or total flow time, while observing a number of side constraints. This paper characterizes the computational complexity of several restricted classes of CMPs. The principal objective is to identify the most parsimonious set of problem features that make the CMP intractable. A polynomial-time algorithm is provided for the single criterion two-convoy movement problem. The performance of a simple prioritization–idling approximation algorithm is also analyzed for the K-convoy movement problem. Error bounds are developed for the makespan and flow time objectives.     

$$L^1$$ penalization of volumetric dose objectives in optimal control of PDEs

This work is concerned with a class of PDE-constrained optimization problems that are motivated by an application in radiotherapy treatment planning. Here the primary design objective is to minimize the volume where a functional of the state violates a prescribed level, but prescribing these levels in the form of pointwise state constraints leads to infeasible problems. We therefore propose an alternative approach based on \(L^1\) penalization of the violation that is also applicable when state constraints are infeasible. We establish well-posedness of the corresponding optimal control problem, derive first-order optimality conditions, discuss convergence of minimizers as the penalty parameter tends to infinity, and present a semismooth Newton method for their efficient numerical solution. The performance of this method for a model problem is illustrated and contrasted with an alternative approach based on (regularized) state constraints.     

On a nonseparable convex maximization problem with continuous knapsack constraints

We develop a polynomial-time algorithm for a class of nonseparable convex maximization problems with continuous knapsack constraints based on an analysis of the Karush-Kuhn-Tucker optimality conditions and the special problem structure. This problem class has applicability in areas such as production and logistics planning and financial engineering.     

IMRT treatment planning for prostate cancer using prioritized prescription optimization and mean-tail-dose functions

Treatment planning for intensity modulated radiation therapy (IMRT) is challenging due to both the size of the computational problems (thousands of variables and constraints) and the multi-objective, imprecise nature of the goals. We apply hierarchical programming to IMRT treatment planning. In this formulation, treatment planning goals/objectives are ordered in an absolute hierarchy, and the problem is solved from the top-down such that more important goals are optimized in turn. After each objective is optimized, that objective function is converted into a constraint when optimizing lower-priority objectives. We also demonstrate the usefulness of a linear/quadratic formulation, including the use of mean-tail-dose (mean dose to the hottest fraction of a given structure), to facilitate computational efficiency. In contrast to the conventional use of dose-volume constraints (no more than x% volume of a structure should receive more than y dose), the mean-tail-dose formulation ensures convex feasibility spaces and convex objective functions. To widen the search space without seriously degrading higher priority goals, we allowed higher priority constraints to relax or 'slip' a clinically negligible amount during lower priority iterations. This method was developed and tuned for external beam prostate planning and subsequently tested using a suite of 10 patient datasets. In all cases, good dose distributions were generated without individual plan parameter adjustments. It was found that allowance for a small amount of 'slip,' especially in target dose homogeneity, often resulted in improved normal tissue dose burdens. Compared to the conventional IMRT treatment planning objective function formulation using a weighted linear sum of terms representing very different dosimetric goals, this method: (1) is completely automatic, requiring no user intervention, (2) ensures high-priority planning goals are not seriously degraded by lower-priority goals, and (3) ensures that lower priority, yet still important, normal tissue goals are separately pushed as far as possible without seriously impacting higher priority goals.     

多变量、多约束连续或离散的非线性规划的一个通用算法

利用目标函数对约束函数关于设计变量的一阶微分或差分之比,给出了一个求解非线性规划的通用算法．不论变量和约束有多少,也不论变量是连续的还是离散的,这一算法都比较有效,尤其对离散非线性规划更有效．该方法是一种搜索法,勿需解任何数学方程,只需要计算函数值以及函数对变量的偏微分或差分值．许多数值例题和运筹学中一些经典问题,如1) 一、二维的背包问题;2) 一、二维资源分配问题;3) 复合系统工作可靠性问题;4) 机器负荷问题等,经用此法求解验证均较传统方法更有效和可靠．该方法的主要优点是:1) 不受问题的规模限制;2) 只要在可行域（集）内存在目标函数和约束函数及其一阶导数或差分的值,肯定可以搜索到最优的解,没有不收敛和不稳定的问题．     

An exact penalty approach for solving a class of minimization problems with boolean variables

An exact penalty approach for solving minimization problems with a concave objective function, linear constraints and Boolean variables is proposed. The penalty problems have continuous variables. An estimation of the penalty parameter which guarantees the exactness can be calculated on the base of an auxiliary problem. The results are applied to problems with an arbitrary quadratic objective function, linear constraints and Boolean variables. This leads to a modified Lagrangean approach for the latter problems. In the general case, the penalty approach is compared with a direct application of results of global optimization to a modification of the initial problem.     

An Exact Penalty Function Method for Continuous Inequality Constrained Optimal Control Problem

In this paper, we consider a class of optimal control problems subject to equality terminal state constraints and continuous state and control inequality constraints. By using the control parametrization technique and a time scaling transformation, the constrained optimal control problem is approximated by a sequence of optimal parameter selection problems with equality terminal state constraints and continuous state inequality constraints. Each of these constrained optimal parameter selection problems can be regarded as an optimization problem subject to equality constraints and continuous inequality constraints. On this basis, an exact penalty function method is used to devise a computational method to solve these optimization problems with equality constraints and continuous inequality constraints. The main idea is to augment the exact penalty function constructed from the equality constraints and continuous inequality constraints to the objective function, forming a new one. This gives rise to a sequence of unconstrained optimization problems. It is shown that, for sufficiently large penalty parameter value, any local minimizer of the unconstrained optimization problem is a local minimizer of the optimization problem with equality constraints and continuous inequality constraints. The convergent properties of the optimal parameter selection problems with equality constraints and continuous inequality constraints to the original optimal control problem are also discussed. For illustration, three examples are solved showing the effectiveness and applicability of the approach proposed.     

Global Optimization: Fractal Approach and Non-redundant Parallelism

More and more optimization problems arising in practice can not be solved by traditional optimization techniques making strong suppositions about the problem (differentiability, convexity, etc.). This happens because very often in real-life problems both the objective function and constraints can be multiextremal, non-differentiable, partially defined, and hard to be evaluated. In this paper, a modern approach for solving such problems (called global optimization problems) is described. This approach combines the following innovative and powerful tools: fractal approach for reduction of the problem dimension, index scheme for treating constraints, non-redundant parallel computations for accelerating the search. Through the paper, rigorous theoretical results are illustrated by figures and numerical examples.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.     

An approximation-based approach for fuzzy multi-period production planning problem with credibility objective

This paper develops a fuzzy multi-period production planning and sourcing problem with credibility objective, in which a manufacturer has a number of plants or subcontractors. According to the credibility service levels set by customers in advance, the manufacturer has to satisfy different product demands. In the proposed production problem, production cost, inventory cost and product demands are uncertain and characterized by fuzzy variables. The problem is to determine when and how many products are manufactured so as to maximize the credibility of the fuzzy costs not exceeding a given allowable invested capital, and this credibility can be regarded as the investment risk criteria in fuzzy decision systems. In the case when the fuzzy parameters are mutually independent gamma distributions, we can turn the service level constraints into their equivalent deterministic forms. However, in this situation the exact analytical expression for the credibility objective is unavailable, thus conventional optimization algorithms cannot be used to solve our production planning problems. To overcome this obstacle, we adopt an approximation scheme to compute the credibility objective, and deal with the convergence about the computational method. Furthermore, we develop two heuristic solution methods. The first is a combination of the approximation method and a particle swarm optimization (PSO) algorithm, and the second is a hybrid algorithm by integrating the approximation method, a neural network (NN), and the PSO algorithm. Finally, we consider one 6-product source, 6-period production planning problem, and compare the effectiveness of two algorithms via numerical experiments.     

Fair optimization of fortnightly physician schedules with flexible shifts

This research addresses a shift scheduling problem in which physicians are assigned to demand periods. We develop a reduced set covering approach that requires shift templates to be generated for a single day and compare it to an implicit modeling technique where shift-building rules are implemented as constraints. Both techniques allow full flexibility in terms of different shift starting times and lengths as well as break placements. The objective is to minimize the paid out hours under the restrictions given by the labor agreement. Furthermore, we integrate physician preferences and fairness aspects into the scheduling model. Computational results show the efficiency of the reduced set covering formulation in comparison to the implicit modeling approach.     

Relaxation-based algorithms for minimax optimization problems with resource allocation applications

We consider minimax optimization problems where each term in the objective function is a continuous, strictly decreasing function of a single variable and the constraints are linear. We develop relaxation-based algorithms to solve such problems. At each iteration, a relaxed minimax problem is solved, providing either an optimal solution or a better lower bound. We develop a general methodology for such relaxation schemes for the minimax optimization problem. The feasibility tests and formulation of subsequent relaxed problems can be done by using Phase I of the Simplex method and the Farkas multipliers provided by the final Simplex tableau when the corresponding problem is infeasible. Such relaxation-based algorithms are particularly attractive when the minimax optimization problem exhibits additional structure. We explore special structures for which the relaxed problem is formulated as a minimax problem with knapsack type constraints; efficient algorithms exist to solve such problems. The relaxation schemes are also adapted to solve certain resource allocation problems with substitutable resources. There, instead of Phase I of the Simplex method, a max-flow algorithm is used to test feasibility and formulate new relaxed problems.Corresponding author.Work was partially done while visiting AT&T Bell Laboratories.     

Optimal discrete-valued control computation

In this paper, we consider an optimal control problem in which the control takes values from a discrete set and the state and control are subject to continuous inequality constraints. By introducing auxiliary controls and applying a time-scaling transformation, we transform this optimal control problem into an equivalent problem subject to additional linear and quadratic constraints. The feasible region defined by these additional constraints is disconnected, and thus standard optimization methods struggle to handle these constraints. We introduce a novel exact penalty function to penalize constraint violations, and then append this penalty function to the objective. This leads to an approximate optimal control problem that can be solved using standard software packages such as MISER. Convergence results show that when the penalty parameter is sufficiently large, any local solution of the approximate problem is also a local solution of the original problem. We conclude the paper with some numerical results for two difficult train control problems.