An Iterated Local Search for the Budget Constrained Generalized Maximal Covering Location Problem

Capacitated covering models aim at covering the maximum amount of customers’ demand using a set of capacitated facilities. Based on the assumptions made in such models, there is a unique scenario to open a facility in which each facility has a pre-specified capacity and an operating budget. In this paper, we propose a generalization of the maximal covering location problem, in which facilities have different scenarios for being constructed. Essentially, based on the budget invested to construct a given facility, it can provide different service levels to the surrounded customers. Having a limited budget to open the facilities, the goal is locating a subset of facilities with the optimal opening scenario, in order to maximize the total covered demand and subject to the service level constraint. Integer linear programming formulations are proposed and tested using ILOG CPLEX. An iterated local search algorithm is also developed to solve the introduced problem.     

Max Horn SAT and the minimum cut problem in directed hypergraphs

In this paper we consider the Maximum Horn Satisfiability problem, which is reduced to the problem of finding a minimum cardinality cut on a directed hypergraph. For the latter problem, we propose different IP formulations, related to three different definitions of hyperpath weight. We investigate the properties of their linear relaxations, showing that they define a hierarchy. The weakest relaxation is shown to be equivalent to the relaxation of a well known IP formulation of Max Horn SAT, and to a max-flow problem on hypergraphs. The tightest relaxation, which is a disjunctive programming problem, is shown to have integer optimum. The intermediate relaxation consists in a set covering problem with a possible exponential number of constraints. This latter relaxation provides an approximation of the convex hull of the integer solutions which, as proven by the experimental results given, is much tighter than the one known in the literature. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.Corresponding author.     

A node-based layered graph approach for the Steiner tree problem with revenues,budget and hop-constraints

The Steiner tree problem with revenues, budget and hop-constraints (STPRBH) is a variant of the classical Steiner tree problem. The goal is to find a tree maximizing the collected revenue, which is associated with nodes, subject to a given budget for the edge cost of the tree and a hop-limit for the distance between the given root node and any other node in that tree. In this work, we introduce a novel generic way to model hop-constrained tree problems as integer linear programs and apply it to the STPRBH. Our approach is based on the concept of layered graphs that gained widespread attention in the recent years, due to their computational advantage when compared to previous formulations for modeling hop-constraints. Contrary to previous MIP formulations based on layered graphs (that are arc-based models), our model is node-based. Thus it contains much less variables and allows to tackle large-scale instances and/or instances with large hop-limits, for which the size of arc-based layered graph models may become prohibitive. The aim of our model is to provide a good compromise between quality of root relaxation bounds and the size of the underlying MIP formulation. We implemented a branch-and-cut algorithm for the STPRBH based on our new model. Most of the instances available for the DIMACS challenge, including 78 (out of 86) previously unsolved ones, can be solved to proven optimality within a time limit of 1000 s, most of them being solved within a few seconds only. These instances contain up to 500 nodes and 12,500 edges, with hop-limit up to 25.     

Robust combinatorial optimization with variable cost uncertainty

We present in this paper a new model for robust combinatorial optimization with cost uncertainty that generalizes the classical budgeted uncertainty set. We suppose here that the budget of uncertainty is given by a function of the problem variables, yielding an uncertainty multifunction. The new model is less conservative than the classical model and approximates better Value-at-Risk objective functions, especially for vectors with few non-zero components. An example of budget function is constructed from the probabilistic bounds computed by Bertsimas and Sim. We provide an asymptotically tight bound for the cost reduction obtained with the new model. We turn then to the tractability of the resulting optimization problems. We show that when the budget function is affine, the resulting optimization problems can be solved by solving n+1$n+1$ deterministic problems. We propose combinatorial algorithms to handle problems with more general budget functions. We also adapt existing dynamic programming algorithms to solve faster the robust counterparts of optimization problems, which can be applied both to the traditional budgeted uncertainty model and to our new model. We evaluate numerically the reduction in the price of robustness obtained with the new model on the shortest path problem and on a survivable network design problem.     

Selective generalized travelling salesman problem

ABSTRACT

This paper introduces the Selective Generalized Traveling Salesman Problem (SGTSP). In SGTSP, the goal is to determine the maximum profitable tour within the given threshold of the tour’s duration, which consists of a subset of clusters and a subset of nodes in each cluster visited on the tour. This problem is a combination of cluster and node selection and determining the shortest path between the selected nodes. We propose eight mixed integer programming (MIP) formulations for SGTSP. All of the given MIP formulations are completely new, which is one of the major novelties of the study. The performance of the proposed formulations is evaluated on a set of test instances by conducting 4608 experimental runs. Overall, 4138 out of 4608 (~90%) test instances were solved optimally by using all formulations.     

A framework for participatory budget elaboration support

Participatory budgets are becoming increasingly popular in many municipalities all around the world. The underlying idea is to allow citizens to participate in the allocation of a municipal budget. Little decision support methodology is used in this type of activities, frequently based on physical meetings and some kind of voting mechanism. We describe models and methods to support the elaboration of a participatory budget. We model this problem as one of resource allocation, in which citizens attempt to maximize group satisfaction in view of multiple criteria, subject to, possibly, other constraints. Based on a negotiation approach, we propose a general methodology to deal with such a problem.     

