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.     

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.     

Mixed integer formulations for the probabilistic minimum energy broadcast problem in wireless networks

In this paper we study a new variant of the minimum energy broadcast (MEB) problem, namely the probabilistic MEB (PMEB). The objective of the classic MEB problem is to assign transmission powers to the nodes of a wireless network is such a way that the total energy dissipated on the network is minimized, while a connected broadcasting structure is guaranteed by the assigned transmission powers. In the new variant of the problem treated in this paper, node failure is taken into account, aiming at providing solutions with a chosen reliability level for the broadcasting structure. Three mixed integer linear programming formulations for the new problem are presented, together with efficient formulation-dependent methods for their solution. Computational results are proposed and discussed. One method emerges as the most promising one under realistic settings. It is able to handle problems with up to fifty nodes.     

Extremal and game-theoretic characterizations of the probabilistic approach to income redistribution

In this paper, we cast the problem of income redistribution in two different ways, one as a nonlinear goal programming model and the other as a game theoretic model. These two approaches give characterizations for the probabilistic approach suggested by Intriligator for this problem. All three approaches reinforce the linear income redistribution plan as a desirable mechanism of income redistribution.This research was partly supported by ONR Contract No. N00014-82-K-0295 with the Center for Cybernetic Studies, The University of Texas, Austin, Texas.     

Functional inference in semiparametric models using the piggyback bootstrap

This paper introduces the “piggyback bootstrap.” Like the weighted bootstrap, this bootstrap procedure can be used to generate random draws that approximate the joint sampling distribution of the parametric and nonparametric maximum likelihood estimators in various semiparametric models, but the dimension of the maximization problem for each bootstrapped likelihood is smaller. This reduction results in significant computational savings in comparison to the weighted bootstrap. The procedure can be stated quite simply. First obtain a valid random draw for the parametric component of the model. Then take the draw for the nonparametric component to be the maximizer of the weighted bootstrap likelihood with the parametric component fixed at the parametric draw. We prove the procedure is valid for a class of semiparametric models that includes frailty regression models airsing in survival analysis and biased sampling models that have application to vaccine efficacy trials. Bootstrap confidence sets from the piggyback, and weighted bootstraps are compared for biased sampling data from simulated vaccine efficacy trials.     

Adaptive sample size and importance sampling in estimation-based local search for the probabilistic traveling salesman problem

The probabilistic traveling salesman problem is a paradigmatic example of a stochastic combinatorial optimization problem. For this problem, recently an estimation-based local search algorithm using delta evaluation has been proposed. In this paper, we adopt two well-known variance reduction procedures in the estimation-based local search algorithm: the first is an adaptive sampling procedure that selects the appropriate size of the sample to be used in Monte Carlo evaluation; the second is a procedure that adopts importance sampling to reduce the variance involved in the cost estimation. We investigate several possible strategies for applying these procedures to the given problem and we identify the most effective one. Experimental results show that a particular heuristic customization of the two procedures increases significantly the effectiveness of the estimation-based local search.     

A contribution to the linear programming approach to joint cost allocation: Methodology and application

The linear programming (LP) approach has been commonly proposed for joint cost allocation purposes. Within a LP framework, the allocation rules are based on a marginal analysis. Unfortunately, the additivity property which is required to completely allocate joint costs fails in presence of capacity, institutional or environmental constraints.     

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.     

MIP-based decomposition strategies for large-scale scheduling problems in multiproduct multistage batch plants: A benchmark scheduling problem of the pharmaceutical industry

An efficient systematic iterative solution strategy for solving real-world scheduling problems in multiproduct multistage batch plants is presented. Since the proposed method has its core a mathematical model, two alternative MIP scheduling formulations are suggested. The MIP-based solution strategy consists of a constructive step, wherein a feasible and initial solution is rapidly generated by following an iterative insertion procedure, and an improvement step, wherein the initial solution is systematically enhanced by implementing iteratively several rescheduling techniques, based on the mathematical model. A salient feature of our approach is that the scheduler can maintain the number of decisions at a reasonable level thus reducing appropriately the search space. A fact that usually results in manageable model sizes that often guarantees a more stable and predictable optimization model behavior. The proposed strategy performance is tested on several complicated problem instances of a multiproduct multistage pharmaceuticals scheduling problem. On average, high quality solutions are reported with relatively low computational effort. Authors encourage other researchers to adopt the large-scale pharmaceutical scheduling problem to test on it their solution techniques, and use it as a challenging comparison reference.     

