ABSTRACT. The basic Progressive Hedging (PH) algorithm was proposed by Rockafellar and Wets a few decades ago, but recent work with various co-authors has resulted in significant enhancements in terms of computation of bounds, parallelization, connections with dual decomposition and practical speed of primal convergence for MIPs. This talk reviews these developments.

ABSTRACT. Using the contextual setting of optimizing grid-level energy storage, we study the effect of dimensionality on the performance of different approximation methodologies. We build on the algorithmic framework of approximate dynamic programming to introduce novel machine learning strategies which overcome the curse of dimensionality inherent in scenario trees. The energy storage setting is used to create families of problems which exhibit different characteristics of the information state.

ABSTRACT. Consider the minimization of a nonlinear function involving expected values, i.e., the composition of two stochastic functions f and g. We propose a stochastic compositional gradient descent (SCGD) method that updates based on noisy gradients of f and g. We prove that SCGD converges a.s. to an optimal solution. The convergence involves the interplay of two iterations with different time scales. Rate of convergence are provided for convex and strongly convex problems, respectively. The proposed SCGD methods may find wide application in learning, estimation, dynamic programming.

ABSTRACT. We discuss our computational experience with an algorithm for solving two-stage stochastic programs with mixed integer recourse. The algorithm generalizes Benders' approach and is based on dynamic construction of the value function of the second stage problem. As in the classical algorithm, the master problem is solved with a lower approximation to the true value function and the subproblem is to determine whether that approximation is exact tat the current iterate. Implementing this algorithm efficiently presents many challenges in practice. The talk will describe these challenges and present computational results.

ABSTRACT. In practice, any performance analysis in stochastic modeling is subject to input model uncertainty. In this presentation we adopt a nonparametric viewpoint to assess such uncertainty, and consider worst-case analysis in which the uncertainty is represented by constraints in an optimization over the input probability distribution. For systems that involve generating i.i.d. input replications, such as queueing models, the objective function of such optimization is nonlinear with respect to the input distribution. Our main contribution consists of the design of a simulable gradient estimator and convergence analysis for a stochastic analog of the conditional gradient method that approximates the local optima of such worst-case optimizations.

ABSTRACT. In this paper we are concerned with stochastic temporal manufacturing processes with work-in-process inventories in which multiple products are produced from raw materials and parts. The processes may be composed of subprocesses, which, in turn may be either composite or atomic, i.e., a machine on a manufacturing floor. We assume that machines' throughput is stochastic and so are work-in-process inventories and costs. We consider the problem of optimizing the process, that is finding throughput expectation setting for each machine at each time point over the time horizon as to minimize the total cost of production subject to satisfying the production demand with a requested probability. To address this problem, we propose an efficient iterative heuristic algorithms that is based on (1) producing high quality candidate machine settings based on deterministic approximation of the given stochastic problem, and (2) running stochastic simulations to find the best machine setting out of the produced candidates, using optimal simulation budget allocation methods. We conduct an experimental study which shows that our algorithm significantly outperforms the the four popular simulation-based optimization algorithms used in the study.

ABSTRACT. For roughly six decades since the seminal paper of Robbins and Monro (1951), Stochastic Approximation has dominated the landscape of algorithms for solving root finding and optimization problems with Monte Carlo observable functions. Recently, however, inspired by the rise in parallel computing and advances in nonlinear programming methods, there has been increasing interest in alternative sampling-based frameworks. Such frameworks are convenient in that they use an existing recursive method, e.g., quasi-Newton or trust-region recursion, with embedded Monte Carlo estimators of objects appearing within the recursion. In this talk, after reviewing some recent results on optimal sampling rates, we consider the question of how to adaptively sample within stochastic recursions. Specifically, we will demonstrate that a simple adaptive scheme that has deep connections to proportional-width sequential confidence intervals endows stochastic recursions with convergence rates that are arbitrarily close to being optimal.

ABSTRACT. We introduce the Row-Partition Branching Method for set partitioning and set packing problems. Branching is accomplished by selecting a subset of the rows of the problem that must be covered and partitioning the variables according to the number of rows of the subset that each variable covers. The method can be viewed as a generalization of the well-known Ryan-Foster branching scheme. We discuss implementation issues associated with our method and show through computational experiments that the method is competitive with other branching methods for set partitioning and packing problems.

ABSTRACT. In this talk, we smash together ideas that have proven to be effective at exploiting symmetry with strong cutting planes for mixed integer programs. We hope that the computational results will be earth-shattering.

ABSTRACT. We study a variant of the capacitated vehicle routing problem where the cost over each arc is defined as the product of the arc length and the weight of the vehicle when it traverses that arc. We propose two new mixed integer linear programming formulations for the problem: an arc-load formulation and a set partitioning formulation based on q-routes with additional constraints. A family of cycle elimination constraints are derived for the arc-load formulation. We show that the arc-load formulation with the new cycle elimination constraints gives the same LP bound as the set partitioning formulation based on 2-cycle-free q-routes, which is stronger than the LP bound given by the two-index one-commodity flow formulation. We propose a branch-and-cut algorithm for the arc-load formulation, and a branch-cut-and-price algorithm for the set partitioning formulation strengthened by additional constraints. Computational results on instances from the literature demonstrate that a significant improvement can be achieved by the branch-cut-and-price algorithm over other methods.

ABSTRACT. This paper determines the trends in energy use of the manufacturing industries across Colombian departments over the period 2005-2013, this empirical study examines energy efficiency based on two Malmquist data envelopment analysis model. The results show considerable variation in energy efficiency across Colombian departments. Results from the Malmquist data envelopment analysis model suggest that Colombian manufacturing industries have an excellent potential to improve energy use and several manufacturing industries across Colombian departments have experienced gains in productivity, a growth in efficiency, a better balance between inputs and outputs and scale production and improvements in innovation through new technologies. Second-stage panel data techniques show that higher energy prices, exportations and productivity lead to higher energy efficiency, while higher presence of energy intensive sectors and small and medium enterprises across Colombian departments reduce energy efficiency. The findings of this study show that different energy policies should apply across Colombian departments and that they should encourage the importance of energy efficiency in order to improve it, especially in small and medium enterprises and energy intensive sectors.

ABSTRACT. With less emission, higher efficiency, and quicker responsibility and flexibility than other types of power plants, combined-cycle units, as gas-fired generators, have been gaining more and more shares of the total U.S. power generation. As a result, a critical problem arises as unit commitment self-scheduling for the generation company (GENCO) owning combined-cycle units, in order to maximize the total profit. Meanwhile, due to the inherent uncertainties in the electricity market (including unexpected outage of generators and transmissions, fluctuating electricity demand, and intermittent renewable energy output), the information on electricity price is limited. In this presentation, we present a data-driven stochastic self-scheduling approach for the combined-cycle unit, utilizing a significant amount of historical day-ahead price data. In this approach, the detailed distribution of the uncertain parameter is not required and the conservatism is adjustable based on the amount of the data.

ABSTRACT. We develop mixed-integer nonlinear optimization model (MINLP) for the design and operation of natural gas transmission networks in a multi-period setting. Our model determines the locations and the timing of pipeline and compressor station installations in the network along with purchasing quantity and gas flows in each period. We solve our model using the Bonmin algorithm available through COIN-OR project on the NEOS Server and examine the optimality of results via constraint and integrality relaxations.

In our computational studies, we generate test instances based on realistic network structure and data related to natural gas network in Turkey and other published data. Our analysis includes a close look into into changes in network configuration and operations based on changes in design and operation cost parameters and the number of periods in the planning horizon.

ABSTRACT. Modeling languages for formulating and analyzing optimization problems are essentially declarative, in that they are founded on a symbolic description of a model’s objective function and constraints rather than a procedural specification of how a problem instance is to be generated and solved. Yet successful optimization modeling languages have come to offer many of the same facilities as procedural, high-level programming languages, in two ways: by extension of their syntax to interpreted scripting languages, and by exposure of their functions through application programming interfaces (APIs). How can scripting and APIs benefit the user of a declarative language, and what do they offer in comparison to modeling exclusively in a general-purpose language? This presentation suggests a variety of answers, using the AMPL system’s scripting features and APIs to present a variety of examples.

