A bulk arrival queueing model with fuzzy parameters and varying batch sizes

This paper develops a nonlinear programming approach to derive the membership functions of the steady-state performance measures in bulk arrival queueing systems with varying batch sizes, in that the arrival rate and service rate are fuzzy numbers. The basic idea is based on Zadeh’s extension principle. Two pairs of mixed integer nonlinear programs (MINLP) with binary variables are formulated to calculate the upper and lower bounds of the system performance measure at possibility level α. From different values of α, the membership function of the system performance measure is constructed. For practice use, the defuzzification of performance measures is also provided via Yager ranking index. To demonstrate the validity of the proposed method, a numerical example is solved successfully.     

Global Optimization of Nonlinear Bilevel Programming Problems

A novel technique that addresses the solution of the general nonlinear bilevel programming problem to global optimality is presented. Global optimality is guaranteed for problems that involve twice differentiable nonlinear functions as long as the linear independence constraint qualification condition holds for the inner problem constraints. The approach is based on the relaxation of the feasible region by convex underestimation, embedded in a branch and bound framework utilizing the basic principles of the deterministic global optimization algorithm, BB [2, 4, 5, 11]. Epsilon global optimality in a finite number of iterations is theoretically guaranteed. Computational studies on several literature problems are reported.     

Global solution of optimization problems with signomial parts

In this paper a new approach for the global solution of nonconvex MINLP (Mixed Integer NonLinear Programming) problems that contain signomial (generalized geometric) expressions is proposed and illustrated. By applying different variable transformation techniques and a discretization scheme a lower bounding convex MINLP problem can be derived. The convexified MINLP problem can be solved with standard methods. The key element in this approach is that all transformations are applied termwise. In this way all convex parts of the problem are left unaffected by the transformations. The method is illustrated by four example problems.     

Optimization models for the single delay management problem in public transportation

Passengers travelling in public transportation networks often have to use different lines to cover the trip from their origin to the desired destination. As a consequence, the reliability of connections between vehicles is a key issue for the attractiveness of the intermodal transportation network and it is strongly affected by some unpredictable events like breakdowns or vehicle delays. In such cases, a decision is required to determine if the connected vehicles should wait for the delayed ones or keep their schedule. The delay management problem (DMP) consists in defining the wait/depart policy which minimizes the total delay on the network. In this work, we present two equivalent mixed integer linear programming models for the DMP with a single initial delay, able to reduce the number of variables with respect to the formulations proposed by the literature. The two models are solved by a branch and cut procedure and by a constraint generation approach respectively, and preliminary computational results are presented.     

A hybrid Outer-Approximation/Benders Decomposition algorithm for the single allocation hub location problem under congestion

An efficient procedure that concurrently generates Outer-Approximation and Benders cuts is devised to tackle the single allocation hub location problem under congestion, an MINLP. The proposed method is able to optimally solve large instances (up to 200 nodes) in reasonable time. The combination of both cuts is an algorithmic novelty.     

Integrated design and operation of remnant inventory supply chains under uncertainty

We consider the simultaneous design and operation of remnant inventory supply chains. Remnant inventory is generated when demand for various lengths of a product may be satisfied by existing inventory, or by cutting a large piece into smaller pieces. We formulate our problem as a two-stage stochastic mixed-integer program. In solving our stochastic program, we enhance the standard L-shaped method in two ways. Our computational experiments demonstrate that these enhancements are effective, dramatically reducing the solution time for large instances.     

Interior analysis of the green product mix solution

When modeling optimal product mix under emission restrictions produces a solution with unacceptable level of profit, analyst is moved to investigate the cause(s). Interior analysis (IA) is proposed for this purpose. With IA, analyst can investigate the impact of accommodating emission controls in step-by-step one-at-a-time manner and in doing so track how profit and other important features of product mix degrade and to which emission control enforcements its diminution may be attributed. In this way, analyst can assist manager in identifying implementation strategies. Although IA is presented within context of a linear programming formulation of the green product mix problem, its methodology may be applied to other modeling frameworks. Quantity dependent penalty rates and transformations of emissions to forms with or without economic value are included in the modeling and illustrations of IA.     

