A fast algorithm for the rectilinear distance location problem

In this paper, we consider the rectilinear distance location problem with box constraints (RDLPBC) and we show that RDLPBC can be reduced to the rectilinear distance location problem (RDLP). A necessary and sufficient condition of optimality is provided for RDLP. A fast algorithm is presented for finding the optimal solution set of RDLP. Global convergence of the method is proved by a necessary and sufficient condition. The new proposed method is provably more efficient in finding the optimal solution set. Computational experiments highlight the magnitude of the theoretical efficiency.     

Finding efficient solutions for rectilinear distance location problems efficiently

Given n planar existing facility locations, a planar new facility location X is called efficient if there is no other location Y for which the rectilinear distance between Y and each existing facility is at least as small as between X and each existing facility, and strictly less for at least one existing facility. Rectilinear distances are typically used to measure travel distances between points via rectilinear aisles or street networks. We first present a simple arrow algorithm, based entirely on geometrical analysis, that constructs all efficient locations. We then present a row algorithm which is of order n(log n) that constructs all efficient locations, and establish that no alternative algorithm can be of a lower order.     

A polygonal upper bound for the efficient set for single-facility location problems with mixed norms

Summary In this paper it is shown that, in a multiobjective single-facility location problem in which distances are measured by arbitrary mixed norms, the set of efficient points is a subset of apolygonal hull of the demand points. Using a certain type of projection, this hull can be easily built. We apply this to a certain family of norms, containing the set ofl _p -norms, and, in a particular case, classical results are obtained.     

The multifacility maximin planar location problem with facility interaction

^** Email: s.salhi{at}kent.ac.uk Two branch-and-bound algorithms are proposed to optimally solvethe maximin formulation for locating p facilities in the plane.Tight upper and lower bounds are constructed and suitable methodsof guiding the search developed. To enhance the method, efficientmeasures for identifying specific squares for subdivision aresuggested. The proposed algorithms are evaluated on a set ofrandomly generated problems of up to five facilities and 120nodes.     

An integer linear programming-based heuristic for scheduling heterogeneous,part-time service employees

Scheduling of heterogeneous, part-time, service employees with limited availability is especially challenging because employees have different availability and skills, and work different total work hours in a planning period, e.g., a week. The constraints typically are to meet employee requirements during each hour in a planning period with shifts which have a minimum & maximum length, and do not exceed 5 work days per week for each employee. The objectives typically are to minimize over staffing and to meet the target total work hours for each employee during the planning period. We decompose this problem into (a) determining good shifts and then (b) assigning the good shifts to employees, and use a set of small integer linear programs to solve each part. We apply this method to the data given in a reference paper and compare our results. Also, several random problems are generated and solved to verify the robustness of our solution method.     

An exact solution procedure for a cluster hub location problem

This paper proposes a new (MIP) model formulation and a new solution procedure for the hub network design problem under a non-restrictive policy introduced by Sung and Jin [Sung, C.S., Jin, H.W., 2001. Dual-based approach for a hub network design problem under non-restrictive policy. European Journal of Operational Research 132 (1), 88–105]. The model formulation contains significantly fewer variables so that optimal solutions for the LP-relaxation of the model can be determined for large instances using standard procedures for LP-models. Furthermore, the LP-relaxation provides very tight lower bounds. Computational results are given, which demonstrate that the new model formulation allows for solving much larger instances. It turned out that the new (exact) solution procedure, which utilises the new model formulation, is faster than the heuristic proposed by Sung and Jin (2001). It is also shown that the problem is np-hard.     

An interior-point method for the single-facility location problem with mixed norms using a conic formulation

We consider the single-facility location problem with mixed norms, i.e. the problem of minimizing the sum of the distances from a point to a set of fixed points in , where each distance can be measured according to a different p-norm. We show how this problem can be expressed into a structured conic format by decomposing the nonlinear components of the objective into a series of constraints involving three-dimensional cones. Using the availability of a self-concordant barrier for these cones, we present a polynomial-time algorithm (a long-step path-following interior-point scheme) to solve the problem up to any given accuracy. Finally, we report computational results for this algorithm and compare with standard nonlinear optimization solvers applied to this problem. This paper presents research results of the Belgian Network DYSCO (Dynamical Systems, Control, and Optimization), funded by the Interuniversity Attraction Poles Programme, initiated by the Belgian State, Science Policy Office. The first author acknowledges support by an FSR grant from Université Catholique de Louvain and a FRIA grant from Fonds de la Recherche Scientifique-FNRS. The scientific responsibility rests with its authors.     

Improved sorting-based procedure for integer programming

Recently, Cornuéjols and Dawande have considered a special class of 0-1 programs that turns out to be hard for existing IP solvers. One of them is a sorting-based algorithm, based on an idea of Wolsey. In this paper, we show how to improve both the running time and the space requirements of this algorithm. The drastic reduction of space needed allows us to solve much larger instances than was possible before using this technique. Received: November 10, 1999 / Accepted: July 6, 2001?Published online March 27, 2002     

Remarks on the integer Talmud solution for integer bankruptcy problems