ABSTRACT. Second-order cone programming (SOCP) problems have a wide range of applications and can be efficiently solved by interior-point methods. While it is possible to express SOCP problems in a variety of ways using high-level constructs of algebraic modeling languages, solvers usually accept specific forms of such problems or perform only rudimentary transformations. We describe the design and implementation of a framework for automatic reformulation of SOCP problems into forms recognized by solvers. The system allows users to express problems in forms which are natural for their applications rather than imposed by solver limitations. This work is based on the earlier work by Erickson (2013), and is applicable to existing AMPL solvers with minimal modifications to the solver interface code. To achieve this, the reformulation framework integrates seamlessly with the AMPL Solver Library (ASL), applying transformations to the problem and the solution transparently both for the solver and the modeler. Detection and transformation of supported constructs is performed by recursive traversal of acyclic expression graphs. We give a number of examples showing transformations performed by the system.

ABSTRACT. This presentation describes modeling extensions in Pyomo that support the formulation and analysis of bilevel programs. These modeling extensions strongly leverage Pyomo's object-oriented design and intrinsic support for modeling with blocks. We describe a bilevel solver that can be generically be applied to an important class of mixed-integer linear bilevel programs.

ABSTRACT. “Flat” algebraic representations force modelers to explicitly convert or relax high-level constructs, which can obscure much of the structure in the model. We will show how high-level non-algebraic modeling constructs in Pyomo can be coupled with automated model transformations to improve model clarity and abstraction. This allows modelers to explicitly apply transformations that link the structured model to a solver, thereby separating the core model from subsequent reformulation decisions.

ABSTRACT. SC:David Bergman

The most common approach to generate cuts in integer programming is to derive them from the linear programming relaxation. We study the alternative approach of extracting cuts from a discrete relaxation known as relaxed binary decision diagrams, focusing on 0-1 integer programs. The general idea of the algorithm is to generate a cut that defines a facet of the convex hull of this discrete relaxation and then refine the relaxation in a guided manner in order to strengthen the cut. We provide computational evidence that this algorithm generates strong cuts.

ABSTRACT. Techniques for solving optimization problems naturally prioritize the value of an objective function, typically producing a single solution. While this is essential from the optimality point of view, there are scenarios where it may be advantageous to consider multiple solutions, as distinct as possible from one another. Unfortunately, constraint-based techniques that can be used to generate diverse solutions are designed for satisfaction problems. They do not assess objective quality. In this work, we tackle this issue with a generic paradigm for assessing both solution diversity and solution quality, that can be implemented in most existing solvers. As there is no requirement for the initial solution to be optimal, there is therefore no theoretical restriction on solving large problems, using for instance Large Neighborhood Search. We show that our technique can be specialized to produce diverse solutions of high quality in the context of over-constrained problems. Furthermore, our paradigm allows us to consider diversity from a different point of view, based on generic concepts expressed by global constraints. Our experiments yield encouraging computational results.

ABSTRACT. Session Chair: David Bergman A new research stream in optimization considers the use of multivalued decision diagrams to encode discrete relaxations of combinatorial problems. These relaxations can then be used, for example, to provide novel optimization bounds in a branch-and-bound framework. In this talk we discuss how to strengthen the optimization bound for cases where multiple decision diagram relaxations are considered, each representing a particular substructure of the problem. For instance, in a nurse scheduling problem each decision diagram could potentially encode the set of feasible shifts of a nurse, which are then related by additional linking constraints. Our proposed technique changes the cost structure of each decision diagram by incorporating dual information of the linking constraints in the form of Lagrangian multipliers. Computational experiments show that the strengthening techniques have a great impact on the bound and can improve solving times substantially.

ABSTRACT. We propose a new first-order augmented Lagrangian algorithm ALCC for solving convex conic programs of the form min{rho(x)+gamma(x): Ax-b in K, x in chi}, where rho and gamma are closed convex functions, and gamma has a Lipschitz continuous gradient, A is mxn real matrix, K is a closed convex cone, and chi is a "simple" convex compact set such that optimization problems of the form min{rho(x)+|x-x0|_2^2: x in chi} can be efficiently solved for any given x0. We show that any limit point of the primal ALCC iterates is an optimal solution of the conic convex problem, and the dual ALCC iterates have a unique limit point that is a Karush-Kuhn-Tucker (KKT) point of the conic program. We also show that for any epsilon>0, the primal ALCC iterates are epsilon-feasible and epsilon optimal after O(log(1/epsilon)) iterations which require solving O(1/epsilon log(1/epsilon)) problems of the form min{rho(x)+|x-x0|_2^2: x in chi}.

ABSTRACT. The stable principal component pursuit (SPCP) is a non-smooth convex optimization problem, the solution of which enables one to reliably recover the low rank and sparse components of a data matrix which is corrupted by a dense noise matrix, even when only a fraction of data entries are observable. In this paper, we propose a new algorithm for solving SPCP. The proposed algorithm is a modification of the alternating direction method of multipliers (ADMM) where we use an increasing sequence of penalty parameters instead of a fixed penalty. The algorithm is based on partial variable splitting and works directly with the non-smooth objective function. We show that both primal and dual iterate sequences converge under mild conditions on the sequence of penalty parameters. To the best of our knowledge, this is the first convergence result for a variable penalty ADMM when penalties are not bounded, the objective function is non-smooth and its sub-differential is not uniformly bounded. Using partial variable splitting and adopting an increasing sequence of penalty multipliers, together, significantly reduce the number of iterations required to achieve feasibility in practice. Our preliminary computational tests show that the proposed algorithm works very well in practice, and outperforms ASALM, a state of the art ADMM algorithm for the SPCP problem with a constant penalty parameter.

ABSTRACT. We describe some new approximate versions of the alternating direction method of multipliers (ADMM) algorithm for convex optimization, which may be viewed as a decomposition variant of the classical augmented Lagrangian method. The approximation acceptance criteria of these new ADMM versions are more readily testable than those known previously, but convergence to an optimum can still be proved.

ABSTRACT. Integer programming is the (not very appealing or descriptive) name for optimization models and algorithms in which some variables are required to have integer values. Planning and operational problems in energy, finance, health, manufacturing, military, transportation, and in almost any imaginable domain where decisions are made, are formulated and solved using integer programming. For example, most Fortune 500 companies use integer programming in some aspects of their business. Currently available software is capable of solving models with thousands, and sometimes millions, of variables and constraints. We will discuss some integer programming models whose solutions have had big impact in solving important problems, and present recent progress that has made it possible to solve very large instances and to obtain provably good solutions quickly. We’ll close by speculating on future advances in methodology and applications.

ABSTRACT. The origins of Stochastic Programming are usually traced to a 1955 paper under the label of "Linear Programming under Uncertainty." From this point of view, SP is an outgrowth of Linear Programming. While this viewpoint has been exploited extensively in the literature, few algorithms exploit the ties of SP with Approximate Dynamic Programming, and Simulation. In this tutorial, we will highlight the computational role of ADP-type value function approximations in SP, as well as the use of sampling and replications as in Simulation. We will discuss how low variance solutions can be obtained by using replicated value functions for SP. While most of the computational results to date have been in the two stage case, algorithmic extensions to the multistage will also be presented.

ABSTRACT. Options portfolio optimization has been seldom studied in the portfolio optimization field. Existing, and limited literature only incorporates European options when constructing portfolios. We propose approximate dynamic programming algorithms for both European and American options portfolio with piecewise linear functions and recursive progressive hedging method, respectively. Computational experiments show good results for a very difficult problem.

ABSTRACT. Many sequential decision problems can be formulated as Markov Decision Processes (MDPs) where the optimal value function (or cost–to–go function) can be shown to satisfy a monotone structure in some or all of its dimensions. When the state space becomes large, traditional techniques, such as the backward dynamic programming algorithm (i.e., backward induction), may no longer be effective in finding a solution within a reasonable time frame, and thus, we are forced to consider other approaches, such as approximate dynamic programming (ADP). We propose a provably convergent ADP algorithm called Monotone–ADP that exploits the monotonicity of the value functions in order to increase the rate of convergence. In this paper, we describe a general finite–horizon problem setting where the optimal value function is monotone, present a convergence proof for Monotone–ADP under various technical assumptions, and show numerical results for a family of optimal stopping problems, with the largest being a seven– dimensional problem with nearly 20 million states. The empirical results indicate that by taking advantage of monotonicity, we can attain high quality solutions within a relatively small number of iterations, using up to an order of magnitude less computation than is needed to compute the optimal solution exactly.

