Efficiency Bounds for Missing Data Models With Semiparametric Restrictions

This paper shows that the semiparametric efficiency bound for a parameter identified by an unconditional moment restriction with data missing at random (MAR) coincides with that of a particular augmented moment condition problem. The augmented system consists of the inverse probability weighted (IPW) original moment restriction and an additional conditional moment restriction which exhausts all other implications of the MAR assumption. The paper also investigates the value of additional semiparametric restrictions on the conditional expectation function (CEF) of the original moment function given always observed covariates. In the program evaluation context, for example, such restrictions are implied by semiparametric models for the potential outcome CEFs given baseline covariates. The efficiency bound associated with this model is shown to also coincide with that of a particular moment condition problem. Some implications of these results for estimation are briefly discussed.     

Interactive fuzzy goal programming for multi-objective transportation problems

This paper presents an interactive fuzzy goal programming approach to determine the preferred compromise solution for the multi-objective transportation problem. The proposed approach considers the imprecise nature of the input data by implementing the minimum operator and also assumes that each objective function has a fuzzy goal. The approach focuses on minimizing the worst upper bound to obtain an efficient solution which is close to the best lower bound of each objective function. The solution procedure controls the search direction via updating both the membership values and the aspiration levels. An important characteristic of the approach is that the decision maker's role is concentrated only in evaluating the efficient solution to limit the influences of his/her incomplete knowledge about the problem domain. In addition, the proposed approach can be applied to solve other multi-objective decision making problems. The performance of this solution approach is evaluated by comparing its results with that of the two existing methods in the literature.     

价格下界随时间递增的占线采购问题

本文研究的是价格不确定且其下界随时间递增的原材料采购问题。在实际的原材料采购问题中,原材料的价格随时间的变动往往是不可预测的。之前的学者在研究价格不确定的占线采购问题时,假设价格在一个统一的常数上下界内,这没有考虑到经过时间的变化,价格的上下界可能也是变化的。本文提出并研究价格下界随时间递增的原材料占线采购问题。构建了相应数学模型,给出了相应的竞争采购策略并证明了竞争比,同时通过证明问题的匹配竞争比下界,说明给出的竞争采购策略是最优的,最后利用数值分析进一步说明竞争策略具有较好的竞争性能。     

Fire scheduling for planned artillery attack operations under time-dependent destruction probabilities

In this paper, we consider the fire scheduling problem (FSP) for field artillery, which is the problem of scheduling operations of firing at given targets with a given set of weapons. We consider a situation in which the number of available weapons is smaller than the number of targets, the targets are assigned to the weapons already, and targets may move and hence the probability that a target is destroyed by a firing attack decreases as time passes. We present a branch and bound algorithm for the FSP with the objective of minimizing total threat of the targets, which is expressed as a function of the destruction probabilities of the targets. Results of computational tests show that the suggested algorithm solves problems of a medium size in a reasonable amount of computation time.     

Minimum entropy coloring

We study an information-theoretic variant of the graph coloring problem in which the objective function to minimize is the entropy of the coloring. The minimum entropy of a coloring is called the chromatic entropy and was shown by Alon and Orlitsky (IEEE Trans. Inform. Theory 42(5):1329–1339, 1996) to play a fundamental role in the problem of coding with side information. In this paper, we consider the minimum entropy coloring problem from a computational point of view. We first prove that this problem is NP-hard on interval graphs. We then show that, for every constant ε>0, it is NP-hard to find a coloring whose entropy is within (1−ε)log n of the chromatic entropy, where n is the number of vertices of the graph. A simple polynomial case is also identified. It is known that graph entropy is a lower bound for the chromatic entropy. We prove that this bound can be arbitrarily bad, even for chordal graphs. Finally, we consider the minimum number of colors required to achieve minimum entropy and prove a Brooks-type theorem. S. Fiorini acknowledges the support from the Fonds National de la Recherche Scientifique and GERAD-HEC Montréal. G. Joret is a F.R.S.-FNRS Research Fellow.     

Exact solution method to solve large scale integer quadratic multidimensional knapsack problems

In this paper we develop a branch-and-bound algorithm for solving a particular integer quadratic multi-knapsack problem. The problem we study is defined as the maximization of a concave separable quadratic objective function over a convex set of linear constraints and bounded integer variables. Our exact solution method is based on the computation of an upper bound and also includes pre-procedure techniques in order to reduce the problem size before starting the branch-and-bound process. We lead a numerical comparison between our method and three other existing algorithms. The approach we propose outperforms other procedures for large-scaled instances (up to 2000 variables and constraints). A extended abstract of this paper appeared in LNCS 4362, pp. 456–464, 2007.     

