Budget-Constrained Maximization of “Cobb-Douglas with Linear Components” Utility Function

In what follows, we provide the demand analysis associated with budget-constrained linear utility maximization for each of several categories of goods, with the marginal rate of consumption expenditure-as a share of wealth- being a positive constant less than or equal to one. The marginal rate of consumption expenditure is endogenously determined, by a budget-constrained “Cobb-Douglas … Read more

Neural Approximate Dynamic Programming for the Ultra-fast Order Dispatching Problem

Same-Day Delivery (SDD) services aim to maximize the fulfillment of online orders while minimizing delivery delays but are beset by operational uncertainties such as those in order volumes and courier planning. Our work aims to enhance the operational efficiency of SDD by focusing on the ultra-fast Order Dispatching Problem (ODP), which involves matching and dispatching … Read more

The limitation of neural nets for approximation and optimization

We are interested in assessing the use of neural networks as surrogate models to approximate and minimize objective functions in optimization problems. While neural networks are widely used for machine learning tasks such as classification and regression, their application in solving optimization problems has been limited. Our study begins by determining the best activation function … Read more

Solving Various Classes of Arc Routing Problems with a Memetic Algorithm-based Framework

Arc routing problems are combinatorial optimization problems that have many real-world applications, such as mail delivery, snow plowing, and waste collection. Various variants of this problem are available, as well as algorithms intended to solve them heuristically or exactly. Presented here is a generic algorithmic framework that can be applied to a variety of arc … Read more

Facets of the knapsack polytope from non-minimal covers

We propose two new classes of valid inequalities (VIs) for the binary knapsack polytope, based on non-minimal covers. We also show that these VIs can be obtained through neither sequential nor simultaneous lifting of well-known cover inequalities. We further provide conditions under which they are facet-defining. The usefulness of these VIs is demonstrated using computational … Read more

Solving Nonconvex Optimization Problems using Outer Approximations of the Set-Copositive Cone

We consider the solution of nonconvex quadratic optimization problems using an outer approximation of the set-copositive cone that is iteratively strengthened with conic constraints and cutting planes. Our methodology utilizes an MILP-based oracle for a generalization of the copositive cone that considers additional linear equality constraints. In numerical testing we evaluate our algorithm on a … Read more

Semidefinite programming by Projective Cutting-Planes

\(\) Seeking tighter relaxations of combinatorial optimization problems, semidefinite programming is a generalization of linear programming that offers better bounds and is still polynomially solvable. Yet, in practice, a semidefinite program is still significantly harder to solve than a similar-size Linear Program (LP). It is well-known that a semidefinite program can be written as an … Read more

A Single-Loop Algorithm for Decentralized Bilevel Optimization

Bilevel optimization has gained significant attention in recent years due to its broad applications in machine learning. This paper focuses on bilevel optimization in decentralized networks and proposes a novel single-loop algorithm for solving decentralized bilevel optimization with a strongly convex lower-level problem. Our approach is a fully single-loop method that approximates the hypergradient using … Read more

Relaxation strength for multilinear optimization: McCormick strikes back

We consider linear relaxations for multilinear optimization problems. In a recent paper, Khajavirad proved that the extended flower relaxation is at least as strong as the relaxation of any recursive McCormick linearization (Operations Research Letters 51 (2023) 146-152). In this paper we extend the result to more general linearizations, and present a simpler proof. Moreover, … Read more

Combining Precision Boosting with LP Iterative Refinement for Exact Linear Optimization

This article studies a combination of the two state-of-the-art algorithms for the exact solution of linear programs (LPs) over the rational numbers, i.e., without any roundoff errors or numerical tolerances. By integrating the method of precision boosting inside an LP iterative refinement loop, the combined algorithm is able to leverage the strengths of both methods: … Read more