ABSTRACT. The United States Army uses Vendor Managed Inventory (VMI) replenishment to manage resupply operations while engaged in a combat environment; upper-echelon organizations (e.g., a brigade) maintains situational awareness regarding the inventory of lower-echelon organizations (e.g., battalions and companies). The Army is interested in using a fleet of cargo unmanned aerial vehicles (CUAVs) to perform resupply operations. We formulate an infinite horizon, discrete time stochastic Markov decision process model of the military inventory routing problem with direct delivery, the objective of which is to determine an optimal unmanned tactical airlift policy for the resupply of geographically dispersed brigade combat team elements operating in an austere, Afghanistan-like combat situation. An approximate policy iteration algorithm with instrumental variables Bellman error minimization is used to determine near-optimal policies. Within the least-squares temporal differences policy evaluation step, we use a modified version of the Bellman equation that is based on the post-decision state variable. Computational results are obtained for examples based on representative resupply situations experienced by the United States Army in Afghanistan.

ABSTRACT. In city logistics, challenges for courier, express and parcel service providers increase. E.g., service providers deal with stochastic customer requests. The requests appear during the day and are not known in the beginning of the planning. Due to working hour restrictions, not every request can be served the same day. So, requests can be confirmed or postponed. Postponed requests are served the following day. Objective is to maximize the number of confirmations per day. For this problem, decisions contain both routing and confirmations and have impact on the current and the following service period.

To anticipate possible future requests, we apply Value Function Approximation (VFA). VFA approximates the expected number of future confirmation regarding a decision outcome. VFA selects decisions maximizing the sum of immediate and expected future confirmations. Because of multi-periodicity and the vast number of possible customer locations, the problem dimensionality is high and has to be reduced to apply VFA. To remain a high level of relevant information, we introduce a dynamic lookup table (DLT). The DLT adapts the level of detail to the problem specifics. For the given problem, DLT outperforms all traditional LT approaches in terms of solution quality and allows efficient and effective approximation.

ABSTRACT. We propose a new paradigm for data-driven decision making in uncertain environments. Through our new theoretical and computational advances in disparity-based stochastic optimization methods, we show that the proposed approach offers both efficiency and robustness against model misspecification and real-life data issues such as contamination. It also facilitates the quantification of uncertainty in decisions due to historical data/input stream variability. We establish the consistency and convergence rates of the new method, and compare it to the current practice of estimating probability distribution models using the maximum likelihood method and then performing stochastic optimizations with the estimated models as input. Through a set of real-life examples, we show that the new method is both asymptotically efficient and robust, while the current approach can suffer from significant biases and variances due to model misspecification and data contamination.

ABSTRACT. The ``weakly coupled dynamic program'' describes a broad class of stochastic optimization problems in which multiple controlled stochastic processes evolve independently but subject to a set of linking constraints imposed on the controls. One feature of the weakly coupled dynamic program is that it decouples into lower-dimensional dynamic programs by dualizing the linking constraint via the Lagrangian relaxation, which also yields a bound on the optimal value of the original dynamic program. Together with the Lagrangian bound, we utilize the information relaxation approach that relaxes the non-anticipative constraint on the controls to obtain a tighter dual bound. We also investigate other combinations of the relaxations and place the resulting bounds in order. To tackle large-scale problems, we further propose a computationally tractable method based on information relaxation, and provide insightful interpretation and performance guarantee. We implement our method and demonstrate its use on two classes of problems.

ABSTRACT. We develop derivative free algorithms for optimization contexts where the objective function is observable only through a stochastic simulation. The algorithms we develop follow the trust-region framework where a local model is constructed, used, and updated as the iterates evolve through the search space. The salient feature of our algorithms is the incorporation of adaptive sampling to keep the variance (statistical error) and the squared bias (model error) of the local model in lock step, in a bid to ensure optimal convergence rates. Such balancing is accomplished dynamically, through careful estimation of errors using function estimates at visited points. We will discuss convergence and efficiency.

ABSTRACT.  

In this talk, I will present an overview of some recent research solving large-scale Unit Commitment problems from the electrical grid, with a focus on parallel algorithms. We consider a planning model that represents the Western Energy Coordinating Council grid, modeled as a mixed-integer linear program (MILP) with hundreds of thousands of variables and constraints for the deterministic version. We also consider a two-stage stochastic optimization extension of the deterministic model.  To solve the deterministic models, we propose a parallelization strategy featuring coordinated concurrent MILP tree search. On a cluster of 16 IBM Power7 machines, our implementation achieves an average 12 times speedup.  We are also able to solve all deterministic instances within an hour on a single Power7 machine. To solve the stochastic models, we propose a parallelization strategy based on progressive hedging (PH) that features MILP subproblems and guided MILP solves for finding feasible solutions.

ABSTRACT. The restoration process of the bulk power system after a partial or complete blackout relies on generating units with black- start capabilities. In the normal build-up restoration process, the system is sectionalized first into a set of subsystems in which the generators are started afterwards. Due to the complexity of the restoration process, the sectionalization and generator sequencing problems have been studied separately in the literature, ignoring their interlocking connections, which may lead to a sub-optimal restoration plan for the overall restoration process. In this work, we integrate the two problems into a single model that minimizes the restoration duration for the overall system. We propose an integer programming formulation to model the sectionalization problem as a graph partition problem with connectivity constraints. A continuous-time representation of the generator start-up sequencing problem is used based on a semi-infinite programming formulation. Our case study shows that the proposed model can achieve a global optimization solution effectively.

ABSTRACT. Motivated by the intermittency of renewable energy, we propose a multi-stage stochastic integer programming model in this talk to address unit commitment problems under uncertainty, for which we construct several classes of strong inequalities by lifting procedures to strengthen the original formulation. Our preliminary computational experiments show encouraging results.

ABSTRACT. Uncertainties bring many reliability issues to the power system planning and operations. The stochastic programming has been proposed to solve the unit commitment problem with uncertainty. However, scalability remains as a challenge to large power systems. In this work, a set of reliability cuts are identified based on the polyhedral structure taking advantages of the unique power system characteristics. The necessary and sufficient condition for a feasible dispatch in the power grid is shown and then the extreme rays of the dual cone (polyhedron structure) are characterized. The extreme rays are determined by the combinatorial selection of the buses and the transmission lines. The crucial selections of the buses and the transmission lines are carried out by off-line study. The test results are presented on a RTS96 73-bus system. The problem is formulated as a 24-period security-constrained unit commitment problem with N-1 generator failure contingency reliability requirement. The proposed method is examined and compared with the stochastic programming approach. The preliminary test results show that the proposed method improves the computational efficiency significantly.

ABSTRACT. Weather elements such as temperature and solar radiation play a crucial role in renewable power production as well as power consumption. In this paper, we address a power producer’s objective of risk management for its weather, price and production risk exposures. We investigate the extent of natural hedge embedded in the dependence of power production using renewable energy sources and power consumption. We further develop explicit cross hedges for the risk management objectives of a renewable power producer using weather derivatives.

ABSTRACT. We present a linear mixed integer programming model for the time-dependent heterogeneous green vehicle routing and scheduling problem (GVRSP) with the objective of minimizing total carbon dioxide emissions and weighted tardiness. Instead of discrete time intervals, the proposed model takes the traveled distances of arcs in different time periods as decision variables to determine the travel schedules of vehicles. We propose an exact dynamic programming method to calculate the optimal discrete departure/arriving time for the GVRSP. The dynamic programming method significantly reduces the computational complexity of the GVRSP when applying existing heuristic algorithms to solve large-sized problems. A genetic algorithm with dynamic programming (GA-DP) is developed to solve the formulated problem. Computational experiments are carried out to study the efficiency of the proposed hybrid solution approach with promising results.

ABSTRACT. In the swap-body vehicle routing problem (SBVRP), a homogeneous fleet of an unlimited number of trucks, semi-trailers, and swap-bodies is used to serve a set of customers. Some customers may only be served by trucks due to a set of location-dependent accessibility constraints. Four types of operations (park, pickup, swap, exchange) can be performed at designated swap locations. Each of these operations has a different cost. The objective function has fixed and variable costs for vehicle components involving service and swap-action times. We present a survey of related problems and propose a local search heuristic for the SBVRP. Computational results earned a place in the finals of a competition against 27 teams of international researchers.

ABSTRACT. In this paper an unequal area Cyclic Facility Layout Problem (CFLP) is studied. Dynamic and seasonal nature of the product demands results in the necessity for the considering the CFLP where product demands as well as the departmental area requirements are changing from one period to the next one. Since the CFLP is NP-hard, we propose a Simulated Annealing (SA) metaheuristic with a dynamic temperature update schedule to solve the CFLP. In the SA algorithm, both relative department locations and dimensions of departments are determined simultaneously. We benchmark the performance of the proposed SA algorithm with earlier approaches on different test problems from the literature and find out that the SA algorithm is promising.