Joint Inventory and Pricing Coordination with Incomplete Demand Information

In retailing operations, retailers face the challenge of incomplete demand information. We develop a new concept named K‐approximate convexity, which is shown to be a generalization of K‐convexity, to address this challenge. This idea is applied to obtain a base‐stock list‐price policy for the joint inventory and pricing control problem with incomplete demand information and even non‐concave revenue function. A worst‐case performance bound of the policy is established. In a numerical study where demand is driven from real sales data, we find that the average gap between the profits of our proposed policy and the optimal policy is 0.27%, and the maximum gap is 4.6%.     

A Combined D.C. Optimization—Ellipsoidal Branch-and-Bound Algorithm for Solving Nonconvex Quadratic Programming Problems

In this paper we propose a new branch-and-bound algorithm by using an ellipsoidal partition for minimizing an indefinite quadratic function over a bounded polyhedral convex set which is not necessarily given explicitly by a system of linear inequalities and/or equalities. It is required that for this set there exists an efficient algorithm to verify whether a point is feasible, and to find a violated constraint if this point is not feasible. The algorithm is based upon the fact that the problem of minimizing an indefinite quadratic form over an ellipsoid can be efficiently solved by some available (polynomial and nonpolynomial time) algorithms. In particular, the d.c. (difference of convex functions) algorithm (DCA) with restarting procedure recently introduced by Pham Dinh Tao and L.T. Hoai An is applied to globally solving this problem. DCA is also used for locally solving the nonconvex quadratic program. It is restarted with current best feasible points in the branch-and-bound scheme, and improved them in its turn. The combined DCA-ellipsoidal branch-and-bound algorithm then enhances the convergence: it reduces considerably the upper bound and thereby a lot of ellipsoids can be eliminated from further consideration. Several numerical experiments are given.     

Two-agent scheduling problems on a single-machine to minimize the total weighted late work

In this paper, two-agent scheduling problems are presented. The different agents share a common processing resource, and each agent wants to minimize a cost function depending on its jobs only. The objective functions we consider are the total weighted late work and the maximum cost. The problem is to find a schedule that minimizes the objective function of agent A, while keeping the objective function of agent B cannot exceed a given bound U. Some different scenarios are presented by depending on the objective function of each agent. We address the complexity of those problems, and present the optimal polynomial time algorithms or pseudo-polynomial time algorithm to solve the scheduling problems, respectively.     

Change-making problems revisited: a parameterized point of view

The change-making problem is the problem of representing a given amount of money with the fewest number of coins possible from a given set of coin denominations. In the general version of the problem, an upper bound for the availability of every coin value is given. Even the special case, where for each value an unlimited number of coins is available, is NP-hard. Since in the original problem some amounts can not be represented, especially if no coin of value one exists, we introduce generalized problems that look for approximations of the given amount such that a cost function is minimized. We recall algorithms for the change-making problem and present new algorithms for the generalized version of the problem. Motivated by the NP-hardness we study fixed-parameter tractability of all these problems. We show that some of these problems are fixed-parameter tractable and that some are \(\hbox {W}[1]\)-hard. In order to show the existence of polynomial and constant-size kernels we prove some general results and apply them to several parameterizations of the change-making problems.     

Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval

In this article, we consider the non-resumable case of the single machine scheduling problem with a fixed non-availability interval. We aim to minimize the makespan when every job has a positive tail. We propose a polynomial approximation algorithm with a worst-case performance ratio of 3/2 for this problem. We show that this bound is tight. We present a dynamic programming algorithm and we show that the problem has an FPTAS (Fully Polynomial Time Approximation Algorithm) by exploiting the well-known approach of Ibarra and Kim (J. ACM 22:463–468, 1975). Such an FPTAS is strongly polynomial. The obtained results outperform the previous polynomial approximation algorithms for this problem.     

The maximum dispersion problem

In the maximum dispersion problem, a given set of objects has to be partitioned into a number of groups. Each object has a non-negative weight and each group has a target weight, which may be different for each group. In addition to meeting the target weight of each group, all objects assigned to the same group should be as dispersed as possible with respect to some distance measure between pairs of objects. Potential applications for this problem come from such diverse fields as the problem of creating study groups or the design of waste collection systems. We develop and compare two different (mixed-) integer linear programming formulations for the problem. We also study a specific relaxation that enables us to derive tight bounds that improve the effectiveness of the formulations. Thereby, we obtain an upper bound by finding in an auxiliary graph subsets of given size with minimal diameter. A lower bound is derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact solution scheme for the maximum dispersion problem and present extensive computational experiments to assess its efficiency.     