Stochastic Programming with Multivariate Second Order Stochastic Dominance Constraints with Applications in Portfolio Optimization

In this paper we study optimization problems with multivariate stochastic dominance constraints where the underlying functions are not necessarily linear. These problems are important in multicriterion decision making, since each component of vectors can be interpreted as the uncertain outcome of a given criterion. We propose a penalization scheme for the multivariate second order stochastic dominance constraints. We solve the penalized problem by the level function methods, and a modified cutting plane method and compare them to the cutting surface method proposed in the literature. The proposed numerical schemes are applied to a generic budget allocation problem and a real world portfolio optimization problem.     

Algorithms for an Integer Multicommodity Network Flow Problem with Node Reliability Considerations

In this paper, we consider the problem of sending a set of multiple commodities from their origin to destination nodes via intermediate hubs. Each hub node is associated with a reliability function, which depends on the total flow that crosses that hub. The probability that each commodity is successfully relayed from its origin to its destination is given by the product of hub reliabilities on the commodity’s path. The problem we consider seeks to find minimum-cost commodity paths such that each commodity reaches its destination with a sufficiently large probability. We first formulate the problem as a nonlinear multicommodity network-flow problem and prove that it is strongly NP-hard. We then present two linearization techniques for this formulation, and propose a pair of lower- and upper-bounding formulations, which can then be used within an exact cutting-plane algorithm to solve the problem. Finally, we analyze the computational effectiveness of our proposed strategies on a set of randomly generated instances.     

The Arc-Item-Load and Related Formulations for the Cumulative Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) consists of finding the cheapest way to serve a set of customers with a fleet of vehicles of a given capacity. While serving a particular customer, each vehicle picks up its demand and carries its weight throughout the rest of its route. While costs in the classical CVRP are measured in terms of a given arc distance, the Cumulative Vehicle Routing Problem (CmVRP) is a variant of the problem that aims to minimize total energy consumption. Each arc’s energy consumption is defined as the product of the arc distance by the weight accumulated since the beginning of the route.The purpose of this work is to propose several different formulations for the CmVRP and to study their Linear Programming (LP) relaxations. In particular, the goal is to study formulations based on combining an arc-item concept (that keeps track of whether a given customer has already been visited when traversing a specific arc) with another formulation from the recent literature, the Arc-Load formulation (that determines how much load goes through an arc).Both formulations have been studied independently before – the Arc-Item is very similar to a multi-commodity-flow formulation in Letchford and Salazar-González (2015) and the Arc-Load formulation has been studied in Fukasawa et al. (2016) – and their LP relaxations are incomparable. Nonetheless, we show that a formulation combining the two (called Arc-Item-Load) may lead to a significantly stronger LP relaxation, thereby indicating that the two formulations capture complementary aspects of the problem. In addition, we study how set partitioning based formulations can be combined with these formulations. We present computational experiments on several well-known benchmark instances that highlight the advantages and drawbacks of the LP relaxation of each formulation and point to potential avenues of future research.     

Alternative configurations for cutting machines in a tube cutting mill

In a steel tube mill where an endless stream of steel tube is supplied from a manufacturing facility, trim waste is never made regardless of cutting patterns used and the standard cutting stock problem seems meaningless. Therefore, the continuous stock cutting problem with setup is introduced to minimize the sum of cutting time and pattern changing time to meet the given demand. We propose a new configuration of cutting machines to achieve higher production efficiency, namely the open-ended configuration as opposed to the traditional closed-ended configuration, thereby two variants of the problem are defined. We propose linear formulations for both problems using binary expansion of the number of pieces of different types in a pattern. Furthermore, we define the time for pattern change as a linear function of the number of knives used in the pattern to be more realistic. Computational studies suggest that the open-ended cutting machine may improve the production time by up to 44% and that our linear formulations are more efficient than the existing ones.     

一个约束乘积最大问题的强多项式时间算法

本文讨论了约束乘积最大问题最优解的结构特征,在此基础上给出了一个计算时间为O(n2)的强多项式时间算法,并且对于单边约束的情形给出了复杂度更低(O(nlnn))的强多项式时间算法.     

An exact procedure and LP formulations for the leader—follower location problem

The leader—follower location problem consists of determining an optimal strategy for two competing firms which make decisions sequentially. The leader optimisation problem is to minimise the maximum market share of the follower. The objective of the follower problem is to maximise its market share. We describe linear programming formulations for both problems and analyse the use of these formulations to solve the problems. We also propose an exact procedure based on an elimination process in a candidate list.     

Heuristics for multimode scheduling problems with dedicated resources

We study scheduling problems with multiple modes and dedicated resources arising in production and project management, which constitute a special class of the general multimode resource-constrained project scheduling problem. A task may require simultaneously a set of discrete, renewable resources to be processed and the processing can be performed in different modes, that is with different resource sets, processing times, or costs. Precedence constraints can exist among tasks. The total budget that can be allocated to the project can be limited. The problem consists of identifying a mode for each task and a starting time for its processing respecting precedence, resource, and budget constraints. A graph model and an iterative solution scheme are presented. Specific heuristic algorithms for the cases with and without budget constraints are given and computational results are discussed.     

