Bi-objective Simulation Optimization on Integer Lattices using the Epsilon-Constraint Method in a Retrospective Approximation Framework

Categories Integer Programming, Multi-Criteria Optimization, Optimization of Simulated Systems Tags , ,

We consider multi-objective simulation optimization (MOSO) problems on integer lattices, that is, nonlinear optimization problems in which multiple simultaneous objective functions can only be observed with stochastic error, e.g., as output from a Monte Carlo simulation model. The solution to a MOSO problem is the efficient set, which is the set of all feasible decision … Read more

A Column Generation Algorithm for Vehicle Scheduling and Routing Problems

Categories Applications - OR and Management Sciences Tags , , ,

During natural or anthropogenic disasters, humanitarian organizations (HO) are faced with the time sensitive task of sending critical resources from multiple depots to the affected areas that can be scattered across a region. This responsibility includes the quick acquisition of vehicles from the local market and the preparation of pickup and delivery schedules and vehicle … Read more

A lower bound on the iterative complexity of the Harker and Pang globalization technique of the Newton-min algorithm for solving the linear complementarity problem

Categories Complementarity and Variational Inequalities, Nonsmooth Optimization Tags , , , , , , , , ,

The plain Newton-min algorithm for solving the linear complementarity problem (LCP) 0 ≤ x ⊥ (Mx+q) ≥ 0 can be viewed as an instance of the plain semismooth Newton method on the equational version min(x,Mx+q) = 0 of the problem. This algorithm converges for any q when M is an M-matrix, but not when it … Read more

Multi-Product Newsvendor Problem with Customer-driven Demand Substitution: A Stochastic Integer Program Perspective

Categories Applications - OR and Management Sciences Tags , , , ,

This paper studies a multi-product newsvendor problem with customer-driven demand substitution, where each product, once run out of stock, can be proportionally substituted by the others. This problem has been widely studied in the literature, however, due to nonconvexity and intractability, only limited analytical properties have been reported and no efficient approaches have been proposed. … Read more

An Approximation Algorithm for Vehicle Routing with Compatibility Constraints

Categories Approximation Algorithms, Transportation Tags , ,

We study a multiple-vehicle routing problem with a minimum makespan objective and compatibility constraints. We provide an approximation algorithm and a nearly-matching hardness of approximation result. We also provide computational results on benchmark instances with diverse sizes showing that the proposed algorithm (i) has a good empirical approximation factor, (ii) runs in a short amount … Read more

The Proximal Alternating Minimization Algorithm for two-block separable convex optimization problems with linear constraints

Categories Convex Optimization Tags , , , , ,

The Alternating Minimization Algorithm (AMA) has been proposed by Tseng to solve convex programming problems with two-block separable linear constraints and objectives, whereby (at least) one of the components of the latter is assumed to be strongly convex. The fact that one of the subproblems to be solved within the iteration process of AMA does … Read more

An ADMM-Based Interior-Point Method for Large-Scale Linear Programming

Categories Convex and Nonsmooth Optimization, Linear, Cone and Semidefinite Programming Tags , , , , ,

In this paper, we propose a new framework to implement interior point method (IPM) in order to solve some very large scale linear programs (LP). Traditional IPMs typically use Newton’s method to approximately solve a subproblem that aims to minimize a log-barrier penalty function at each iteration. Due its connection to Newton’s method, IPM is … Read more

Solving Time Dependent Traveling Salesman Problems with Time Windows

Categories Transportation Tags , , ,

We present a new solution approach for the Time Dependent Traveling Salesman Prob- lem with Time Windows. This problem considers a salesman who departs from his home, has to visit a number of cities within a pre-determined period of time, and then returns home. The problem allows for travel times that can depend on the … Read more

Sensitivity Analysis for Nonlinear Programming in CasADi

Categories Modeling Languages and Systems, Quadratic Programming Tags , , , ,

We present an extension of the CasADi numerical optimization framework that allows arbitrary order NLP sensitivities to be calculated automatically and efficiently. The approach, which can be used together with any NLP solver available in CasADi, is based on a sparse QR factorization and an implementation of a primal-dual active set method. The whole toolchain … Read more

A Fully Distributed Dual Consensus ADMM Based on Partition for DC-OPF with Carbon Emission Trading

Categories Applications - Science and Engineering, Energy Tags , , , ,

This paper presents a novel fully distributed alternating direction method of multipliers (ADMM) approach for solving the direct current optimal power flow with carbon emission trading (DC-OPF-CET) problem. Different from the other ADMM-based distributed approaches which disclosing boundary buses and branches information among adjacent subsystems, our proposed method adopts a new strategy by using ADMM … Read more