Model calibration is challenging for large-scale system models with a great number of variables. Existing approaches to partitioning system models and prioritizing data acquisition rely on heuristics rather than forma...
详细信息
Model calibration is challenging for large-scale system models with a great number of variables. Existing approaches to partitioning system models and prioritizing data acquisition rely on heuristics rather than formal treatments. The sensor placement problem in physical dynamic systems points to a promising avenue for formalizing data acquisition priorities, which addresses the following question for system models: With the model at hand and pre-existing data availability on a subset of model variables, what are the (next) k model variables that would bring the largest utility to model calibration, once their data are acquired? In this study, we formalize this problem as a combinatorial optimization and adapt two solutions, the information-entropy approach and the miss-probability approach, from physical dynamic systems to system models in management sciences. Next, based on the idea of the data availability partition, we develop a third solution. The new approach can be understood from the entropy perspective and is embedded in the theoretical framework for the evaluation of side information. Our solution applies to system models of all topologies: analytical results of the optimal placement are derived for binary/multinary trees;for general (directed) tree structures, an algorithm to determine the optimal placement is devised, whose complexity is upper-bounded by O(nlog(2)(n)) for an n-variable system;for arbitrary model topologies with the presence of loops, sequential-optimal and simulated-annealing schemes are formulated. Three approaches are compared on a validating example;our solution outperforms the two alternatives. Application on a multicompartment system demonstrates the toolkit's practical use.
We propose a method to approximate the solution of online mixed-integer optimization (MIO) problems at very high speed using machine learning. By exploiting the repetitive nature of online optimization, we can greatly...
详细信息
We propose a method to approximate the solution of online mixed-integer optimization (MIO) problems at very high speed using machine learning. By exploiting the repetitive nature of online optimization, we can greatly speed up the solution time. Our approach encodes the optimal solution into a small amount of information denoted as strategy using the voice of optimization framework. In this way, the core part of the optimization routine becomes a multiclass classification problem that can be solved very quickly. In this work, we extend that framework to real-time and high-speed applications focusing on parametric mixed-integer quadratic optimization. We propose an extremely fast online optimization method consisting of a feedforward neural network evaluation and a linear system solution where the matrix has already been factorized. Therefore, this online approach does not require any solver or iterative algorithm. We show the speed of the proposed method both in terms of total computations required and measured execution time. We estimate the number of floating point operations required to completely recover the optimal solution as a function of the problem dimensions. Compared with state-of-the-art MIO routines, the online running time of our method is very predictable and can be lower than a single matrix factorization time. We benchmark our method against the state-of-the-art solver Gurobi obtaining up to two to three orders of magnitude speedups on examples from fuel cell energy management, sparse portfolio optimization, and motion planning with obstacle avoidance.
In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible sche...
详细信息
In this paper, we study a scheduling problem on a single machine, provided that the jobs have individual release dates and deadlines, and the processing times are controllable. The objective is to find a feasible schedule that minimizes the total cost of reducing the processing times. We reformulate the problem in terms of maximizing a linear function over a submodular polyhedron intersected with a box. For the latter problem of submodular optimization, we develop a recursive decomposition algorithm and apply it to solving the single machine scheduling problem to achieve the best possible running time.
During the past few years, there has been a trend to enrich traditional revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both mod...
详细信息
During the past few years, there has been a trend to enrich traditional revenue management models built upon the independent demand paradigm by accounting for customer choice behavior. This extension involves both modeling and computational challenges. One way to describe choice behavior is to assume that each customer belongs to a segment, which is characterized by a consideration set, i.e., a subset of the products provided by the firm that a customer views as options. Customers choose a particular product according to a multinomial-logit criterion, a model widely used in the marketing literature. In this paper, we consider the choice-based, deterministic, linear programming model (CDLP) of Gallego et al. (2004) [Gallego, G., G. Iyengar, R. Phillips, A. Dubey. 2004. Managing flexible products on a network. Technical Report CORC TR-2004-01, Department of Industrial Engineering and Operations Research, Columbia University, New York], and the follow-up dynamic programming decomposition heuristic of van Ryzin and Liu (2008) [van Ryzin, G. J., Q. Liu. 2008. On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2) 288-310]. We focus on the more general version of these models, where customers belong to overlapping segments. To solve the CDLP for real-size networks, we need to develop a column generation algorithm. We prove that the associated column generation subproblem is indeed NP-hard and propose a simple, greedy heuristic to overcome the complexity of an exact algorithm. Our computational results show that the heuristic is quite effective and that the overall approach leads to high-quality, practical solutions.
We show that multigrid ideas can be used to reduce the computationalcomplexity of estimating an expected value arising from a stochastic differential equation using Monte Carlo path simulations. In the simplest case ...
详细信息
We show that multigrid ideas can be used to reduce the computationalcomplexity of estimating an expected value arising from a stochastic differential equation using Monte Carlo path simulations. In the simplest case of a Lipschitz payoff and a Euler discretisation, the computational cost to achieve an accuracy of O(epsilon) is reduced from O(epsilon(-3)) to O(epsilon(-2)(log epsilon)(2)). The analysis is supported by numerical results showing significant computational savings.
Vaccination against infectious disease is hailed as one of the great achievements in public health. However, the United States Recommended Childhood Immunization Schedule is becoming increasingly complex as it is expa...
详细信息
Vaccination against infectious disease is hailed as one of the great achievements in public health. However, the United States Recommended Childhood Immunization Schedule is becoming increasingly complex as it is expanded to cover additional diseases. Moreover, biotechnology advances have allowed vaccine manufacturers to create combination vaccines that immunize against several diseases in a single injection. All these factors are creating a combinatorial explosion of alternatives and choices (each with a different cost) for public health policy makers, pediatricians, and parents/guardians (each with a different perspective). The General Vaccine Formulary Selection Problem (GVFSP) is introduced to model general childhood immunization schedules that can be used to illuminate these alternatives and choices by selecting a vaccine formulary that minimizes the cost of fully immunizing a child and the amount of extraimmunization. Both exact algorithms and heuristics for GVFSP are presented. A computational comparison of these algorithms and heuristics is presented for the 2006 Recommended Childhood Immunization Schedule, as well as several randomly generated childhood immunization schedules that are likely to be representative of future childhood immunization schedules. The results reported here provide both fundamental insights into the structure of the GVFSP models and algorithms and practical value for the public health community.
The dispersion problem arises in selecting facilities to maximize som, function of the distances between the facilities. The problem also arises in selecting nondominated solutions for multiobjective decision making. ...
详细信息
The dispersion problem arises in selecting facilities to maximize som, function of the distances between the facilities. The problem also arises in selecting nondominated solutions for multiobjective decision making. It is known to be NP-hard under two objectives: maximizing the minimum distance (MAX-MIN) between any pair of facilities and maximizing the average distance (MAX-AVG). We consider the question of obtaining near-optimal solutions. For MAX-MIN, we show that if the distances do not satisfy the triangle inequality, there is no polynomial-time relative approximation algorithm unless P = NP. When the distances satisfy the triangle inequality, we analyze an efficient heuristic and show that it provides a performance guarantee of two. We also prove that obtaining a performance guarantee of less than two is NP-hard. For MAX-AVG, we analyze an efficient heuristic and show that it provides a performance guarantee of four when the distances satisfy the triangle inequality. We also present a polynomial-time algorithm for the 1-dimensional MAX-AVG dispersion problem. Using that algorithm, we obtain a heuristic which provides an asymptotic performance guarantee of pi/2 for the 2-dimensional MAX-AVG dispersion problem.
Maximum average weight ideal problems in ordered sets arise from modeling variants of the investment problem and, in particular, learning problems in the context of concepts with tree-structured attributes in artifici...
详细信息
Maximum average weight ideal problems in ordered sets arise from modeling variants of the investment problem and, in particular, learning problems in the context of concepts with tree-structured attributes in artificial intelligence. Similarly, trying to construct tests with high reliability leads to a nontrivial maximum average weight ideal problem. This paper investigates the computationalcomplexity and shows that the general problem is NP-complete. Important special cases (e.g., finding rooted subtrees of maximal average weight), however, can be handled with efficient algorithms.
暂无评论