ABSTRACT. Forecasting the demands for aircraft spare parts suffers from extremely low accuracy because most parts’ demands are intermittent and erratic. Forecasting errors often exceed 50% (Mean Absolute Deviation). For the same reasons, insufficient historical data exists to properly select a forecasting heuristic. Typically, forecasters employ heuristics selected by studying historical demands of many different aircraft parts. However, this approach overlooks the sizes of historical data sets (sometimes only a few failures per part) and the inherent differences in the failure rates (and thus demand rates) of each different type of part. In a new approach, basic engineering data about the probabilities of failure (over time) can be combined with Monte Carlo simulations to improve forecasting heuristic selection and, thus, to improve accuracy. The Monte Carlo simulations test the performance of a range of forecasting heuristics against possible in-service part failure/replacement cycles, based upon Weibull models of parts’ likely failure rates. These results may be tabulated for forecasting professionals to select the appropriate heuristic for any given part based upon the engineering estimates of that part's failure rate. Extensive simulations were performed and example tables were developed. Samples are presented, along with techniques for application to a particular fleet of aircraft.

ABSTRACT. Scheduling problems have historically considered time-based objective functions (e.g., completion time, tardiness, workload, changeover time). Over the last years, due to the need of including energy and environmental factors, the overall scheduling problem has been generally extended to the multi-objective case, including both energy and environment-related costs (e.g., peak-power load, energy consumption, associated car- bon footprint) [2].

This work considers a flexible flow-shop environment where m machines are employed to execute n jobs. Each activity in a job has a set of possible execution modes with different trade-off between energy consumed and processing time. Moreover, global energy consumption may also depend on the possibility to of switching-off the machines during the idle periods. The goal is to widen the knowledge about performance capa- bilities, in particular the ability of efficiently finding high quality approximations of the solution Pareto front.

We explore the development of innovative meta-heuristic algorithms for solving the proposed multi-objective scheduling problem. In particular, we consider stochastic lo- cal search (SLS) algorithms [3] in line with the large neighborhood search approaches proposed in [8, 6, 7]. Such procedures are typically composed of a number of different components, each of which should contribute to the final solving capabilities of the al- gorithm. In this work, we empirically analyze the effects of the algorithmic components for the proposed problem; the analysis is done using some benchmarks and case stud- ies taken from the literature [1, 2, 5, 4], targeted at finding energy-efficient scheduling solutions with makespan and energy consumption as objectives.

References [1] Dai, M., Tang, D., Giret, A., Salido, M.A., Li, W.: Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer- Integrated Manufacturing 29(5), 418 – 429 (2013), http://www.sciencedirect. com/science/article/pii/S0736584513000318 [2] Fang,K.,Uhan,N.,Zhao,F.,Sutherland,J.W.:Anewapproachtoschedulinginmanufactur- ing for power consumption and carbon footprint reduction. Journal of Manufacturing Systems 30(4), 234 – 240 (2011), http://www.sciencedirect.com/science/article/ pii/S0278612511000690, selected Papers of 39th North American Manufacturing Re- search Conference [3] Hoos, H.H., Stu ̈tzle, T.: Stochastic Local Search. Foundations and Applications. Morgan Kaufmann (2005) [4] Jiang,Z.,Zuo,L.,E,M.:Studyonmulti-objectiveflexiblejob-shopschedulingproblemcon- sidering energy consumption. Journal of Industrial Engineering and Management 7(3), 589 – 604 (2014), http://jiem.org/index.php/jiem/article/view/1075 [5] Luo, H., Du, B., Huang, G.Q., Chen, H., Li, X.: Hybrid flow shop scheduling considering machine electricity consumption cost. International Journal of Production Economics 146(2), 423 – 439 (2013), http://www.sciencedirect.com/science/article/pii/ S0925527313000467 [6] Oddi, A., Rasconi, R., Cesta, A., Smith, S.F.: Iterative flattening search for the flexible job shop scheduling problem. In: IJCAI 2011, Proceedings of the 22nd International Joint Confer- ence on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011. pp. 1991–1996 (2011), http://ijcai.org/papers11/Papers/IJCAI11-332.pdf [7] Pacino,D.,Hentenryck,P.V.:Largeneighborhoodsearchandadaptiverandomizeddecompo- sitions for flexible jobshop scheduling. In: IJCAI 2011, Proceedings of the 22nd International Joint Conference on Artificial Intelligence, Barcelona, Catalonia, Spain, July 16-22, 2011. pp. 1997–2002 (2011), http://ijcai.org/papers11/Papers/IJCAI11-333.pdf [8] Schaus, P., Hartert, R.: Multi-objective large neighborhood search. In: Schulte, C. (ed.) Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, vol. 8124, pp. 611–627. Springer Berlin Heidelberg (2013), http://dx.doi.org/10. 1007/978-3-642-40627-0_46

ABSTRACT. High Performance Computing centers play a key role in the world ICT infrastructure. The ever-growing need for computing power, coupled with tight energy constraints, is pushing HPC center managers to adopt complex, heterogeneous, architectures to process incoming jobs as efficiently as possible. Employing Combinatorial Optimization for improving the operations of such complex systems is both extremely appealing and extremely challenging: the difficulty stems from a multitude of factors, including the size and complexity of the target systems, the need to maintain response times as low as those of currently used heuristics, the unwillingness of many managers to invest in this kind of technology. In this work, we present an approach based on Constraint Programing and MILP to perform workload dispatching on the EURORA supercomputer, installed at the CINECA computing center in Italy. Our approach relies on decomposition techniques to maintain scalability and low response times, while freely accessible solvers are used instead of more powerful commercial tools to increase the appeal for HPC center managers. The approach is compared against a previous system of ours, which was based on ILOG CP Optimizer and proved already capable to beat a state of the art dispatcher (Portable Batch System -- PBS).

ABSTRACT. To be deemed safe for operation, safety-critical Real-Time Embedded Systems (RTES) must satisfy strict performance requirements constraining how quickly the system must react to external inputs. Stress testing such systems is crucial, because their correct behavior has to be ensured even under the worst operating conditions. In this presentation, we address the derivation of worst case schedules for RTES tasks with respect to three common classes of performance requirements, namely task deadlines, response time, and CPU usage. Specifically, we re-express this worst-case analysis as a Constrained Optimization Problem (COP) that mimics a task priority-based preemptive scheduler over the space of system inputs. The solutions to this COP are input combinations that maximize the chance to violate performance requirements, thus defining a worst case scenario. These combinations in turn characterize stress test cases that once executed push the system to its worst performance. Our preliminary validation in several case studies showed that the COP effectively generates test cases maximizing deadline misses, response time, and CPU usage. Ongoing and future work on this topic involves combining Constraint Programming with Evolutionary Algorithms in order to efficiently generate highly diverse solutions, i.e., test cases stressing the system in different worst-case scenarios.

ABSTRACT. We consider the problem of scheduling patients in a medical clinic. Patients must see one of the clinic's doctors and some must also receive a scan prior to seeing the doctor. Complications of the problem include stochastic processing times and model selection based on the decision problem of interest. We present models as well as computational results based on both integer programming and approximation algorithms approaches.

ABSTRACT. We consider regularized mixed-membership matrix factorization, where one factor matrix can have a limited number of non-zero entries, and the other has simplex constraints. This provides a mixed-membership representation for each column of the original matrix with sparse mixing components. This problem is known to be NP-Hard, and occurs in a wide variety of contexts, including computational biology, recommendation systems, and image processing. We transform the original biconvex optimization problem into a mixed-integer linear program, and show that moderate-size problems can be solved to global optimality, and that approximate solutions to larger problems can be found via a sequential refinement approach.

ABSTRACT. Scientists use laboratory experiments to find molecules with desirable properties, e.g., that make efficient solar cells; or that cure cancer. The success of such a search hinges on making good decisions about which experiments to perform. We show that machine learning and optimization, together in an optimal learning framework, can be used to choose good experiments, and to reach experimental goals reliably with fewer experiments. We describe how these techniques were used successfully to find minimal peptide substrates for a pair of protein-modifying enzymes, with application to novel biochemical sensors.