The Retail Planning Problem Under Demand Uncertainty

We consider the retail planning problem in which the retailer chooses suppliers and determines the production, distribution, and inventory planning for products with uncertain demand to minimize total expected costs. This problem is often faced by large retail chains that carry private‐label products. We formulate this problem as a convex‐mixed integer program and show that it is strongly NP‐hard. We determine a lower bound by applying a Lagrangian relaxation and show that this bound outperforms the standard convex programming relaxation while being computationally efficient. We also establish a worst‐case error bound for the Lagrangian relaxation. We then develop heuristics to generate feasible solutions. Our computational results indicate that our convex programming heuristic yields feasible solutions that are close to optimal with an average suboptimality gap at 3.4%. We also develop managerial insights for practitioners who choose suppliers and make production, distribution, and inventory decisions in the supply chain.     

An upper bound on the minimal total cost of the transportation problem with varying demands and supplies

In general cases, to find the exact upper bound on the minimal total cost of the transportation problem with varying demands and supplies is an NP-hard problem. In literature, there are only two approaches with several shortcomings to solve the problem. In this paper, the problem is formulated as a bi-level programming model, and proven to be solvable in a polynomial time if the sum of the lower bounds for all the supplies is no less than the sum of the upper bounds for all the demands; and a heuristic algorithm named TPVDS-A based on genetic algorithm is developed as an efficient and robust solution method of the model. Computational experiments on benchmark and new randomly generated instances show that the TPVDS-A algorithm outperforms the two existing approaches.     

A new recombination lower bound and the minimum perfect phylogenetic forest problem

Understanding recombination is a central problem in population genetics. In this paper, we address an established computational problem in this area: compute lower bounds on the minimum number of historical recombinations for generating a set of sequences (Hudson and Kaplan in Genetics 111, 147–164, 1985; Myers and Griffiths in Genetics 163, 375–394, 2003; Gusfield et al. in Discrete Appl. Math. 155, 806–830, 2007; Bafna and Bansal in IEEE/ACM Trans. Comput. Biol. Bioinf. 1, 78–90, 2004 and in J. Comput. Biol. 13, 501–521, 2006; Song et al. in Bioinformatics 421, i413–i244, 2005). In particular, we propose a new recombination lower bound: the forest bound. We show that the forest bound can be formulated as the minimum perfect phylogenetic forest problem, a natural extension to the classic binary perfect phylogeny problem, which may be of interests on its own. We then show that the forest bound is provably higher than the optimal haplotype bound (Myers and Griffiths in Genetics 163, 375–394, 2003), a very good lower bound in practice (Song et al. in Bioinformatics 421, i413–i422, 2005). We prove that, like several other lower bounds (Bafna and Bansal in J. Comput. Biol. 13, 501–521, 2006), computing the forest bound is NP-hard. Finally, we describe an integer linear programming (ILP) formulation that computes the forest bound precisely for certain range of data. Simulation results show that the forest bound may be useful in computing lower bounds for low quality data. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 16–26. The work was performed while Y. Wu was with UC Davis and supported by grants CCF-0515278 and IIS-0513910 from National Science Foundation. D. Gusfield supported by grants CCF-0515278 and IIS-0513910 from National Science Foundation.     

Staying safe and visible via message sharing in online social networks

As an imperative channel for fast information propagation, online social networks (OSNs) also have their defects. One of them is the information leakage, i.e., information could be spread via OSNs to the users whom we are not willing to share with. Thus the problem of constructing a circle of trust to share information with as many friends as possible without further spreading it to unwanted targets has become a challenging research topic but still remained open. Our work is the first attempt to study the Maximum Circle of Trust problem seeking to share the information with the maximum expected number of poster’s friends such that the information spread to the unwanted targets is brought to its knees. First, we consider a special and more practical case with the two-hop information propagation and a single unwanted target. In this case, we show that this problem is NP-hard, which denies the existence of an exact polynomial-time algorithm. We thus propose a Fully Polynomial-Time Approximation Scheme (FPTAS), which can not only adjust any allowable performance error bound but also run in polynomial time with both the input size and allowed error. FPTAS is the best approximation solution one can ever wish for an NP-hard problem. We next consider the number of unwanted targets is bounded and prove that there does not exist an FPTAS in this case. Instead, we design a Polynomial-Time Approximation Scheme (PTAS) in which the allowable error can also be controlled. When the number of unwanted targets are not bounded, we provide a randomized algorithm, along with the analytical theoretical bound and inapproximaibility result. Finally, we consider a general case with many hops information propagation and further show its #P-hardness and propose an effective Iterative Circle of Trust Detection (ICTD) algorithm based on a novel greedy function. An extensive experiment on various real-world OSNs has validated the effectiveness of our proposed approximation and ICTD algorithms. Such an extensive experiment also highlights several important observations on information leakage which help to sharpen the security of OSNs in the future.     

