A tighter formulation of the <Emphasis Type="Italic">p</Emphasis>-median problem

Given a set of clients and a set of potential sites for facilities, the p-median problem consists of opening a set of p sites and assigning each client to the closest open facility to it. It can be viewed as a variation of the uncapacitated facility location problem. We propose a new formulation of this problem by a mixed integer linear problem. We show that this formulation, while it has the same value by LP-relaxation, can be much more efficient than two previous formulations. The computational experiment performed on two sets of benchmark instances has showed that the efficiency of the standard branch-and-cut algorithm has been significantly improved. Finally, we explore the structure of the new formulation in order to derive reduction rules and to accelerate the LP-relaxation resolution.     

Complexity of determining the most vital elements for the p-median and p-center location problems

We consider the k most vital edges (nodes) and min edge (node) blocker versions of the p-median and p-center location problems. Given a weighted connected graph with distances on edges and weights on nodes, the k most vital edges (nodes) p-median (respectively p-center) problem consists of finding a subset of k edges (nodes) whose removal from the graph leads to an optimal solution for the p-median (respectively p-center) problem with the largest total weighted distance (respectively maximum weighted distance). The complementary problem, min edge (node) blocker p-median (respectively p-center), consists of removing a subset of edges (nodes) of minimum cardinality such that an optimal solution for the p-median (respectively p-center) problem has a total weighted distance (respectively a maximum weighted distance) at least as large as a specified threshold. We show that k most vital edges p-median and k most vital edges p-center are NP-hard to approximate within a factor $\frac{7}{5}-\epsilon$ and $\frac{4}{3}-\epsilon$ respectively, for any ?>0, while k most vital nodes p-median and k most vital nodes p-center are NP-hard to approximate within a factor $\frac{3}{2}-\epsilon$ , for any ?>0. We also show that the complementary versions of these four problems are NP-hard to approximate within a factor 1.36.     

A Parametric Approach for a Nonlinear Discrete Location Problem

A discrete location problem is formulated for the design of a postal service network. The cost objective of this problem includes a nonlinear concave component. A parametric integer programming algorithm is developed to find an approximate solution to the problem. The algorithm reduces the problem into a sequence of p-median problems and deals with the nonlinear cost by a node-replacement scheme. Preliminary computational results are presented.     

Myopic Analysis for Multi‐Echelon Inventory Systems with Batch Ordering and Nonstationary/Time‐Correlated Demands

We provide an exact myopic analysis for an N‐stage serial inventory system with batch ordering, linear ordering costs, and nonstationary demands under a finite planning horizon. We characterize the optimality conditions of the myopic nested batching newsvendor (NBN) policy and the myopic independent batching newsvendor (IBN) policy, which is a single‐stage approximation. We show that echelon reorder levels under the NBN policy are upper bounds of the counterparts under both the optimal policy and the IBN policy. In particular, we find that the IBN policy has bounded deviations from the optimal policy. We further extend our results to systems with martingale model of forecast evolution (MMFE) and advance demand information. Moreover, we provide a recursive computing procedure and optimality conditions for both heuristics which dramatically reduces computational complexity. We also find that the NBN problem under the MMFE faced by one stage has one more dimension for the forecast demand than the one faced by its downstream stage and that the NBN policy is optimal for systems with advance demand information and stationary problem data. Numerical studies demonstrate that the IBN policy outperforms on average the NBN policy over all tested instances when their optimality conditions are violated.     

Protein Threading by Linear Programming: Theoretical Analysis and Computational Results

In a previous paper (Xu, Li, Kim, and Xu, Journal of Bioinformatics and Computational Biology, vol. 1, no. 1, pp. 95–117, 2003), we have used an integer programming approach to implement a protein threading program RAPTOR for protein 3D structure prediction, based on the threading model treating pairwise contacts rigorously and allowing variable gaps. We have solved the integer program by the canonical branch-and-bound method. In this paper we present a branch-and-cut method, a careful theoretical analysis of our formulation and why our approach is so effective. The result of cutting plane analysis is that two types of well-known cuts for this problem are already implied in the constraint set, which provides us some intuition that our formulation would be very effective. Experimental results show that for about 99 percent of real threading instances, the linear relaxations of their integer programs solve to integral optimal solutions directly. For the rest one percent of real instances, the integral solutions can be obtained with only several branch nodes. Experimental results also show that no special template or sequence features result in more possibilities of fractional solutions. This indicates that extra effort to seek for cutting planes to strengthen the existing formulation is unnecessary.     

Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios

We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin–destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.     

The <Emphasis Type="Italic">p</Emphasis>-maxian problem on block graphs

This paper deals with the p-maxian problem on block graphs with unit edge length. It is shown that the two points with maximum distance provide an optimal solution for the 2-maxian problem of block graphs except for K ₃. It can easily be extended to the p-maxian problem of block graphs. So we solve the p-maxian problem on block graphs in linear time.     

Experimental Results Indicating Lattice‐Dependent Policies May Be Optimal for General Assemble‐To‐Order Systems

We consider an assemble‐to‐order (ATO) system with multiple products, multiple components which may be demanded in different quantities by different products, possible batch ordering of components, random lead times, and lost sales. We model the system as an infinite‐horizon Markov decision process under the average cost criterion. A control policy specifies when a batch of components should be produced, and whether an arriving demand for each product should be satisfied. Previous work has shown that a lattice‐dependent base‐stock and lattice‐dependent rationing (LBLR) policy is an optimal stationary policy for a special case of the ATO model presented here (the generalized M‐system). In this study, we conduct numerical experiments to evaluate the use of an LBLR policy for our general ATO model as a heuristic, comparing it to two other heuristics from the literature: a state‐dependent base‐stock and state‐dependent rationing (SBSR) policy, and a fixed base‐stock and fixed rationing (FBFR) policy. Remarkably, LBLR yields the globally optimal cost in each of more than 22,500 instances of the general problem, outperforming SBSR and FBFR with respect to both objective value (by up to 2.6% and 4.8%, respectively) and computation time (by up to three orders and one order of magnitude, respectively) in 350 of these instances (those on which we compare the heuristics). LBLR and SBSR perform significantly better than FBFR when replenishment batch sizes imperfectly match the component requirements of the most valuable or most highly demanded product. In addition, LBLR substantially outperforms SBSR if it is crucial to hold a significant amount of inventory that must be rationed.     

Stochastic lot sizing problem with controllable processing times

In this study, we consider the stochastic capacitated lot sizing problem with controllable processing times where processing times can be reduced in return for extra compression cost. We assume that the compression cost function is a convex function as it may reflect increasing marginal costs of larger reductions and may be more appropriate when the resource life, energy consumption or carbon emission are taken into consideration. We consider this problem under static uncertainty strategy and α service level constraints. We first introduce a nonlinear mixed integer programming formulation of the problem, and use the recent advances in second order cone programming to strengthen it and then solve by a commercial solver. Our computational experiments show that taking the processing times as constant may lead to more costly production plans, and the value of controllable processing times becomes more evident for a stochastic environment with a limited capacity. Moreover, we observe that controllable processing times increase the solution flexibility and provide a better solution in most of the problem instances, although the largest improvements are obtained when setup costs are high and the system has medium sized capacities.     

Solving Steiner Tree Problems in Graphs with Lagrangian Relaxation

This paper presents an algorithm to obtain near optimal solutions for the Steiner tree problem in graphs. It is based on a Lagrangian relaxation of a multi-commodity flow formulation of the problem. An extension of the subgradient algorithm, the volume algorithm, has been used to obtain lower bounds and to estimate primal solutions. It was possible to solve several difficult instances from the literature to proven optimality without branching. Computational results are reported for problems drawn from the SteinLib library.     

Bounds of Relative Regret Limit in p‐Robust Supply Chain Network Design

This research studies the p‐robust supply chain network design with uncertain demand and cost scenarios. The optimal design integrates the supplier selection together with the facility location and capacity problem. We provide a new framework to obtain the relative regret limit, which is critical in the robust supply chain design but is assumed to be a known value in the existing literature. We obtain lower and upper bounds for relative regret limit and obtain a sequence of optimal solutions for series relative regret limits between the upper and lower bounds. An algorithm for p‐robust supply chain network design is provided. A series of numerical examples are designed to find the properties of the bottleneck scenarios. A scenario with low probability and a low optimal objective function value for the scenario has a greater chance of being a bottleneck. To focus only on the influence from the relative regret, we also introduce three separate new objective functions in p‐robust design. The proposed new theories and approaches provide a sequence of options for decision makers to reduce the marketing risks effectively in supply chain network design.     

Dual Objective Segmentation to Improve Targetability: An Evolutionary Algorithm Approach**