Improving weak efficiency frontiers in the fuzzy data envelopment analysis models

Evaluating the performance of activities or organization by common data envelopment analysis models requires crisp input/output data. However, the precise inputs and outputs of production processes cannot be always measured. Thus, the data envelopment analysis measurement containing fuzzy data, called “fuzzy data envelopment analysis”, has played an important role in the evaluation of efficiencies of real applications. This paper focuses on the fuzzy CCR model and proposes a new method for determining the lower bounds of fuzzy inputs and outputs. This improves the weak efficiency frontiers of the corresponding production possibility set. Also a numerical example illustrates the capability of the proposed method.     

Computation of lower bounds on the network cost in location problems subject to distance constraints

Methods for the computation of lower bounds on the cost of the connecting network for the continuous and discrete variants of the problem of location of interconnected objects subject to minimal or maximal distances between them are proposed. For the continuous variant, the bound is found by solving a linear programming problem. For the discrete variant, an assignment problem with a rectangular matrix containing forbidden entries is constructed. An application of the assignment problem for locating objects of various sizes is described.     

A dual simplex-based method for determination of the right and left returns to scale in DEA

This study reviews the concept of the “right” and the “left” returns to scale (RTS) in data envelopment analysis (DEA), and a dual simplex-based method, for determining these two notions in RTS, is proposed, which has computational advantages as compared to the customary method.     

Recent developments in the qualitative approach to inverse electromagnetic scattering theory

We consider the inverse scattering problem of determining both the shape and some of the physical properties of the scattering object from a knowledge of the (measured) electric and magnetic fields due to the scattering of an incident time-harmonic electromagnetic wave at fixed frequency. We shall discuss the linear sampling method for solving the inverse scattering problem which does not require any a priori knowledge of the geometry and the physical properties of the scatterer. Included in our discussion is the case of partially coated objects and inhomogeneous background. We give references for numerical examples for each problem discussed in this paper.     

Global variation of outputs with respect to the variation of inputs in performance analysis; generalized RTS

Returns to scale (RTS) is an important topic in performance analysis, which helps managers to make decisions about the expansion or contraction of the operation of the DMU under assessment. But the RTS classification of DMUs gives only partial information, because it is a local notion. In this paper we extend the concept of RTS and we seek the precise relation between the proportional variation of outputs and the proportional variation of inputs. An approach is provided, which is able to determine this relation based on the parametric analysis and perturbation in linear programming.     

线性分式规划最优解集的求法

本文使用多面集的表示定理 ,导出了线性分式规划最优解集的结构 ,并给出确定全部最优解的计算步骤 .     

A branch-and-price algorithm to solve the integrated berth allocation and yard assignment problem in bulk ports

In this research, two crucial optimization problems of berth allocation and yard assignment in the context of bulk ports are studied. We discuss how these problems are interrelated and can be combined and solved as a single large scale optimization problem. More importantly we highlight the differences in operations between bulk ports and container terminals which highlights the need to devise specific solutions for bulk ports. The objective is to minimize the total service time of vessels berthing at the port. We propose an exact solution algorithm based on a branch and price framework to solve the integrated problem. In the proposed model, the master problem is formulated as a set-partitioning problem, and subproblems to identify columns with negative reduced costs are solved using mixed integer programming. To obtain sub-optimal solutions quickly, a metaheuristic approach based on critical-shaking neighborhood search is presented. The proposed algorithms are tested and validated through numerical experiments based on instances inspired from real bulk port data. The results indicate that the algorithms can be successfully used to solve instances containing up to 40 vessels within reasonable computational time.     

An efficient approach to updating simplex multipliers in the simplex algorithm

The simplex algorithm computes the simplex multipliers by solving a system (or two triangular systems) at each iteration. This note offers an efficient approach to updating the simplex multipliers in conjunction with the Bartels–Golub and Forrest–Tomlin updates for LU factors of the basis. It only solves one triangular system. The approach was implemented within and tested against MINOS 5.51 on 129 problems from Netlib, Kennington and BPMPD. Computational results show that the new approach improves simplex implementations. Project 10371017 supported by National Natural Science Foundation of China.