Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased

Partial inverse combinatorial optimization problems are bilevel optimization problems in which the leader aims to incentivize the follower to include a given set of elements in the solution of their combinatorial problem. If the set of required elements defines a complete follower solution, the inverse combinatorial problem is solvable in polynomial time as soon as … Read more

Policy with guaranteed risk-adjusted performance for multistage stochastic linear problems

Risk-averse multi-stage problems and their applications are gaining interest in various fields of applications. Under convexity assumptions, the resolution of these problems can be done with trajectory following dynamic programming algorithms like Stochastic Dual Dynamic Programming (SDDP) to access a deterministic lower bound, and dual SDDP for deterministic upper bounds. In this paper, we leverage … Read more

A Hybrid Genetic Algorithm for Generalized Order Acceptance and Scheduling

In this paper, a novel approach is presented to address a challenging optimization problem known as Generalized Order Acceptance Scheduling. This problem involves scheduling a set of orders on a single machine with release dates, due dates, deadlines, and sequence-dependent setup times judiciously to maximize revenue. In view of resource constraints, not all orders can … Read more

Kantorovich and Zalgaller (1951): the 0-th Column Generation Algorithm

This article delves into the early development of the Column Generation technique. It begins with Kantorovich’s classic 1939 work, correcting widespread misconceptions about his contributions to the Cutting Stock Problem. Then, it brings to light Kantorovich and Zalgaller’s lesser-known 1951 book, which is revealed to contain a complete Column Generation algorithm. The article also places … Read more

The convergence rate of the Sandwiching algorithm for convex bounded multiobjective optimization

Sandwiching algorithms, also known as Benson-type algorithms, approximate the nondominated set of convex bounded multiobjective optimization problems by constructing and iteratively improving polyhedral inner and outer approximations. Using a set-valued metric, an estimate of the approximation quality is determined as the distance between the inner and outer approximation. The convergence of the algorithm is evaluated … Read more

Addressing Hierarchical Jointly-Convex Generalized Nash Equilibrium Problems with Nonsmooth Payoffs

We consider a Generalized Nash Equilibrium Problem whose joint feasible region is implicitly defined as the solution set of another Nash game. This structure arises e.g. in multi-portfolio selection contexts, whenever agents interact at different hierarchical levels. We consider nonsmooth terms in all players’ objectives, to promote, for example, sparsity in the solution. Under standard … Read more

Computing an approximation of the nondominated set of multi-objective mixed-integer nonlinear optimization problems

In practical applications, one often has not only one, but several objectives that need to be optimized simultaneously. What is more, modeling such real world problems usually involves using both, continuous and integer variables. This then results in multi-objective mixed-integer optimization problems, which are in focus of this paper. We present an approximation concept, called … Read more

From Optimization to Control: Quasi Policy Iteration

Recent control algorithms for Markov decision processes (MDPs) have been designed using an implicit analogy with well-established optimization algorithms. In this paper, we make this analogy explicit across four problem classes with a unified solution characterization. This novel framework, in turn, allows for a systematic transformation of algorithms from one domain to the other. In … Read more

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