On the use of the simplex algorithm for the absolute deviation curve fitting problem

Linear curve-fitting problems are commonly solved using a criterion which minimises the sum of the squares of deviations of observations from the line. The legitimacy of this operation relies on a number of assumptions which in practice are often left untested. Alternatively the curve-fitting exercise is justified by its computational tractibility. An alternative procedure which fits lines using a criterion of minimising the sum of the absolute deviations of observations from the line is acknowledged to have attractive properties, but is often avoided because of computational difficulties in solution. In fact this problem has long been known to be amenable to solution by linear programming, and in this paper we present some results, commentary and advice based on the use of three LP codes to solve the problem. Two of these codes are conventional implementations of the simplex method while the third is a special purpose code written for just this problem. Live data from a problem of batch manufacture was used, and the influence of data is part of the investigation. At least some of the advice is contrary to that offered by earlier authors.     

The multi-product newsboy problem with supplier quantity discounts and a budget constraint

This paper considers the multi-product newsboy problem with both supplier quantity discounts and a budget constraint, while each feature has been addressed separately in the literature. Different from most previous nonlinear optimization models on the topic, the problem is formulated as a mixed integer nonlinear programming model due to price discounts. A Lagrangian relaxation approach is presented to solve the problem. Computational results on both small and large-scale test instances indicate that the proposed algorithm is extremely effective for the problem. An extension to multiple constraints and preliminary computational results are also reported.     

Optimal scheduling of inspection times in a production process with a finite planning horizon

Inspection models applicable to a finite planning horizon are developed for the following lifetime distributions: uniform, exponential, and Weibull distribution. For a given lifetime distribution, maximization of profit is used as the sole optimization criterion for determining an optimal planning horizon over which a system may be operated as well as ideal inspection times. Illustrative examples (focusing on the uniform and Weibull distributions and using Mathematica programs) are given. For some situations, evenly spreading inspections over the entire planning horizon are seen to result in the attainment of desirable profit levels over a shorter planning horizon. Scope for further research is given as well. Copyright © 2016 John Wiley & Sons, Ltd.     

MIP reformulations of the probabilistic set covering problem

In this paper, we address the following probabilistic version (PSC) of the set covering problem: where A is a 0-1 matrix, is a random 0-1 vector and is the threshold probability level. We introduce the concepts of p-inefficiency and polarity cuts. While the former is aimed at deriving an equivalent MIP reformulation of (PSC), the latter is used as a strengthening device to obtain a stronger formulation. Simplifications of the MIP model which result when one of the following conditions hold are briefly discussed: A is a balanced matrix, A has the circular ones property, the components of are pairwise independent, the distribution function of is a stationary distribution or has the disjunctive shattering property. We corroborate our theoretical findings by an extensive computational experiment on a test-bed consisting of almost 10,000 probabilistic instances. This test-bed was created using deterministic instances from the literature and consists of probabilistic variants of the set covering model and capacitated versions of facility location, warehouse location and k-median models. Our computational results show that our procedure is orders of magnitude faster than any of the existing approaches to solve (PSC), and in many cases can reduce hours of computing time to a fraction of a second. Anureet Saxena’s research was supported by the National Science Foundation through grant #DMI-0352885 and by the Office of Naval Research through contract N00014-03-1-0133. Vineet Goyal’s research was supported in part by NSF grant CCF-0430751 and ITR grant CCR-0122581.     

Characterization and modelling of guillotine constraints

This paper focuses on guillotine cuts which often arise in real-life cutting stock problems. In order to construct a solution verifying guillotine constraints, the first step is to know how to determine whether a given cutting pattern is a guillotine pattern. For this purpose, we first characterize guillotine patterns by proving a necessary and sufficient condition. Then, we propose a polynomial algorithm to check this condition. Based on this mathematical characterization of guillotine patterns, we then show that guillotine constraints can be formulated into linear inequalities. The performance of the algorithm to check guillotine cutting patterns is evaluated by means of computational results.     

Lot-sizing with production and delivery time windows