Cluster‐based segmentation usually involves two sets of variables: (i) the needs‐based variables (referred to as the bases variables), which are used in developing the original segments to identify the value, and (ii) the classification or background variables, which are used to profile or target the customers. The managers’ goal is to utilize these two sets of variables in the most efficient manner. Pragmatic managerial interests recognize the underlying need to start shifting from methodologies that obtain highly precise value‐based segments but may be of limited practical use as they provide less targetable segments. Consequently, the imperative is to shift toward newer segmentation approaches that provide greater focus on targetable segments while maintaining homogeneity. This requires dual objective segmentation, which is a combinatorially difficult problem. Hence, we propose and examine a new evolutionary methodology based on genetic algorithms to address this problem. We show, based on a large‐scale Monte Carlo simulation and a case study, that the proposed approach consistently outperforms the existing methods for a wide variety of problem instances. We are able to obtain statistically significant and managerially important improvements in targetability with little diminution in the identifiability of value‐based segments. Moreover, the proposed methodology provides a set of good solutions, unlike existing methodologies that provide a single solution. We also show how these good solutions can be used to plot an efficient Pareto frontier. Finally, we present useful insights that would help managers in implementing the proposed solution approach effectively.     

Multi-phase Algorithms for Throughput Maximization for Real-Time Scheduling