In Fragnelli et al. (TOP 22:892–933, 2014; TOP 24:88–130, 2016), we considered a bankruptcy problem with the additional constraint that the estate has to be assigned in integer unities, allowing for non-integer claims; we dealt with the extension to our setting of the constrained equal losses solution and of the constrained equal awards solution. Here, we analyze the possibilities of extending the Talmud solution to the integer situation, starting from the existing approaches for the non-integer case; some of these approaches are compatible with the non-integer claims, but in order to comply with as much as possible of the approaches it is necessary to switch to integer claims.     

Efficient heuristics for the rectilinear distance capacitated multi-facility Weber problem

In this paper, we consider the capacitated multi-facility Weber problem with rectilinear distance. This problem is concerned with locating m capacitated facilities in the Euclidean plane to satisfy the demand of n customers with the minimum total transportation cost. The demand and location of each customer are known a priori and the transportation cost between customers and facilities is proportional to the rectilinear distance separating them. We first give a new mixed integer linear programming formulation of the problem by making use of a well-known necessary condition for the optimal facility locations. We then propose new heuristic solution methods based on this formulation. Computational results on benchmark instances indicate that the new methods can provide very good solutions within a reasonable amount of computation time.     

A heuristic procedure for stochastic integer programs with complete recourse

In this paper, we propose a successive approximation heuristic which solves large stochastic mixed-integer programming problem with complete fixed recourse. We refer to this method as the Scenario Updating Method, since it solves the problem by considering only a subset of scenarios which is updated at each iteration. Only those scenarios which imply a significant change in the objective function are added. The algorithm is terminated when no such scenarios are available to enter in the current scenario subtree. Several rules to select scenarios are discussed. Bounds on heuristic solutions are computed by relaxing some of the non-anticipativity constraints. The proposed procedure is tested on a multistage stochastic batch-sizing problem.     

Optimal locations for a class of nonlinear, single-facility location problems on a network

This paper investigates a class of single-facility location problems on an arbitrary network. Necessary and sufficient conditions are obtained for characterizing locally optimal locations with respect to a certain nonlinear objective function. This approach produces a number of new results for locating a facility on an arbitrary network, and in addition it unifies several known results for the special case of tree networks. It also suggests algorithmic procedures for obtaining such optimal locations.     

Mixed strategies in maximin testing of robust stabilization performance

We consider algorithms for testing robust stabilization performance for bilinear systems of special form, discrete-continuous systems of control of a dynamic object. We present an example of synthesis of a mixed testing strategy in the space module-orbital station rendezvous problem.     

Analysis of the consistency of a mixed integer programming-based multi-category constrained discriminant model

Classification is concerned with the development of rules for the allocation of observations to groups, and is a fundamental problem in machine learning. Much of previous work on classification models investigates two-group discrimination. Multi-category classification is less-often considered due to the tendency of generalizations of two-group models to produce misclassification rates that are higher than desirable. Indeed, producing “good” two-group classification rules is a challenging task for some applications, and producing good multi-category rules is generally more difficult. Additionally, even when the “optimal” classification rule is known, inter-group misclassification rates may be higher than tolerable for a given classification model. We investigate properties of a mixed-integer programming based multi-category classification model that allows for the pre-specification of limits on inter-group misclassification rates. The mechanism by which the limits are satisfied is the use of a reserved judgment region, an artificial category into which observations are placed whose attributes do not sufficiently indicate membership to any particular group. The method is shown to be a consistent estimator of a classification rule with misclassification limits, and performance on simulated and real-world data is demonstrated.     

Distributions of rectilinear deviation distance to visit a facility

This paper deals with the deviation distance to visit a facility from pre-planned routes. Facilities are approximated by both points and lines on a continuous plane. To see the relationship between the deviation distance and the availability of facilities, we derive the distributions of the rectilinear deviation distance for regular and random patterns of facilities. These distributions demonstrate how the shortest distance and the relative position of origin and destination affect the deviation distance. We also show that the deviation distance is a generalization of the nearest neighbour distance.     

On the maximin distance properties of orthogonal designs via the rotation

Space-filling designs are widely used in computer experiments. They are frequently evaluated by the orthogonality and distance-related criteria. Rotating orthogonal arrays is an appealing approach to constructing orthogonal space-filling designs. An important issue that has been rarely addressed in the literature is the design selection for the initial orthogonal arrays. This paper studies the maximin L₂-distance properties of orthogonal designs generated by rotating two-level orthogo...     

Mixed integer programming for scheduling flexible flow lines with limited intermediate buffers

This paper presents new mixed integer programming formulations for scheduling of a flexible flow line with blocking. The flexible flow line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more identical parallel machines. The line produces several different product types and each product must be processed by, at most, one machine in each stage. A product which has completed processing on a machine may remain there and block the machine until a downstream machine becomes available for processing. The objective is to determine a production schedule for all products so as to complete the products in a minimum time. The basic mixed integer programming formulations have been enhanced to model blocking scheduling with alternative processing routes where for each product a set of routes is available for processing. A reentrant flow line where a product visits a set of stages more than once is also considered. Numerical examples are presented to illustrate applications of the various models proposed.