ABSTRACT. We present a scalable solver, PIPS-IPM, that computes in operationally compatible time the optimal electricity dispatch under uncertainty. PIPS-IPM is a hybrid MPI-SMP parallel solver for stochastic programming problems that uses an interior point method and implements specialized distributed-memory linear algebra. We also present a study of the effects of the wind correlations on the optimal dispatch in the State of Illinois power grid systems. The simulations indicate that a gap in the dispatch costs and market inefficiencies can occur as the result of improper estimation and use of wind correlations.

ABSTRACT. We discuss scenario generation processes for modeling load and renewables power output for the ISO-NE system, based on epi-spline optimization technology. The resulting scenarios are used as input to a parallel scenario-based decomposition scheme based on the progressive hedging algorithm, which is capable of solving large-scale, real-world stochastic unit commitment instances in less than 20 minutes of wall clock time. We also analyze cost savings of stochastic versus deterministic unit commitment on the ISO-NE system.

Please schedule in session with David Woodruff and Carl Laird talks in the same track.

ABSTRACT. In this paper, we investigate the restoration of an interdicted power grid under limited resources for recovery by backup generation facilities. In case of maximum disruptive attack plans with limited offensive resources, we propose an optimized plan by backups and line switching to recover the power grid. We present a two stage stochastic programming and a robust optimization model for this problem. We present efficient computational methods to solve the equivalent mixed integer programs of the two-stage stochastic and robust optimization models.

ABSTRACT. In the AC optimal power flow (ACOPF) problem is a nonlinear programming formulation that seeks to find optimal setpoints for system generators to minimize the operating cost while meeting load demands throughout the transmission system. However, system operators would also like to protect themselves against potential system failure. In this presentation, we formulate a stochastic ACOPF problem where each contingency scenario considers failure in an individual transmission element. We solve this problem efficiently using a parallel nonlinear interior-point method based on the Schur-complement decomposition of the linear KKT system solved at each iteration.

ABSTRACT. Stochastic variational inequalities (SVIs) model a variety of equilibrium and optimization problems with uncertain data. Often the true formulation of these problems cannot be solved directly and a suitable approximation is solved instead. In this paper we consider the use of a sample average approximation (SAA), which replaces the true function in the SVI by a sample average function. We examine methods for computing confidence regions and confidence intervals for the true solution to the SVI using the SAA solution and sample data. The methods are applied to a stochastic Cournot-Nash equilibrium problem of moderate size, with sensitivity analysis performed for the choice of two parameters that are needed in the degenerate case.

ABSTRACT. Stochastic programming problems are very difficult problems as they involve optimization as well as uncertainty analysis. Algorithms for solving large scale nonlinear stochastic programming problems are very few in number, as are the engineering applications of these problems. This talk introduces BONUS algorithms for large scale stochastic nonlinear problems for both open equation systems and black box models. Real world applications of these algorithms in the areas of energy and environmental engineering are also detailed.

ABSTRACT. We study a class of chance-constrained two-stage stochastic optimization problems where second-stage feasible recourse decisions incur additional cost. This problem class can be considered as generalizing both chance-constrained and traditional two-stage stochastic programs. In addition, we propose a new model, where "recovery" decisions are made for the infeasible scenarios to obtain feasible solutions to a relaxed second-stage problem. We develop decomposition algorithms with specialized optimality and feasibility cuts to solve this class of problems. Computational results on a chance-constrained resource planning problem indicate that our algorithms are highly effective in solving these problems compared to a mixed-integer programming reformulation and a naive decomposition method.

ABSTRACT. In this paper, we consider a Stackelberg game in a network where a leader interdicts a subset of arcs given a certain budget, and maximizes the worst-case objective of a follower who seeks a path with a sufficiently short distance under random traveling cost on each arc. In particular, we consider the follower being risk averse, who aims to restrict the risk of traveling between origin and destination nodes for a distance that is longer than a given threshold value. We analyze two variants of the stochastic shortest path interdiction problem depending on the follower’s ability of reacting to the uncertainty. We propose branch-and-cut algorithms and employ linearization techniques for solving the bilevel programs formulated for the two variants. We demonstrate the computational efficacy by testing a diverse set of network instances.

Session Chair: Dr. Siqian Shen

ABSTRACT. We investigate two min-max distributionally robust variants of appointment scheduling, which assigns arrival time to a fixed sequence of appointments under random service durations and appointment ``no-shows'', of which the joint distribution is unknown but bounded by a confidence set based on using marginal mean values. The first variant minimizes the worst-case expected cost of appointment waiting, server idleness and overtime. In the second variant we minimize the worst-case expected cost of server idleness, subject to constrained worst-case conditional value-at-risk (CVaR) of waiting and overtime. We reformulate the first variant to result in a mixed-integer trilinear separation problem with its convex hull described by a linear program. We derive another linear programming separation problem for the second CVaR variant. We test randomly generated instances to demonstrate the tractability of the reformulations and insights of appointment scheduling under multiple heterogeneous sources of data uncertainty.

* This abstract is submitted to the session organized by Siqian Shen.

ABSTRACT. This presentation focuses on an improvement project for the local children's advocacy center, which provides medical evaluations and treatment for abused children. The center has been struggling with a high number of no-shows for initial evaluations. This prevents children who were supposed to be seen from getting the help required. As part of the improvement project, a simulation was used to evaluate various improvement scenarios. The final implemented solution has shown a 42% improvement (29% to 17%) in missed appointments after its first few months of implementation.

ABSTRACT. Consumer Decision Simulator

With an evolving need for reduction of marketing research costs, companies have been exploring alternative data sources like web analytics, social media and direct customer feedback. However most of this data might come with considerable noise, and isolating true signals could actually take the costs up again.

Based on past consumer behavior and current research (including neuro marketing research) we can put together a series of consumer behavior algorithms and create a statistical model that could mimic the way our consumers make a choice. This tool which would be the “consumer decision simulator” could then be tested for historical scenarios and once we have reduced the margin of error we can leverage the same to predict consumer behavior in the future. By design this model would be tuned every time it does not forecast accurately, thereby improving the algorithms as more and more data is processed with time.

Huge cost savings could be brought in by substituting a large portion of market research, with this analytics backed consumer decision simulator. Even if we save 80% of the costs for just 10% of all companies that invest in market research, it could translate to almost USD 2 Billion.

ABSTRACT. Railroad classification yards play a significant role in freight transportation: shipments are consolidated to benefit from economies of scales. However, the disassembling of inbound trains, the classification of railcars and reassembling of outbound trains add significant time to the overall transportation. Determining the operational schedule of a railroad classification yard to ensure that railcars pass as quickly as possible through the yard to continue with their journey to their final destination is a challenging problem. In this paper, we create a simulation optimization model to mimic the dynamics of a classification yard and determine prioritizing rules for the sequencing of inbound and outbound trains to optimize performance measures such as average wait time and daily throughput.

ABSTRACT. The nuclear fuel cycle is comprised of all of the facilities and material flows required to generate power from nuclear reactors. Many possible fuel cycle options exist to industrial and governmental entities, including a once-through cycle as well as recycling used fuel in an open cycle. Nuclear fuel cycle simulators (NFCS) are decision-making tools that model both supply chain dynamics and an appropriate level of physics, capturing material composition changes due to irradiation and radioactive decay. Cyclus is an open source, agent-based NFCS, treating facilities individually and representing material transfers as discrete transactions between facilities. The primary abstraction in the simulation kernel is the Dynamic Resource Exchange (DRE) in which isotopic-specific demand is queried, supply is proposed, and a bipartite supply-demand network with constraints is created. The DRE network can then translated into a mixed integer linear program (MILP) and solved using Coin-OR's Branch and Cut solver. The solution is then back-translated into simulation space, and the corresponding trades are executed. This work describes the DRE process and formulation as well as the results of a scoping study in which ~1E4 DRE instances were generated and solved using a high-throughput computing (HTC) system at UW Madison.

ABSTRACT. Dynamic optimization problems that include differential equations as constraints are often solved by discretizing the model and then solving the resulting nonlinear problem. Several strategies exist for discretizing dynamic systems including finite difference methods and collocation over finite elements. However, implementing these discretization strategies is usually done by hand which can be both time consuming and error prone.

This talk introduces a tool for automatic model discretization developed using the open-source modeling language Pyomo. Our tool is capable of discretizing ODE and PDE systems as well as higher order derivatives and mixed partial derivatives. We will discuss the straight-forward syntax behind this functionality as well as the flexible discretization options that are available. Finally, we will look at a few sample problems that show the wide range of dynamic optimzation problems that can now be represented and solved using Pyomo.