Allocation of Returned Products among Different Recovery Options through an Opportunity Cost–Based Dynamic Approach*

In a make‐to‐order product recovery environment, we consider the allocation decision for returned products decision under stochastic demand of a firm with three options: refurbishing to resell, parts harvesting, and recycling. We formulate the problem as a multiperiod Markov decision process (MDP) and present a linear programming (LP) approximation that provides an upper bound on the optimal objective function value of the MDP model. We then present two solution approaches to the MDP using the LP solution: a static approach that uses the LP solution directly and a dynamic approach that adopts a revenue management perspective and employs bid‐price controls technique where the LP is resolved after each demand arrival. We calculate the bid prices based on the shadow price interpretation of the dual variables for the inventory constraints and accept a demand if the marginal value is higher than the bid price. Since the need for solving the LP at each demand arrival requires a very efficient solution procedure, we present a transportation problem formulation of the LP via variable redefinitions and develop a one‐pass optimal solution procedure for it. We carry out an extensive numerical analysis to compare the two approaches and find that the dynamic approach provides better performance in all of the tested scenarios. Furthermore, the solutions obtained are within 2% of the upper bound on the optimal objective function value of the MDP model.     

OPTIMAL ORDERING IN A DUAL‐SUPPLIER SYSTEM WITH DEMAND FORECAST UPDATES

We study how an updated demand forecast affects a manufacturer's choice in ordering raw materials. With demand forecast updates, we develop a model where raw materials are ordered from two suppliers—one fast but expensive and the other cheap but slow—and further provide an explicit solution to the resulting dynamic optimization problem. Under some mild conditions, we demonstrate that the cost function is convex and twice‐differentiable with respect to order quantity. With this model, we are able to evaluate the benefit of demand information updating which leads to the identification of directions for further improvement. We further demonstrate that the model applies to multiple‐period problems provided that some demand regularity conditions are satisfied. Data collected from a manufacturer support the structure and conclusion of the model. Although the model is described in the context of in‐bound logistics, it can be applied to production and out‐bound logistics decisions as well.     

Reducibility of stochastic networks

This paper deals with the problem of reducing a stochastic network to one equivalent activity. The problem was motivated by the question of determining or approximating the probability distribution function of the duration of the longest or shortest path in a stochastic network. We define a particular reduction and use it to characterize the reducibility of such a network. The network can be reduced to one equivalent activity if the network does not have a special graph which we call the ‘interdictive graph’, or IG for short. If an IG is embedded in the network, the network is irreducible. In this case, its reduction becomes possible by duplicating some of the arcs in the irreducible network. The concept of duplicating an arc is introduced, then it is used to identify the arcs which can be duplicated. The reduction procedure is stated and illustrative examples are provided. An upper bound on the number of duplications is established.     

A hybrid heuristic for the uncapacitated single allocation hub location problem

The uncapacitated single allocation hub location problem (USAHLP), with the hub-and-spoke network structure, is a decision problem in regard to the number of hubs and location–allocation. In a pure hub-and-spoke network, all hubs, which act as switching points for internodal flows, are interconnected and none of the non-hubs (i.e., spokes) are directly connected. The key factors for designing a successful hub-and-spoke network are to determine the optimal number of hubs, to properly locate hubs, and to allocate the non-hubs to the hubs. In this paper two approaches to determine the upper bound for the number of hubs along with a hybrid heuristic based on the simulated annealing method, tabu list, and improvement procedures are proposed to resolve the USAHLP. Computational experiences indicate that by applying the derived upper bound for the number of hubs the proposed heuristic is capable of obtaining optimal solutions for all small-scaled problems very efficiently. Computational results also demonstrate that the proposed hybrid heuristic outperforms a genetic algorithm and a simulated annealing method in solving USAHLP.