A competitive genetic algorithm for single row facility layout

The single row facility layout is the NP-Hard problem of arranging facilities with given lengths on a line, so as to minimize the weighted sum of the distances between all pairs of facilities. Owing to the computational complexity of the problem, researchers have developed several heuristics to obtain good quality solutions. In this paper, we … Read more

Addressing rank degeneracy in constraint-reduced interior-point methods for linear optimization

In earlier work (Tits et al., SIAM J. Optim., 17(1):119–146, 2006; Winternitz et al., COAP, doi=10.1007/s10589-010-9389-4, 2011), the present authors and their collaborators proposed primal-dual interior-point (PDIP) algorithms for linear optimization that, at each iteration, use only a subset of the (dual) inequality constraints in constructing the search direction. For problems with many more constraints … Read more

Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences

Randomized algorithms that base iteration-level decisions on samples from some pool are ubiquitous in machine learning and optimization. Examples include stochastic gradient descent and randomized coordinate descent. This paper makes progress at theoretically evaluating the difference in performance between sampling with- and without-replacement in such algorithms. Focusing on least means squares optimization, we formulate a … Read more

Asymptotic Analysis of Sample Average Approximation for Stochastic Optimization Problems with Joint Chance Constraints via CVaR/DC Approximations

Conditional Value at Risk (CVaR) has been recently used to approximate a chance constraint. In this paper, we study the convergence of stationary points when sample average approximation (SAA) method is applied to a CVaR approximated joint chance constrained stochastic minimization problem. Specifically, we prove, under some moderate conditions, that optimal solutions and stationary points … Read more

Sensitivity analysis for the outages of nuclear power plants

Nuclear power plants must be regularly shut down in order to perform refueling and maintenance operations. The scheduling of the outages is the first problem to be solved in electricity production management. It is a hard combinatorial problem for which an exact solving is impossible. Our approach consists in modelling the problem by a two-level … Read more

Interior-Point Methods for Nonconvex Nonlinear Programming: Cubic Regularization

In this paper, we present a barrier method for solving nonlinear programming problems. It employs a Levenberg-Marquardt perturbation to the Karush-Kuhn-Tucker (KKT) matrix to handle indefinite Hessians and a line search to obtain sufficient descent at each iteration. We show that the Levenberg-Marquardt perturbation is equivalent to replacing the Newton step by a cubic regularization … Read more

A Parallel Bundle Method for Asynchronous Subspace Optimization in Lagrangian Relaxation

An algorithmic approach is proposed for exploiting parallelization possibilities in large scale optimization models of the following generic type. Objects change their state over time subject to a limited availability of common resources. These are modeled by linear coupling constraints and result in few objects competing for the same resource at each point in time. … Read more

Exact Penalization, Level Function Method and Modified Cutting-Plane Method for Stochastic Programs with Second Order Stochastic Dominance Constraints

Level function methods and cutting plane methods have been recently proposed to solve stochastic programs with stochastic second order dominance (SSD) constraints. A level function method requires an exact penalization setup because it can only be applied to the objective function, not the constraints. Slater constraint qualification (SCQ) is often needed for deriving exact penalization. … Read more

Branch-and-Price Guided Search for Integer Programs with an Application to the Multicommodity Fixed Charge Network Flow Problem

We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in … Read more

An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables

Kitahara and Mizuno (2011a) obtained an upper bound for the number of different solutions generated by the primal simplex method with Dantzig’s (the most negative) pivoting rule. In this paper, we obtain an upper bound with any pivoting rule which chooses an entering variable whose reduced cost is negative at each iteration. The bound is … Read more