ABSTRACT. Pyomo supports the formulation and analysis of mathematical models for complex optimization applications. Pyomo's modeling objects are embedded within Python, a full-featured high-level programming language that contains a rich set of supporting libraries. This presentation describes recent advances in Pyomo 4.0, which is a major evolution of the Pyomo software. Pyomo is a rebranding of the Coopr software, and it contains significant modeling extensions and changes that impact the user.

ABSTRACT. The Pyomo modeling package provides a flexible framework for construction of problem transformations and meta-algorithms. Inspired by the Outer Approximation (OA) algorithm, the Pyomo modeling framework is used to develop a tailored algorithm for Mixed-Integer Nonlinear Programming (MINLP) problems. This approach is an iterative algorithm relying on solving a sequence of lower and upper bounding problems. Particularly, the nonlinear functions in the original MINLP are relaxed by a series of piecewise linear under- and over-estimators, which can be easily implemented using Pyomo’s built-in functions. To demonstrate its application, our tailored solution technique is used to solve infectious disease parameter estimation problems formulated as non-convex MINLPs.

ABSTRACT. (Session Chair:Bergman) Understanding spatio-temporal resource preferences is paramount in the design of policies for sustainable development. Unfortunately, resource preferences are often unknown to policy-makers and have to be inferred from data. In this paper we consider the problem of inferring agents’ preferences from observed movement trajectories and formulate it as an Inverse Reinforcement Learning problem (IRL). With the goal of informing policy-making, we take a probabilistic approach and consider generative models that can be used to simulate behavior under new circumstances such as changes in resource availability, access policies, or climate. We introduce so-called Dynamic Discrete Choice models from Econometrics and prove that they generalize the Max-Entropy IRL Model, one of the most widely used probabilistic approaches from the Machine Learning literature. Furthermore, we develop SPL-GD, a new learning algorithm for Dynamic Discrete Choice models that is considerably faster than the state of the art and scales to very large datasets.

We consider an application in the context of pastoralism in the arid and semi-arid regions of Africa, where migratory pastoralists face regular risks due to resource availability, droughts, and resource degradation from climate change and development. We show how our approach based on satellite and survey data can accurately model migratory pastoralism in East Africa and that it considerably outperforms other approaches on a large-scale real-world dataset of pastoralists’ movements in Ethiopia collected over 3 years.

ABSTRACT. This talk explores how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used in constraint programming and local search) and constraint satisfiability (typically exploited in mathematical programming). The paper considers dual and primal methods, studies their properties, and discusses how they can be implemented in terms of high-level model combinators and algorithmic templates. Experimental results suggest the potential benefits of Lagrangian methods for improving high-level constraint programming and local search models.

ABSTRACT. We introduce in this paper a new flow-driven and constraint-based approach for error localization. The input is a faulty program for which a counter-example and a postcondition are provided. To identify helpful information for error location, we generate a constraint system for the paths of the control flow graph for which at most k conditional statements may be erroneous. Then, we calculate Minimal Correction Sets (MCS) of bounded size for each of these paths. The removal of one of these sets of constraints yields a maximal satisfiable subset, in other words, a maximal subset of constraints satisfying the post condition. To compute the MCS, we extend the algorithm proposed by Liffiton and Sakallah in order to handle programs with numerical statements more efficiently. The main advantage of this flow-driven approach is that the computed sets of suspicious instructions are small, each of them being associated to an identified path. Moreover, the constraint-programming based framework allows mixing Boolean and numerical constraints in an efficient and straightforward way. Preliminary experiments are quite encouraging.

ABSTRACT. SC:David Bergman The call center managers at Hydro-Québec (HQ) need to deliver both low operating costs and high service quality. Their task is especially difficult because they need to handle a large workforce (more than 500 employees) while satisfying an incoming demand that is typically both time-varying and uncertain. The current techniques for determining the schedule of each employee according to the forecast call volumes at HQ are often unreliable, and there is a need for more accurate methods. In this paper, we address the concerns of the call center managers at HQ by modeling the problem of multi-activity shift scheduling. This model has been implemented and tested using real-life call center data provided by HQ. The main contribution of this paper is to demonstrate that a constraint programming (CP) model with regular language encoding can solve large problems in an industrial context. Furthermore, we show that our CP-based formulation has considerably better performance than a well-known commercial software package.

ABSTRACT. Stationary Gaussian random fields are used as models in a range of applications such as image analysis or geostatistics. For example, the spatial distribution of fMRI signals is often modeled as a stationary Gaussian random field with a pre-specified covariance structure. One of the most effective and exact methods to synthesize such fields is based on the so-called circulant matrix embedding. But the standard version of the method works only under suitable assumptions, which are well-known to fail for many practical covariance structures of stationary fields of interest. In this talk, I will present a novel methodology which adaptively constructs feasible circulant embeddings based on constrained quadratic optimization. In the first part of my talk, I will review two circulant embedding methods, namely, the standard and smoothing windows circulant embeddings. Then, I will give several examples of covariance functions for which these methods fail and motivate the formulation of a quadratic problem with linear inequality constraints. In the second part of my talk I will explain how a well-known interior point optimization strategy called primal log barrier method can be suitably adapted to solve the quadratic problem faster than commercial solvers. Time permitting, future work will also be discussed.

ABSTRACT. In optimization problems it is of fundamental importance to have a short and easy to verify proof of infeasibility.

In linear programming (LP) the celebrated Farkas' lemma easily verifies infeasibility: the linear system (1) x≥0,Ax=b is infeasible, if and only if the alternative system (2) y^T A≥0,y^T b=-1. is feasible and the "if" statement is trivial to prove. I.e., the system (2) is a short certificate of infeasibility of (1).

Semidefinite programming (SDP) is the problem of optimizing a linear objective subject to linear constraints, and the matrix variable being positive semidefinite. SDP is a vast generalization of LP, with applications in combinatorial optimization, engineering and statistics. The straightforward generalization of Farkas' lemma, however, may fail.

We present a short certificate of infeasibility of SDPs using a standard form reformulation. The "if" direction is almost as easy to prove as in the LP Farkas' lemma.

Obviously, there are infinitely many infeasible SDPs. Still, the reformulation allows us to systematically generate all of them; and we prove that, somewhat surprisingly, there are only finitely many "representative" SDPs in every dimension.

ABSTRACT. A common problem in machine learning is to optimize a separable convex function. When the number of records and features is very large, parallel computing must be used. We implemented several known algorithms in map reduce on Hadoop and developed new variants suitable for large-scale problems. A thorough computational study is presented.

ABSTRACT. In this paper, we derive a strengthened MILP formulation for certain gas turbine unit commitment problems, in which the ramping rates are no smaller than the minimum generation amounts. This type of gas turbines can usually startup faster and have a larger ramping rate, as compared to the traditional coal-fired power plants. Recently, the number of this type of gas turbines increases significantly due to affordable gas prices and their scheduling flexibilities to accommodate intermittent renewable energy generation. In this study, several new families of strong valid inequalities are developed to help reduce the computational time to solve these types of problems. Meanwhile, the validity and facet-defining proofs are provided for certain inequalities. Finally, numerical experiments on a modified IEEE 118-bus system and the power system data based on recent studies verify the effectiveness of applying our formulation to model and solve this type of gas turbine unit commitment problems, including reducing the computational time to obtain an optimal solution or obtaining a much smaller optimality gap, as compared to the default CPLEX and GUROBI, when the time limit is reached with no optimal solutions obtained.

ABSTRACT. Mixed integer programming (MIP) solvers and their efficiency in solving MIPs are impacted by the solver’s parameter settings and the structure of the MIP. We use a designed experiment approach to fit a model that would suggest settings of the parameters that provided the greatest impact on the performance metrics.

We compared our method for parameter tuning with CPLEX to four other methods. Three methods come from the Selection Tool for Optimization Parameters (STOP), and they are random, greedy heuristic, and pairwise coverage. The last is CPLEX’s own tuning algorithm. In order to evaluate these methods we first work with a limited number of parameters so that a full factorial design can be used and the predictions of the four methods can be ranked on their performance in comparison to the best parameter settings. These experiments are conducted on three classes of MIP problems: survivable fixed telecommunication network design, a formulation of the support vector machine with the ramp loss and L1-norm regularization, and node packing for coding theory graphs.

Determining good parameter settings for a specific solver for a class of instances can reduce computational requirements. With a designed experiment approach we not only obtain good parameter settings, but we also gain insights on which parameters are critical for reducing computational times.