The Red–Blue transportation problem

This paper considers the Red–Blue Transportation Problem (Red–Blue TP), a generalization of the transportation problem where supply nodes are partitioned into two sets and so-called exclusionary constraints are imposed. We encountered a special case of this problem in a hospital context, where patients need to be assigned to rooms. We establish the problem’s complexity, and we compare two integer programming formulations. Furthermore, a maximization variant of Red–Blue TP is presented, for which we propose a constant-factor approximation algorithm. We conclude with a computational study on the performance of the integer programming formulations and the approximation algorithms, by varying the problem size, the partitioning of the supply nodes, and the density of the problem.     

A mathematical program to refine gene regulatory networks

In this paper, we propose a methodology for making sense of large, multiple time-series data sets arising in expression analysis. Specifically, we present a mathematical model to release a reduced and coherent regulatory system given a putative regulatory network. We give two equivalent formulations of the problem and prove that the problem is NP-complete. For solving large scale instances we implemented an Ant Colony Optimization procedure. A computational analysis on randomly generated test instances validates the proposed algorithm and the computations on real data concerning Saccharomyces cerevisiae show the practicability of the proposed methodology.     

An analytic framework to develop policies for testing, prevention, and treatment of two-stage contagious diseases

In this paper we consider healthcare policy issues for trading off resources in testing, prevention, and cure of two-stage contagious diseases. An individual that has contracted the two-stage contagious disease will initially show no symptoms of the disease but is capable of spreading it. If the initial stages are not detected which could lead to complications eventually, then symptoms start appearing in the latter stage when it would be necessary to perform expensive treatment. Under a constrained budget situation, policymakers are faced with the decision of how to allocate budget for prevention (via vaccinations), subsidizing treatment, and examination to detect the presence of initial stages of the contagious disease. These decisions need to be performed in each period of a given time horizon. To aid this decision-making exercise, we formulate a stochastic dynamic optimal control problem with feedback which can be modeled as a Markov decision process (MDP). However, solving the MDP is computationally intractable due to the large state space as the embedded stochastic network cannot be decomposed. Hence we propose an asymptotically optimal solution based on a fluid model of the dynamics in the stochastic network. We heuristically fine-tune the asymptotically optimal solution for the non-asymptotic case, and test it extensively for several numerical cases. In particular we investigate the effect of budget, length of planning horizon, type of disease, population size, and ratio of costs on the policy for budget allocation.     

The one-warehouse multi-retailer problem: reformulation, classification, and computational results

We consider the one-warehouse multi-retailer problem where a warehouse replenishes multiple retailers with deterministic dynamic demands over a horizon. The problem is to determine when and how much to order to the warehouse and retailers such that the total system-wide costs are minimized. We propose a new (combined transportation and shortest path based) integer programming reformulation for the problem in addition to the echelon stock and transportation based formulations in the literature. We analyze the strength of the LP relaxations of three formulations and show that the new formulation is stronger than others. We also show that the new and transportation based formulations are equivalent for the joint replenishment problem, where the warehouse is a crossdocking facility. We extend all formulations to the case with initial inventory at the warehouse and reveal the relation among their LP relaxations. We present our computational experiments with all formulations over a set of randomly generated test instances.     

A multi-commodity flow formulation for the generalized pooling problem

The pooling problem is an extension of the minimum cost network flow problem where the composition of the flow depends on the sources from which it originates. At each source, the composition is known. In all other nodes, the proportion of any component is given as a weighted average of its proportions in entering flow streams. The weights in this average are simply the arc flow. At the terminals of the network, there are bounds on the relative content of the various components. Such problems have strong relevance in e.g. planning models for oil refining, and in gas transportation models with quality constraints at the reception side. Although the pooling problem has bilinear constraints, much progress in solving a class of instances to global optimality has recently been made. Most of the approaches are however restricted to networks where all directed paths have length at most three, which means that there is no connection between pools. In this work, we generalize one of the most successful formulations of the pooling problem, and propose a multi-commodity flow formulation that makes no assumptions on the network topology. We prove that our formulation has stronger linear relaxation than previously suggested formulations, and demonstrate experimentally that it enables faster computation of the global optimum.     

A general framework on the simulation-based optimization under fixed computing budget

In many real world problems, the design space is huge and the estimation of performance measure has to rely on simulation which is time-consuming. Hence, to find the optimal design in the design space based on the simulation output is not trivial. It is important to have a computing time allocation rule to decide how much effort to spend in sampling the design space, how many designs to sample, and how long to run for each design alternative within a given computing budget. In this paper, we propose a framework for making these allocation decisions. We use the problem of assemble-to-order (ATO) systems to demonstrate how this framework can be applied. The sample average approximation (SAA) method is chosen as the sampling method used in this application example. The numerical results show that this framework provides a good basis for allocation decisions.