We study two different lot-sizing problems with time windows that have been proposed recently. For the case of production time windows, in which each client specific order must be produced within a given time interval, we derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. For the variant with nonspecific orders, known to be equivalent to the problem in which the time windows can be ordered by time, we also show equivalence to the basic lot-sizing problem with upper bounds on the stocks. Here we derive polynomial time dynamic programming algorithms and tight extended formulations for the uncapacitated and constant capacity problems with general costs. For the problem with delivery time windows, we use a similar approach to derive tight extended formulations for both the constant capacity and uncapacitated problems with Wagner-Whitin (non-speculative) costs. We are most grateful for the hospitality of IASI, Rome, where part of this work was carried out. The collaboration with IASI takes place in the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract n MRTN-CT-2003-504438. This text presents research results of the Belgian Program on Interuniversity Poles of Attraction initiated by the Belgian State, Prime Minister's Office, Science Policy Programming. The scientific responsibility is assumed by the authors.     

Mixed Integer Models for the Stationary Case of Gas Network Optimization

A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed integer linear program. We study sub-polyhedra linking these piece-wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the separation algorithms are also presented. Our computational results demonstrate the success of this approach. Received: April, 2004     

A Class of Global Optimization Problems as Models of the Phase Unwrapping Problem

Let I={(i,j) i=1, 2,..., N ₁, j=1, 2,..., N ₂} and let U=U_i,j, (i,j)I be a discrete real function defined on I. Let []₂ be modulus 2, we define W:I , ) as follows W=[U]₂. The function U will be called phase function and the function W will be called wrapped phase function. The phase unwrapping problem consists in recovering U from some knowledge of W. This problem is not well defined, that is infinitely many functions U correspond to the same function W, and must be `regularized' to be satisfactorily solvable. We propose several formulations of the phase unwrapping problem as an integer nonlinear minimum cost flow problem on a network. Numerical algorithms to solve the minimum cost flow problems obtained are proposed. The phase unwrapping problem is the key problem in interferometry, we restrict our attention to the SAR (Synthetic Aperture Radar) interferometry problem. We compare the different formulations of the phase unwrapping problem proposed starting from the analysis of the numerical experience obtained with the numerical algorithms proposed on synthetic and real SAR interferometry data. The real data are taken from the ERS missions of the European Space Agency (ESA).     

Valid inequalities and branch-and-cut for the clique pricing problem

Motivated by an application in highway pricing, we consider the problem that consists in setting profit-maximizing tolls on a clique subset of a multicommodity transportation network. We formulate the problem as a linear mixed integer program and propose strong valid inequalities, some of which define facets of the two-commodity polyhedron. The numerical efficiency of these inequalities is assessed by embedding them within a branch-and-cut framework.     

带组约束可靠性网络最优化问题的精确算法

本文提出了一种求解带组约束串-并网络系统最优冗余问题的精确算法.该算法利用拉格朗日松驰和Dantzig-Wolfe分解法得到问题的上界,并结合动态规划求解子问题.算法采用一种有效的切割和剖分方法,以逐步缩小对偶间隙和保证收敛性.数值结果表明该算法对于求解带组约束可靠性最优化问题是很有效的.     

Optimum service capacity and demand management with price incentives

Service firms periodically face fluctuating demand levels. They incur high costs to handle peak demand and pay for under-utilized capacity during low demand periods. In this paper, we develop a mixed integer programming (MIP) model based on the real life experience of a Brazilian telecommunications firm. The model determines the optimum staffing requirements with different seniority levels for employees, as well as the distribution and balancing of workload utilizing flexibility of some customers in their service completion day. The proposed MIP uses monetary incentives to smooth the workload by redistributing some of the peak demand, thereby increasing capacity utilization. Due to the intractable nature of optimizing the proposed MIP model, we present a heuristic solution approach. The MIP model is applied to the case of the examined Brazilian Telecommunications firm. The computational work on this base case and its extensions shows that the proposed MIP model is of merit, leading to approximately seventeen percent reduction in the base case operating costs. Extensive computational work demonstrates that our heuristic provides quality solutions in very short computational times. The model can also be used to select new customers based on the workload, the revenue potential of these new customers and their flexibility in accepting alternate service completion dates. The generic structure of the proposed approach allows for its application to a wide variety of service organizations facing similar capacity and demand management challenges. Such wide applicability enhances the value of our work and its expected benefits.