We consider the problem of off-line throughput maximization for job scheduling on one or more machines, where each job has a release time, a deadline and a profit. Most of the versions of the problem discussed here were already treated by Bar-Noy et al. (Proc. 31st ACM STOC, 1999, pp. 622–631; http://www.eng.tau.ac.il/amotz/). Our main contribution is to provide algorithms that do not use linear programming, are simple and much faster than the corresponding ones proposed in Bar-Noy et al. (ibid., 1999), while either having the same quality of approximation or improving it. More precisely, compared to the results of in Bar-Noy et al. (ibid., 1999), our pseudo-polynomial algorithm for multiple unrelated machines and all of our strongly-polynomial algorithms have better performance ratios, all of our algorithms run much faster, are combinatorial in nature and avoid linear programming. Finally, we show that algorithms with better performance ratios than 2 are possible if the stretch factors of the jobs are bounded; a straightforward consequence of this result is an improvement of the ratio of an optimal solution of the integer programming formulation of the JISP2 problem (see Spieksma, Journal of Scheduling, vol. 2, pp. 215–227, 1999) to its linear programming relaxation.     

The <Emphasis Type="Italic">k</Emphasis>-coloring fitness landscape

This paper deals with the fitness landscape analysis of the k-coloring problem. We study several standard instances extracted from the second DIMACS benchmark. Statistical indicators are used to investigate both global and local structure of fitness landscapes. An approximative distance on the k-coloring space is proposed to perform these statistical measures. Local search operator trajectories on various landscapes are then studied using the time series analysis. Results are used to better understand the behavior of metaheuristics based on local search when dealing with the graph coloring problem.     

Median problems with positive and negative weights on cycles and cacti

This paper deals with facility location problems on graphs with positive and negative vertex weights. We consider two different objective functions: In the first one (MWD) vertices with positive weight are assigned to the closest facility, whereas vertices with negative weight are assigned to the farthest facility. In the second one (WMD) all the vertices are assigned to the nearest facility. For the MWD model it is shown that there exists a finite set of points in the graph which contains the locations of facilities in an optimal solution. Furthermore, algorithms for both models for the 2-median problem on a cycle are developed. The algorithm for the MWD model runs in linear time, whereas the algorithm for the WMD model has a time complexity of  O(n²)\mathcal{O}(n^{2}) .     

Linear solution schemes for Mean-SemiVariance Project portfolio selection problems: An application in the oil and gas industry

We study the Mean-SemiVariance Project (MSVP) portfolio selection problem, where the objective is to obtain the optimal risk-reward portfolio of non-divisible projects when the risk is measured by the semivariance of the portfolio׳s Net-Present Value (NPV) and the reward is measured by the portfolio׳s expected NPV. Similar to the well-known Mean-Variance portfolio selection problem, when integer variables are present (e.g., due to transaction costs, cardinality constraints, or asset illiquidity), the MSVP problem can be solved using Mixed-Integer Quadratic Programming (MIQP) techniques. However, conventional MIQP solvers may be unable to solve large-scale MSVP problem instances in a reasonable amount of time. In this paper, we propose two linear solution schemes to solve the MSVP problem; that is, the proposed schemes avoid the use of MIQP solvers and only require the use of Mixed-Integer Linear Programming (MILP) techniques. In particular, we show that the solution of a class of real-world MSVP problems, in which project returns are positively correlated, can be accurately approximated by solving a single MILP problem. In general, we show that the MSVP problem can be effectively solved by a sequence of MILP problems, which allow us to solve large-scale MSVP problem instances faster than using MIQP solvers. We illustrate our solution schemes by solving a real MSVP problem arising in a Latin American oil and gas company. Also, we solve instances of the MSVP problem that are constructed using data from the PSPLIB library of project scheduling problems.     

Determining an Optimal Penetration Among Weighted Regions in Two and Three Dimensions

We present efficient algorithms for solving the problem of computing an optimal penetration (a ray or a semi-ray) among weighted regions in 2-D and 3-D spaces. This problem finds applications in several areas, such as radiation therapy, geological exploration, and environmental engineering. Our algorithms are based on a combination of geometric techniques and optimization methods. Our geometric analysis shows that the d-D (d = 2, 3) optimal penetration problem can be reduced to solving O(n ^2(d–1)) instances of certain special types of non-linear optimization problems, where n is the total number of vertices of the regions. We also give implementation results of our 2-D algorithms.     

Identification and Estimation of Average Partial Effects in “Irregular” Correlated Random Coefficient Panel Data Models

In this paper we study identification and estimation of a correlated random coefficients (CRC) panel data model. The outcome of interest varies linearly with a vector of endogenous regressors. The coefficients on these regressors are heterogenous across units and may covary with them. We consider the average partial effect (APE) of a small change in the regressor vector on the outcome (cf. Chamberlain (1984), Wooldridge (2005a)). Chamberlain (1992) calculated the semiparametric efficiency bound for the APE in our model and proposed a √N‐consistent estimator. Nonsingularity of the APE's information bound, and hence the appropriateness of Chamberlain's (1992) estimator, requires (i) the time dimension of the panel (T) to strictly exceed the number of random coefficients (p) and (ii) strong conditions on the time series properties of the regressor vector. We demonstrate irregular identification of the APE when T = p and for more persistent regressor processes. Our approach exploits the different identifying content of the subpopulations of stayers—or units whose regressor values change little across periods—and movers—or units whose regressor values change substantially across periods. We propose a feasible estimator based on our identification result and characterize its large sample properties. While irregularity precludes our estimator from attaining parametric rates of convergence, its limiting distribution is normal and inference is straightforward to conduct. Standard software may be used to compute point estimates and standard errors. We use our methods to estimate the average elasticity of calorie consumption with respect to total outlay for a sample of poor Nicaraguan households.     

Decision Support System of Truck Routing and Refueling: A Dual‐Objective Approach

The variable‐route vehicle‐refueling problem (VRVRP) is a variant of the network‐flow problem which seeks, for a vehicle traveling from origin s to destination d, both the route and the refueling policy (sequence of fuel stations to use between s and d) that jointly minimize the fuel cost of operating the vehicle. Commercial‐grade decision support systems that solve the VRVRP are widely used by motor carriers, but they provide heuristic solutions only. Exact methods are available from the academic side, but because they focus on minimizing costs, they tend to cut fuel costs in exchange for increased vehicle miles (which can increase fuel consumptions and pollutants emission). We propose a new approach to the VRVRP that allows carriers to jointly seek the two possibly conflicting goals; minimizing fuel cost and vehicle miles. Computational testing shows that our approach (i) outperforms the commercial software products in both goals, and (ii) finds solutions that require significantly less vehicle miles than those given by the exact method proposed in the academic literature, without incurring unacceptable increases in fuel cost.     

Cautious Expected Utility and the Certainty Effect

Many violations of the independence axiom of expected utility can be traced to subjects' attraction to risk‐free prospects. The key axiom in this paper, negative certainty independence ([Dillenberger, 2010]), formalizes this tendency. Our main result is a utility representation of all preferences over monetary lotteries that satisfy negative certainty independence together with basic rationality postulates. Such preferences can be represented as if the agent were unsure of how to evaluate a given lottery p; instead, she has in mind a set of possible utility functions over outcomes and displays a cautious behavior: she computes the certainty equivalent of p with respect to each possible function in the set and picks the smallest one. The set of utilities is unique in a well defined sense. We show that our representation can also be derived from a “cautious” completion of an incomplete preference relation.