ABSTRACT. It is well-known that the feasible reason of a MISOCO problem can be approximated by a polyhedron. We present a solver implementing a cutting plane algorithm for solving second order conic optimization (SOCO) problems based on such linear approximations. In this algorithm, we iteratively solve linear optimization problem (LP) relaxations of the original MISOCO problem, strengthened by generating linear cuts from the conic constraints. COLA (Conic Optimization with Linear Approximations) is the SOCO solver that implements this algorithm. DietCOLA (Discrete COLA) is a solver for MISOCO problems that uses COLA in a branch-and-bound framework. Computational performance of COLA and DietCOLA are discussed.

We also describe several auxiliary libraries, including an open interface for conic solvers and a cut library for boosting performance of DietCOLA. The cut library implements most known valid inequalities for MISOCO from the literature. It is built as an extension of the cut generation library of the COIN-OR and thus also provides access to the standard classes of valid inequalities from mixed integer linear optimization problems. We demonstrate the results on conic benchmark library (CBLIB 2014).

ABSTRACT. Finding an optimal policy in an inventory setting often involves formulating and solving dynamic programs. These types of problems are notoriously slow to solve, and tractability concerns limit exploration of the solution space over various parameterizations of the problem. In the computing realm, functional programming (FP) has enjoyed a surge of innovation in recent years, motivated pragmatically by its applicability to parallel computing and theoretically by a rich category-theoretic underpinning. Additionally, FP compilers can implement aggressive optimizations due to the lack of mutable state.

We pose a problem consisting of a manufacturer and multiple retailers, in which one retailer has access to additional information about the manufacturer. We formulate this as a finite horizon dynamic program, and implement a solver in Haskell, a leading FP language. Our implementation achieves drastic speed increases relative to our reference Matlab implementation. This allows us to explore the solution space over a broad range of parameterizations of the model. Additionally, we demonstrate a simulated method of moments (SMM) estimation, which matches moments of hypothetical data set with moments resulting from a simulated optimal policy. Our approach is applicable to a broad range of finite-horizon dynamic programs.

ABSTRACT. This research produces the optimum result of sub-trees which are partitioned from a bigger tree. It has its own dominant competitiveness compared to other researches on the tree partition problems in terms of considering both capacity and connectivity which make our research even more realistic. The purpose of the research is to minimize the total sum of edge costs in sub-trees after partitioning a tree. In order to achieve this, we firstly identified fundamental equations to solve the tree partition problem by setting objective function, design variables, and constraints. Based on these equations, we developed the optimization solver using a branch and bound algorithm produced by the Gurobi-Python Interface. Since the solver should consider both capacity and connectivity at the same time during the calculation, the computational cost is expensive. To reduce the computational time of the solver, we added some identified facets and applied our own linear time separation algorithm to generate our own cutting planes specific to the tree partitioning problem. With this solver, it is possible to suggest the way of clustering while satisfying capacities in different partitions and keeping connectivity.

ABSTRACT. In this poster, we present a two-stage robust scheduling problem for power systems with rich hydro resources. We consider the natural water inflow uncertainty in this problem and employ a vector auto-regressive model to depict its fluctuation and seasonality. We design a Benders' decomposition algorithm to solve this problem and verify the proposed approach on a real-world case study.

ABSTRACT. Incomplete or incorrect requirements have been known to cause failure in many systems engineering projects. As projects progress and more information is gathered, stakeholders’ needs and requirements may change and evolve. While intentions are typically good, documenting and communicating these changes continue to pose a monolithic challenge. Oft times, the latest (or updated) requirement(s) become “lost in translation” as they cross project stakeholders, functional domains, and migrate through systems engineering phases; contributing to requirements creep, which causes projects to be behind schedule and over budget. Many methods and tools have been employed to improve requirements management and, as globalization increases, developing sustainable systems has become imperative. In this research, we utilize recommender systems (RSs) to further optimize requirements management for sustainable systems. RSs further facilitate search capabilities and help “push” the most applicable information to the right users within the right time. This promotes knowledge use and reuse, thereby increasing efficiencies in eliciting, analyzing, and managing requirements, further ensuring the system delivered is what was truly needed. Through a cursory literature review further study in these areas is warranted and future research will provide an analysis of experimental data demonstrating the value of RSs in sustainable system requirements management.

ABSTRACT. We consider the robust mixed integer program (MIP) with uncertainties appearing in the body of constraints. Our goal is to derive strong valid inequalities to solve such problems efficiently. Note that such inequalities are valid only if they hold for the intersection of polyhedra defined by all possible realizations. To strengthen robust minimal cover inequalities, we develop a robust lifting algorithm that generates cutting planes with consideration of all scenarios. We show that this dynamic programming procedure is polynomial solvable and provide sufficient conditions that guarantee those inequalities are facet-defining. Finally, we will show that our strategy will improve the computational performance of existing algorithms such as the restart solution strategy by Fischetti and Monaci.

Detailed theoretical derivations, computational performance, as well as discussion on deriving superadditive lifting approximation for this procedure will be presented in our poster.

ABSTRACT. Optimized Profile Descent (OPD) is an arrival procedure for the Next Generation Air Transportation System (NextGen), which has been demonstrated to effectively decrease noise, emissions and fuel costs. In this paper, we develop models to further increase such potential savings of OPD through optimal metering policies, which include identification of the optimal number and locations for such metering points to better sequence and space arriving aircraft. We present an algorithmic framework based on integrations of a stochastic dynamic program and a multistage nonlinear stochastic integer program to minimize the relevant costs involved. A set of discrete scenarios is linked to the realized spacings of aircraft at metering points, and used as inputs to the stochastic models. Noting that the standard stochastic programming formulation is noncovex, a convex formulation is developed through a two dimensional piecewise linearization of several bilinear terms. Moreover, a Lagrangian decomposition procedure is implemented for computational tractability. We present some numerical results based on actual traffic information at selected major U.S. airports. The results demonstrate the efficacy of our algorithmic framework and show a potential savings value of around 8% over current practice. We also implement sensitivity analysis of optimal metering point locations over different arrival rates.

ABSTRACT. Support Vector Data Description (SVDD) is used as an implicit classification method for purposes such as novelty and anomaly detection. The major drawback of this method is its computational complexity since the classical method of solving SVDD involves detecting the ‘support vector’ patterns associated with a sphere in high-dimensional (possibly infinite dimensional) feature space. For N target patterns of dimension d given for training, the current best complexity to solve SVDD is O(N)-an improvement from the original O(N^3 ). This work proposes and demonstrates a novel reduced complexity approach based on SVDD. The proposed algorithm reduces the training complexity to O(d) by avoiding the calculation of the Lagrange multipliers by locating an approximate pre-image of the SVDD sphere’s center in the input space during the training phase itself. It retains the benefit of the kernel trick: i.e. a minimum enclosing space is more descriptive of the data when calculated in a higher-dimensional feature space. The crux of the training algorithm is a gradient descent of the primal objective function using Simultaneous Perturbation Stochastic Approximation (SPSA). Experiments on both synthetic and real-world datasets obtained from UCI machine learning repository have demonstrated that the proposed approach is promising.

ABSTRACT. We study the convex hull of a two-term disjunction applied to the second-order cone and develop a methodology to derive closed-form expressions for convex inequalities that describe the resulting convex hull. Our approach capitalizes on the structure of tight minimal valid linear inequalities for the disjunction. We use this structure and conic duality to derive a family of convex, possibly nonlinear, valid inequalities that summarize the tight minimal linear inequalities. We identify and study the cases where these convex inequalities can equivalently be expressed in conic quadratic form and where a single inequality from this family is sufficient to describe the convex hull.

In more recent work, we extend these results to two-term disjunctions on cross-sections of the second-order cone. We show that a single convex inequality is sufficient to characterize the closed convex hull of all two-term disjunctions on ellipsoids and paraboloids, and split disjunctions on all cross-sections of the second-order cone.

ABSTRACT. A connected graph is said to be k-vertex connected if the resulted graph after removal of fewer than k vertices is still connected. Also, a connected graph is called l-edge connected if the resulted graph after removal of fewer than l edges, is still connected. The diameter d of a graph is the greatest distance between any pair of vertices. We combine the edge and vertex connectivity requirements with diameter constraint, by proposing integer programming models and designing algorithms, to design a minimum-cost network such that the resulted graph, after removal of at most k vertices and/or l edges, has diameter d.

