A Generalized Polynomial Lower Bound for the Weighted Completion Time Variance in a Single Machine

Categories Approximation Algorithms, Combinatorial Optimization, Scheduling Tags , , ,

This paper studies the single-machine problem of minimizing the weighted completion time variance (WCTV) and proposes a polynomially computable lower-bounding framework that generalizes the benchmark introduced by Nessah and Chu (2010). We first develop a generalized augmented-sequence decomposition that mathematically connects the weighted problem with the classical unweighted variance setting. Using this decomposition, we derive … Read more

Equivalence-Based Reduction and Incremental Optimization for Categorical and Ordinal Classification

Categories Data Science Algorithms, Data-Mining, Optimization in Data Science

Exact mathematical programming formulations for estimating classification rules provide guarantees of empirical optimality, but their size grows rapidly with the number of predictive features and model complexity. This paper shows that interpretable classifiers can be estimated by directly maximizing empirical classification accuracy under complexity constraints, using truncation and warm-start strategies compatible with disjunctive normal form … Read more

A note on optimality conditions for optimization problems with empty limiting subdifferentials

Categories Convex and Nonsmooth Optimization, Nonlinear Optimization, Nonsmooth Optimization

We study first-order optimality for constrained composite optimization problems whose objective is the sum of a locally Lipschitz function and a proper lower semicontinuous function. We focus on the case in which the limiting subdifferential of the latter function is empty at a point of interest, so that the usual KKT conditions are unavailable. We … Read more

K-Adaptability in Stochastic Integer Optimization with Recourse

Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , ,

Many optimization problems solved repeatedly in practice, such as in power systems or logistics, share a fixed structure but with different parameter values. Re-optimizing each instance from scratch can be computationally prohibitive, while adopting a single solution for all realizations is overly conservative. The K-adaptability paradigm offers a flexible compromise by precomputing a small set … Read more

Bundle Pricing via Learning the Market from Customer Preferences

Categories Finance and Economics, Optimization in Data Science, Other Topics

We study the problem of learning revenue-maximizing bundle prices when customer valuations and market composition are unknown and the firm observes only customer choices. This problem is challenging because the number of bundle-price decisions grows exponentially with the number of items offered. We develop BLMP (Bundle Pricing via Learning the Market from Customer Preferences), a … Read more

Random Reshuffling for Smooth Convex Optimization: Dominates Stochastic Gradient Descent

Categories Convex Optimization, Nonlinear Optimization, Stochastic Programming Tags , ,

Stochastic Gradient Descent (\(\textsf{SGD}\)) is one of the most classical optimization algorithms with favorable theoretical guarantees, yet its practical implementation differs subtly from its well-known form and is often referred to as Shuffling Stochastic Gradient Descent (\(\textsf{Shuffling SGD}\)). A particularly popular strategy in \(\textsf{Shuffling SGD}\) is Random Reshuffling (\(\textsf{RR}\)), which has achieved great empirical success. … Read more

On the Convergence of Column-and-Constraint Generation Algorithms in Two-Stage Robust Optimization

Categories Robust Optimization Tags , , , , , , ,

We study the well-posedness and convergence of column-and-constraint generation algorithms for general two-stage robust optimization problems. The analysis is formulated in terms of regularity properties of the objective, the second-stage feasible region mapping, and the separation value function, without relying on a particular algebraic representation of the second-stage problem. We give sufficient conditions for the … Read more

Signed Budget Uncertainty for Robust Mixed-Integer Optimization

Categories (Mixed) Integer Linear Programming, Robust Optimization Tags , , ,

Classical budget uncertainty is widely used in robust optimization. It bounds the aggregate absolute deviation of uncertain parameters from nominal values and yields tractable robust counterparts. In many applications, however, information concerns aggregate signed deviations. We therefore study signed budget uncertainty, in which bounds are imposed on signed aggregates rather than absolute deviations. For robust … Read more

A One-Factorization Predictor–Corrector Long-Step Arc-Search Method and a Curvature-Amplified Variant for Semidefinite Programming with a Homogeneous Self-Dual Embedding

Categories Linear, Cone and Semidefinite Programming, Semi-definite Programming Tags ,

In a predictor-corrector arc-search method, a point on the predictor arc is first selected and a corrector is then computed at that point. Since the Karush-Kuhn-Tucker (KKT) matrix changes with the selected point, this correction may require a second factorization in each iteration. We propose a one-factorization arc-search method (OFAS) for semidefinite programming (SDP) that … Read more

BDRS Can Fail for Matrix Scaling and Optimal Transport

Categories Convex Optimization Tags , ,

We show that the Bregman Douglas–Rachford splitting method (BDRS) can fail for matrix scaling and unregularized optimal transport. For matrix scaling, we construct a strictly positive \(36\times6\) integer matrix, positive rational marginals of equal mass, and a positive auxiliary initialization for which the matrix iterates enter a nonconstant six-cycle after one iteration. The construction prescribes … Read more