ABSTRACT. The minimum k-enclosing ball problem seeks the ball with smallest radius that contains at least k of n given points in a general d-dimensional Euclidean space. This problem is NP-hard. The minimum enclosing ball problem (requiring the ball to contain all points) can be formulated as a second-order-cone program and solved in polynomial time. However, it turns out that for the minimum enclosing ball problem there are both primal and dual iterative algorithms that are very similar to the simplex method for linear programming. We incorporate these methods into a branch and bound search to solve the minimum k-enclosing ball problem. Some preliminary computational results will be presented. Both problems have applications in statistical learning theory and classification problems, among others.

ABSTRACT. Maximizing the spread of influence in social networks is the problem of finding such a set of influential nodes that will generate a maximal viral cascade. This work introduces a diffusion-based influence model that captures evidence transfer between communicating actors who are testing a Bayesian hypothesis, e.g., for making judgment about the superiority of some product(s)/service(s) over others, or (dis)utility of a program/policy. The model-based optimization problem solutions inform strategies for market niche selection and protection, and identification of susceptible groups in political campaigning. The NP-Hard problem of selecting influential nodes is first solved as a mixed-integer program. Allowing for a deeper look at influence strategies, the problem instances solved within the presented framework take into account both the number of activated nodes and activation timing. Problem-specific Lagrangian Relaxation and iterative seed removal heuristics are developed next to handle large problem instances. Computational results showcase that the designed algorithms return quality solutions (with the optimality gap below 5%) for small, medium and large problem instances. Insightful observations are made by quantifying the impact of social connection structure on belief reinforcement and “defendability” of network clusters against intrusion of external judgments/preferences/opinions.

ABSTRACT. Uncertainties bring many reliability issues to the power system planning and operations. The stochastic programming has been proposed to solve the unit commitment problem with uncertainty. However, scalability remains as a challenge to large power systems. In this poster, a set of reliability cuts are identified based on the polyhedral structure taking advantages of the unique power system characteristics. The necessary and sufficient condition for a feasible scheduling in the power grid is shown and then the extreme rays of the dual cone (polyhedron structure) are characterized. The extreme rays are determined by the combinatorial selection of the buses and the transmission lines. The crucial selections of the buses and the transmission lines are carried out by off-line study. The test results are presented on a RTS96 73-bus system. The problem is formulated as a 24-period security-constrained unit commitment problem with N-1 generator failure contingency reliability requirement. The proposed method is examined and compared with the stochastic programming approach. The preliminary test results show that the proposed method improves the computational efficiency significantly.

ABSTRACT. We present the statistical and computational aspects of inverse problems for nonlinear parameter dependent dynamical systems. In many situations, the noise assumption of normality is violated: therefore, the maximum likelihood estimation is used for solving the problem in this case. We consider the asymptotic theory approach for problems involving data with different noise forms and constant variance data. In addition, we review the sensitivity analysis to distinguish between high influential parameters and less influential parameters in the nonlinear models. We also use the concept of traditional sensitivity functions to develop a strategy to determine the optimal final time T for an experiment, and to specify the time range of the highest information content with respect to the parameters. Moreover, we consider the role of the traditional sensitivity functions in finding the best sampling distributions. In order to obtain the optimal sampling distributions, we consider Monte Carlo simulations for a given sampling strategy, and then compare the sampling strategies based on the average of the standard errors obtained. We illustrate these ideas throughout with the Verhulst-Pearl logistic growth model.

ABSTRACT. We provide a software comparison of R and IBM SPSS Modeler for a large retailer employing advanced predictive analytics. Designing and implementing analytical solutions that provide reliable and timely decision-support is important to retailers. While analytical software with all the bells and whistles is nice to have, it can be extremely costly. According to Nisbet et al. (2009), the most mediocre data mining tools are able to generate models as good as the best tools at least 90 percent of the time. Less elegant open-source solutions should be considered if they can provide a desired solution while meeting the firms many operational and budgetary constraints and KPIs. Studying a Fortune 500 retailer’s merchandise assortment planning process which builds, ensembles, and cross-validates hundreds of predictive modeling using IBM SPSS Modeler, we re-engineered their modeling structure using the R language and ran our open-source solution against this commercial software. We provide interesting lessons learned, a comparison of out-of-sample error rates for what should be the same algorithms with same tuning parameters, compare computing times, as well as discuss identified quality and security risks that are also key considerations for a firm deciding on an analytical computing platform.

ABSTRACT. The faro shuffle denotes a re-arrangement procedure in which a deck of playing cards is split exactly in half and all cards are perfectly interleaved. In this work we show how to schedule a tournament involving an even number n of teams using the faro shuffle procedure. Given two decks of n cards represented by integers {0,…, n-1}, one deck will be used to determine the opponents of team i while the other deck will be used to identify the rounds in which i faces its opponents. Take the first deck and arrange all cards side-by-side on ascending order. Then, take the second deck and arrange all its cards as a faro shuffle of the first deck, keeping every card of the second deck right below of every card of the first deck. For each position i={1,2,…,n-2}, each card of the second row denotes a round and each card in the first row denotes the opponent of the team at the position 0. Take the card at the position 0 of the first deck, insert it between the cards at positions n-2 and n-1 and repeat the process. The proposed faro method is equivalent to the classic circle method.

ABSTRACT. The support vector machine (SVM) is a flexible classification method that accommodates a kernel trick to learn nonlinear decision rules. The traditional formulation as an optimization problem is a quadratic problem. In efforts to reduce computational complexity, some have proposed using an L1-norm regularization to create a linear programming (LP) problem. In other efforts aimed at increasing the robustness to outliers, investigators have proposed using the ramp loss which results in what may be expressed as a quadratic integer programming problem (QIP). In this paper, we consider combining these ideas for ramp loss SVM with L1-norm regularization. The result is four formulations for SVM that each may be expressed as a mixed integer linear program (MILP). We observe that ramp loss SVM with L1-norm regularization provides robustness to outliers with the linear kernel. We investigate the time required to find good solutions to the various formulations using a branch and bound solver.

ABSTRACT. Principal component analysis (PCA) is one of the most widely used multivariate techniques in statistics. It is commonly used to reduce the dimensionality of data in order to examine its underlying structure and the covariance/correlation structure of a set of variables. While singular value decomposition provides a simple means for identification of the principal components (PCs) for classical PCA, solutions achieved in this manner may not possess certain desirable properties including robustness, smoothness, and sparsity. In this paper, we present several optimization problems related to PCA by considering various geometric perspectives. New techniques for PCA can be developed by altering the optimization problems to which principal component loadings are the optimal solutions.

ABSTRACT. Categorical and ordinal data sets are susceptible to large number of ties in distance/similarity scores and therefore pose a potential problem for the k nearest neighbor (kNN) algorithm. In some cases, exactly k nearest neighbors to a record being classified cannot be chosen without discriminating among a set of equidistant neighbors. In this work, we propose that discriminating among a set of equidistant neighbors be avoided by (1) recruiting all members of the set of equidistant neighbors as opposed to randomly discriminating among them in order to preserve the value of k and (2) adopting a new voting policy such that the set of equidistant neighbors contribute only a single vote during classification to prevent voting bias towards the equidistant neighbors. Therefore, during the recruitment of nearest neighbors, the value of k may be increased to a higher value, while the number of votes needed to determine the predicted class will be less than or equal to k. Preliminary findings indicate that this modification results in higher classification accuracy and, for real-valued data sets, defaults to the unmodified kNN algorithm. Results were obtained by implementing both algorithms using data sets from the UCI Machine Learning Repository.

ABSTRACT. In an electricity network, large power consumers are charged for their peak demand (grid purchase) (in kW) in addition to the energy they consumed (in kWh) within each billing cycle. This charge is called a demand charge. This structure creates an incentive for customers to reduce their peak grid purchase level in order to reduce both the energy payment and the demand charge. To achieve this, a battery energy storage systems (BESS) may be employed to perform peak shaving tasks for power consumers. In our model, the power consumption requirement is assumed to be non deferrable and stochastic. In this paper, we first introduce a Dynamic Programming (DP) algorithm to arrange grid purchases using a battery as a buffer. Then we introduce a Sample Average Approximation (SAA) algorithm that solves the problem in an iterative fashion, providing close-to-optimal solutions in short period of time. We then extend the SAA algorithm to real time planning, where the load forecast is obtained from a real time predictor and may change over time. Simulation shows that real time SAA algorithm produce good result.