Abstracts
Geometric characterization of Pareto efficient weight vectors of 4x4 pairwise comparison matricesKristóf Ábele-Nagy, Zsombor Szádoczki, Sándor BozókiPairwise comparison matrices are important concepts of multi-criteria decision making. There are several methods to obtain a weight vector from a pairwise comparison matrix. A weight vector is called Pareto efficient (or Pareto optimal) if it is not possible to improve the approximations of any matrix element by the ratios of the corresponding elements of the vector without making it worse for another matrix element. The aim is the geometric characterization of Pareto efficient weight vectors of 4x4 pairwise comparison matrices. With the help of a directed graph, we show that (in case of absence of a consistent triad) the set of normalized, Pareto efficient weight vectors is a union of three tetrahedra, such that their vertices correspond to weight vectors calculated from 4-long paths and each tetrahedron corresponds to a Hamiltonian cycle. In case of presence of consistent triads, some tetrahedra collapse into smaller dimensions.
On a Special Property of Eigenvalue-Minimization-Based Completion of Incomplete Pairwise Comparison MatricesKolos Ágoston, Laszlo Csato, Sándor BozókiPairwise comparison matrices play a crucial role in the Analytical Hierarchy Process (AHP). Early research in this area focused primarily on complete pairwise comparison matrices; however, attention has gradually shifted toward the analysis of incomplete matrices as well. In such cases, the central problem is to determine appropriate values for the missing elements. One widely studied approach is eigenvalue-minimization-based completion, in which the unknown entries are determined so as to minimize the dominant eigenvalue of the completed matrix. Although the optimization framework underlying this method has been available for a long time, its theoretical properties have received comparatively limited attention. In this work, we present new results on the structural properties of the eigenvalue minimization approach. In particular, we highlight a previously unrecognized phenomenon that reveals a paradoxical aspect of the method.
On the integration of LP folding into MosekErling AndersenIn 2014, Grohe et al. proposed a presolve technique for linear optimization (LO) problems, now known as LP folding. The idea of LP folding is that if the problem data has certain properties, then a set of variables may be aggregated into one variable, leading to a reduction in the problem size. In most cases, the aggregation reduces the solution time of the linear optimization problem and is therefore advantageous. The purpose of the presentation is to discuss how LP folding has been integrated into the optimization software package Mosek (www.mosek.com). The presentation starts with a brief review of the LP folding technique, followed by a discussion of how LP folding has been implemented in Mosek. Finally, computational results are presented demonstrating the benefits of LP folding when Mosek is employed to solve a set of benchmark problems.
Optimization of Business Process Decision Sequences and Human Resource Allocation via Process SynthesisAndrás Aschenbrenner, Léna Kiss, Botond BertokThe operations of modern companies are characterized by highly detailed internal process definitions. Within these processes, tasks are precisely assigned to the personnel authorized to perform them. While this approach contributes to stable organizational functioning, its drawback is that processes are often established based on practical experience rather than formal optimization, meaning neither efficiency nor cost optimality is guaranteed. In this research, we investigated whether modifying the sequence of predefined decision processes can yield higher efficiency and lower operational costs. Each decision process is treated as a Separation Network Synthesis problem, from which a process synthesis model was developed to generate alternative decision sequences. The resulting methodology provides a guaranteed optimal solution. The cost of separation depends on the time required for decision preparation and execution, the number of participants involved, and their respective labor costs. Furthermore, it is insufficient to fix decision processes only once; the optimal network highly depends on changes in the cardinality and distribution of the cases to be separated. These factors can shift dynamically even when the organizational structure and roles remain unchanged. With the proposed algorithmic method, the efficiency and optimality of the decision mechanism can be measured, and the most favorable decision sequence for any given situation can be automatically generated.
Tiling and covering squares with consecutive squares (70 is not enough)János Balogh, Jiri Sgall, József Békési, Lars Magnus Hvattum, Zsolt TuzaGiven n squares with side lengths p, p+1, ..., q (where p and q are integers, q>p, q-p-1=n), and the sum of their squares is exactly the square of an integer K, the question is whether these squares can be packed into a K×K square (container) without rotation or overlap. In 1978, Mullin claimed that there is no perfect tiling for such sequences. We prove that this is true for certain values of (p, q, K). (Using computer calculations) it is easy to see that if q is at most 1000, then there are 126 possible triples, of which we have proved the impossibilty of more than 100 cases using various geometric and combinatorial ideas. When p=1, the only non-trivial case of the problem is q=n=24, where K=70. We recently proved using combinatorial tools that the answer is ’NO’ for this important and well-known case. If the 1, ..., n squares can be any consecutive squares, then the question can be phrased as follows: what is the largest K' or smallest K'' such that the square of side length K' can be covered by the n consecutive squares (overlapping allowed) or placed in a square of side length K'' (without overlapping), without allowing rotation? Returning to the fact that the squares 1, 2, …, 24 cannot fit (without overlapping) into the 70×70 square, the implication is this: 70 is not enough; more are needed...
Reliable Parking Trajectory Prediction with Verifiable Neural NetworksBalázs Bánhelyi, Nándor VinczeReliable trajectory generation is an important requirement for autonomous parking systems where safety and reliability are critical. In this work, we present a complete pipeline that integrates numerical optimization, light neural networks, and formal verification techniques to predict the parameters of parking maneuvers. Firstly, the optimal trajectory is generated using a kinetic vehicle model and a parametric direction function, and the parameters are determined by solving an optimization problem. These trajectories form a training data set that captures the relationship between the initial state of the vehicle and the successful parking maneuver. A compact Feedforward neural network of 32 neurons is trained to approximate this mapping and rapidly predict driver parameters. To ensure the reliability of the model learned, we use interval and fine arithmetic verification steps. This allows us to take into account input uncertainties such as sensor noise and measurement errors and calculate guaranteed boundary values in network outputs. The predicted parameters are used to simulate the path and the safety and avoidance of collisions are evaluated. By systematically verifying small regions of state space, we identify areas where the network prediction is probable. The results show that small and verifiable neural networks with carefully designed training data and model architectures can achieve reliable and safe performance in autonomous parking tasks.
Tight Approximation Ratio of Algorithm SDF for UET Coupled Task Scheduling ProblemJózsef Békési, Gyorgy Dosa, Gábor GalambosIn the coupled task problem (CTP), we have to schedule n jobs on a single machine. Each job consists of two tasks, and exact delay times between the tasks should elapse, while minimizing some objective function. We consider the case where all tasks are of unit length and the goal is to minimize the sum of the completion times of the jobs. This problem is NP-hard. There is a simple, greedy-type approximation algorithm called SDF (Shortest Delay First) that exhibits acceptable worst-case behaviour for this problem. In [1] Fischer and Györgyi proved that the asymptotic performance ratio (APR) of SDF is smaller or equal than 3/2, but the exact value was unknown. In this talk we prove that the exact value of the ratio is approximately 1.1835. This is the first result that proves a tight APR for a CTP whose objective function is the total completion time. References [1] Fischer, D. & Györgyi, P. (2023), Approximation algorithms for coupled task scheduling minimizing the sum of completion times, Annals of Operations Research, 1--22, https://doi.org/10.1007/s10479-023-05322-5.
Fixed-Parameter Tractability for Steiner Rooted Connected OrientationsKristof BercziFinding a Steiner strongly k-arc-connected orientation is particularly relevant in network design and reliability, as it guarantees robust communication between a designated set of critical nodes. Király and Lau (FOCS 2006) introduced a rooted variant, called the Steiner Rooted Orientation problem, where one is given an undirected graph on n vertices, a root vertex, and a set of t terminals. The goal is to find an orientation of the graph such that the resulting directed graph is Steiner rooted k-arc-connected. This problem generalizes several classical connectivity results in graph theory, such as those on edge-disjoint paths and spanning-tree packings. While the maximum k for which a Steiner strongly k-arc-connected orientation exists can be determined in polynomial time via Nash-Williams' orientation theorem, its rooted counterpart is significantly harder: the problem is NP-hard when both k and t are part of the input. In this talk, we provide a complete understanding of the problem with respect to these two parameters. In particular, we give an algorithm that solves the problem in time f(k,t)*poly(n), establishing fixed-parameter tractability with respect to the number of terminals t and the target connectivity k. We further show that the problem remains NP-hard if either k or t is treated as part of the input, meaning that our algorithm is essentially optimal from a parameterized perspective.
Optimizing Routing Availability Against Localized Disaster ScenariosErika Bérczi-KovácsEnsuring network survivability during regional disasters is essential for meeting stringent SLA availability targets. However, high-availability provisioning through path redundancy often entails excessive bandwidth costs. We formalize the availability-aware routing problem based on risk-zone probabilities, proving it to be NP-hard and inapproximable. To address these computational challenges, we introduce heuristics that balance availability with bandwidth usage by reformulating failure probabilities as capacities. Experimental validation using real-world topologies shows that our methods provide near-optimal results; demonstrating high resilience with minimal resource overhead.
Optimal Energy and Water Utilization Scheduling for Agrivoltaic OperationsBotond Bertok, Balázs Ásványi, Károly KalauzAn optimization method is proposed for the joint scheduling of energy and water utilization in agrivoltaic systems. The approach treats resource management as an optimization problem, accounting for variable solar irradiance and crop-specific needs. The model ensures operational continuity for water pumping, irrigation, and solar tracking, while treating the water reservoir as an integrated energy storage component. In addition to water supply, the model accounts for the light and shade requirements of the crops, as well as fluctuating solar energy market prices and the cooling demands of the photovoltaic panels. The optimization method is based on the process network synthesis approach in the problem formulation and P-graph algorithms in the solution step. Results demonstrate that synchronized scheduling can enhance the synergy between renewable energy production and sustainable farming.
Computing the least core for energy community gamesGiancarlo BigiA coalitional game with transferable utility arising from the analysis of energy communities is introduced as the Energy Sharing Game (ESG). A veto player is needed beyond the prosumers to manage the community, and the worth of a coalition is its benefit compared to the selfish behaviour of the prosumers. the worth of a coalition in ESG is provided by the optimal value of an optimization problem where prosumers control variables, while their presence in the coalition activates constraints and terms in the objective function. Properties of ESG such as superadditivity, monotonicity, convexity and balancedness are analysed both in the presence and absence of admission fees. Then, the least core and its value are studied in detail, underlying the differences between the cases where the game is balanced or not. In particular, an exact formula and computable bounds for the least core value are provided. The computation of the exact formula for the least core value is addressed through suitable families of mixed-integer programs, whose resolution is viable when the underlying optimization problems of the prosumers are linear. Indeed, five different approaches have been developed and tested for problems up to 200 prosumers, and the results show that the fastest is quite efficient. (based on joint papers with D.Fioriti, A.Frangioni, M.Passacantando, D.Poli)
Copositivity-informed relaxations of rigorous sparsity control in StQPs applied to microfinanceImmanuel Bomze, Paula Amaral, Bo PengWe consider the Standard QP with additional hard lower and upper bound constraints on sparsity, allowing not less than a certain number, and not more than a certain larger number, of non-zero entries in all feasible solutions. If the latter exceeds one, then, for continuity reasons, we need semi-continuity constraints on the decision variables, which can be expressed as additional (non-convex) quadratic constraints, so that we arrive at a QCQP with a special structure for which strong copositive relaxations are available. An alternative formulation by a mixed-binary QP (convex in the continuous variables) will also be discussed. In a microfinance context, we want to minimize risk for the organization granting micro-credits while ensuring a minimal number of grantees (and a minimum share of the overall budget). Decomposition and relaxation strategies are presented, along with a short outlook on handling data uncertainty in real-world applications.
Cooperative games with a-priori linksSurajit Borkotokey, Parishmita Boruah, Sujata GoalaThis paper proposes a new framework for cooperative games where players possess pre-existing network connections. Unlike traditional graph-restricted models, our approach integrates network structure directly into the coalition formation process, allowing players' existing connections to influence their worth generation. Within this setup, we first derive the Shapley value, which arises when imposing a classical symmetry condition. Recognizing that pre-existing links often break this symmetry, we introduce a new value: the Link Proportional value. This solution allocates payoffs based on players' connection patterns with their coalition partners. We provide axiomatic characterizations for both values. The model is highly applicable to various allocation problems involving pre-existing network relationships, viz., digital content creation, supply chain management, the co-authorship model, etc., just to name a few.
Probability Bounds via Hypergraph Structures: A Review of Joint Work with Tamás SzántaiJozsef BukszarBounding the probability of the union of events based on limited joint information is a fundamental problem in operations research, with applications in reliability analysis, risk management, and stochastic systems. Classical approaches, such as the Hunter bound and related tree-based methods, rely on pairwise dependencies and graph structures, which restrict their ability to capture higher-order interactions. In this talk, we revisit a line of research conducted jointly with Tamás Szántai, focusing on the development of probability bounds based on hypergraph structures. In particular, we present the concept of hypercherry trees, which extend classical cherry tree representations to hypergraphs and enable the incorporation of higher-order dependencies. These structures yield new upper and lower bounds that generalize earlier results and provide improved flexibility in modeling dependence. We also discuss a broader comparison of bounding techniques, including graph-based and moment-based approaches, highlighting the trade-offs between computational complexity, required information, and bound tightness.
Improved bounds for deterministic algorithms on semi-online scheduling with decreasing processing timesNóra Büki, János Balogh, József BékésiParallel multiprocessor scheduling is a classical problem of on-line optimization, first investigated by Graham, with decades of literature on the general and special cases. In these problems, each input job must be immediately assigned to one of m identical machines. An algorithm's goal is to never create a machine whose load is too high compared to the off-line optimum makespan of the already known jobs. This is denoted by the algorithm's competitive ratio R. In the special case where the input sequence is guaranteed to be non-increasing, tight bounds were proven for m=2 (R=7/6) and m=3 (R=1.180...) by Graham, Seidel et al. and Cheng et al., and a 5/4-competitive algorithm was described by Cheng et al. for any number of machines. We present a 19/16 competitive algorithm for the m=4 case with a matching lower bound, and provide an adversarial input for the m>=6 case for a lower bound of 29/24.
An interior-point approach for risk-neutral and risk-averse multistage stochastic optimizationJordi Castro, Laureano F. Escudero, Juan Francisco MongeA novel approach based on a specialized interior-point method (IPM) is presented for solving both risk-neutral and risk-averse large-scale multistage stochastic optimization (MSSO) problems. The specialized IPM, which is appropriate for problems with block-angular structure, solves the normal equations by combining Cholesky factorizations with preconditioned conjugate gradients. The approach transforms both the risk-neutral and risk-averse MSSO formulations into a block-angular structure by introducing split variables and linking constraints. A broad computational study is reported for large MSSO problems with several stages, hundreds of million of variables and tens of millions of constraints. The proposed approach outperforms state-of-the-art interior-point solvers such as CPLEX by several days of CPU time.
A quantum-classical branch-and-bound algorithmAndrás Czégel, Boglárka G.-TóthWe show a complete quantum-classical hybrid branch-and-bound algorithm to solve binary linear programs with equality constraints. The hybrid algorithm has the traits of branch-and-bound algorithms like convergence metrics and optimality proof, while using quantum optimization in its core to obtain the solutions of the subproblems. It uses the noisy samples from the quantum algorithm to select branching variables with a feasibility jump-like conflict value calculation, a SAT-inspired reduction step between the nodes and a fast LP-free heuristic for bounding calculations. We show numerical results on set partitioning problem instances and provide many details about the characteristics of the different steps of the algorithm.
A Simple 1.5-Approximation Algorithm for a Wide Range of Maximum-Size Stable Matching ProblemsGergely CsájiWe consider the problem of finding maximum-size stable matchings in the presence of ties, a well-known NP-hard problem, by extending the existing 1.5-approximation algorithm to a common generalization of many previously studied and newly introduced models. These include the existence of critical agents, where matching as many of these agents as possible is prioritized; free edges that cannot be blocking edges; and ∆-stabilities, which mean that for an edge to block, the improvement should be at least ∆. We also introduce notions to generalize these further by introducing edge-specific thresholds for each agent, which allow the blocking condition to vary based on the agents and edges, so our framework has a wide range of existing and potential applications. We show that the edge-duplicating technique allows us to treat these different types of generalizations simultaneously while also making the algorithm, proofs, and analysis much simpler and shorter than in previous approaches. In particular, we answer an open question about the existence of a 1.5-approximation algorithm for the Max-SMTI problem with free edges. This demonstrates that our technique successfully exploits a fundamental feature of these problems and has the potential to be useful in many future applications.
Interval Based Verification of Adversarial Example Free Zones for Neural Networks: Dependency Problem RevisitedTibor CsendesRecent machine learning models are sensitive to adversarial input perturbation. That is, an attacker may easily mislead an otherwise well-performing image classification system by altering some pixels. It is quite challenging to prove that a network will have correct output when changing slightly some regions of the images. This is why only a few works targeted this problem. Although there are an increasing number of studies on this field, really reliable robustness evaluation is still an open issue. We will present some new theoretical results on the dependency problem of interval arithmetic what is critical in interval based verification.
Preallocation-based Combinatorial Auction for Efficient Fair Channel Assignments in Multi-Connectivity NetworksDávid CsercsikWe consider a general multi-connectivity framework, intended for ultra-reliable low-latency communications (URLLC) services, and propose a novel, preallocation-based combinatorial auction approach for the efficient allocation of channels. We compare the performance of the proposed method with several other state-of-the-art and alternative channel-allocation algorithms. The two proposed performance metrics are the capacity-based and the utility-based context. We conclude that at the cost of higher but still plausible computational time, the fairness-enhanced version of the proposed preallocation based combinatorial auction algorithm outperforms every other considered method when one considers total system performance and fairness simultaneously, and performs especially well in the utility context. Therefore, the proposed algorithm may be regarded as candidate scheme for URLLC channel allocation problems, where minimal and maximal capacity requirements have to be considered.
Application of a simple ALB model for the robotic assembly of an electronic deviseMáté Csíkos, Tamás KoltaiAssembly Line Balancing (ALB) remains a cornerstone of production optimization, focusing on task allocation to minimize costs and cycle times. While theoretical research has historically emphasized algorithmic complexity, the practical shift toward industrial automation requires flexible and rapid modelling approaches. This paper presents a comprehensive case study of a high-precision optical document reader assembly line, demonstrating how a Simple Assembly Line Balancing Problem (SALBP-2) framework can be effectively applied to real-world robotic environments. Using Integer Linear Programming (ILP), the model aims to minimize cycle time for a dual-workstation configuration, typical in small to medium-lot high-tech manufacturing. The research highlights the strategic transition from complex algorithmic development to practical, decision-oriented modelling that supports rapid operational changes. By decomposing the assembly process into 14 distinct task groups, the study evaluates the impact of technological precedence and synchronization requirements on overall line efficiency. The findings illustrate the trade-offs between workstation configuration and production output, providing a robust decision-support framework for manufacturing managers. This approach validates that even simplified ALB models, when correctly parameterized for robotic integration, offer significant value in optimizing throughput and resource utilization in high-precision assembly environments.
Random descent steps in a probability maximization schemeEdit Csizmás, Rajmund Drenyovszki, Tamas SzantaiGradient computation of multivariate distribution functions calls for considerable effort, a standard procedure being component-wise computation. Hence coordinate descent and derivative-free approaches are attractive. This paper deals with constrained convex problems. We perform random descent steps in an approximation scheme that is an inexact cutting-plane method from a dual viewpoint. We prove that the scheme converges and present a computational study comparing different descent methods applied in the approximation scheme. In our computational study, solver variants applying crude gradient estimates proved more efficient than high-accuracy variants. We presently work on the implementation of specialized descent steps.
Interior-point methods using two distinct classes of AET functionsZsolt Darvay, Petra Renáta RigóIn this talk, we focus on solving P*(kappa)-horizontal linear complementarity problems over Cartesian products of symmetric cones using predictor–corrector interior-point methods. We show that the search directions can be defined via two distinct classes of algebraically equivalent transformations (AETs) of the Nesterov–Todd system. We also discuss the relationship between the AET technique and the kernel-based approach.
SDP analysis of the worst-case convergence for the boosted DCAEtienne De Klerk, Hadi Abbaszadehpeivasti, Adrien TaylorThe difference-of-convex algorithm (DCA) is a well-established nonlinear programming technique that solves successive convex optimization problems. These sub-problems are obtained from the difference-of-convex (DC) decompositions of the objective and constraint functions. We investigate the worst-case performance of the unconstrained DCA, with and without boosting, where boosting simply performs an additional step in the direction generated by the usual DCA method. We show that, for certain classes of DC decompositions, the boosted DCA is provably better in the worst-case than the usual DCA. While several numerical studies have reported that boosted DCA outperforms classical DCA, a theoretical explanation for this behavior has, to the best of our knowledge, not been given until now. Our proof technique relies on semidefinite programming (SDP) performance estimation. This talk is based on joint work with Hadi Abbaszadehpeivasti and Adrien Taylor.
Gradient-Normalized Smoothness for Optimization with Approximate HessiansNikita DoikovIn this talk, we discuss the design of optimization algorithms that use approximate second-order information to achieve fast global convergence rates for both convex and non-convex objectives. The key innovation of our analysis is a novel notion called Gradient-Normalized Smoothness, which characterizes the maximum radius of a ball around the current point that yields a good relative approximation of the gradient field. Our theory establishes a natural intrinsic connection between Hessian approximation and the linearization of the gradient. Importantly, Gradient-Normalized Smoothness does not depend on the specific problem class of the objective functions, while effectively translating local information about the gradient field and Hessian approximation into the global behavior of the method. This new concept equips approximate second-order algorithms with universal global convergence guarantees, recovering state-of-the-art rates for functions with Hölder-continuous Hessians and third derivatives, quasi-self-concordant functions, as well as smooth classes in first-order optimization. These rates are achieved automatically and extend to broader classes, such as generalized self-concordant functions. We demonstrate direct applications of our results for global linear rates in logistic regression and softmax problems with approximate Hessians, as well as in non-convex optimization using Fisher and Gauss-Newton approximations.
Emergency rescue scheduling Gyorgy Dosa, János Balogh, József Békési, Lars Magnus Hvattum, Zsolt Tuza, Béla VizváriThe subject of this talk falls within the scope of post-disaster rescue. Natural disasters are often large in extent. People in need of help can therefore be spread over a large area. The task is to transport injured people to hospital in an emergency situation after a disaster has occurred. Rescue must be organized fairly. This includes the requirement that people should be taken to the hospital as soon as possible. The transportation of every injured and reported person to the hospital is a mission for the transport vehicle, i.e. the ambulance. From the vehicle's point of view, this means that it has to start from a given point, the hospital, visit another point, the patient's location, and then return to the starting point. If the vehicle's capacity admits to transport several people at once, then these missions can be combined, i.e. several locations can be visited within one trip, which can save time. When we consider the possibility of combining, the problem is similar to batch processing. In this way our considered problem has a strong relation with with several areas of optimization, including vehicle routing, and batch scheduling. In our approach, we examine scenarios under which the transport of some injured patients can be combined in the same vehicle. We discuss how this problem relates to the scheduling of batch processing machines. We present exact and approximation algorithms for certain special cases of the problem where the makespan is minimized.
Semismooth Newton methods with global convergence ratesPavel Dvurechensky, Amal Alphonse, Ioannis PapadopoulosWe propose LeAP-SSN (Levenberg-Marquardt Adaptive Proximal Semismooth Newton method), a semismooth Newton-type method with a parameter-free globalisation strategy that guarantees, for minimization problems, nonasymptotic sublinear convergence rate in convex setting and linear convergence rate under the Polyak--Lojasiewicz condition, in Hilbert spaces. The method employs an adaptive Levenberg--Marquardt regularisation for the Newton steps, combined with backtracking, and does not require knowledge of problem-specific constants. The algorithm achieves superlinear convergence under mild semismoothness and Dennis--Moré or partial smoothness conditions. By combining strong global guarantees with superlinear local rates in a fully parameter-agnostic framework, LeAP-SSN bridges the gap between globally convergent second-order algorithms and Semismooth Newton's methods with the fast asymptotic local rates. The practical efficiency of the method is illustrated on representative problems from imaging, contact mechanics, and machine learning. We also propose a modification of this method based on gradient regularization and show that it achieves improved local superlinear convergence under strong semismoothness and is able to work with lazy Hessian updates. The details can be found in https://arxiv.org/abs/2508.16468 and https://arxiv.org/abs/2602.08069.
Optimization of Municipal Waste Collection RoutesAndrás Éles, Olivér Ősz, Marton FritsMunicipal solid waste in large regions is collected at regular intervals by public utility companies using specialized garbage trucks. Designing efficient collection routes is a challenging task due to the large number of settlements and disposal sites, as well as various operational constraints such as vehicle capacity, shift durations, and additional practical rules. Traditionally, route planning has been largely based on prior experience, often inherited from the period before the integration of multiple waste collection companies operating within the region. This work addresses the need for route optimization, with a primary focus on minimizing the total distance traveled and work required. We propose a solution method tailored to the scale and complexity of the problem. Our approach combines spatial decomposition of the service area with heuristic rules and mathematical programming techniques, specifically Mixed-Integer Linear Programming (MILP), to construct high-quality routing plans. The effectiveness of the proposed method is demonstrated through a case study based on real-world data from a Hungarian region.
Structural Approach to Designing Optimal Complex Processing Systems: P-graph FrameworkFerenc FriedlerThe goals concerning efficiency, sustainability, resilience, controllability, and operability constitute appropriate ambitions and targets for researchers when designing, and especially synthesizing, processing systems. Progress in this direction, however, is constrained by the already complex nature of highly interconnected network systems. Even for simple objectives, the applicability of traditional MINLP-type approaches to real-world problems is limited by problem complexity. The latter is significantly increased if, in addition to traditional economic criteria, sustainability, controllability, or operability indicators are considered during design. To overcome this issue, a structure-based reformulation of network design has been performed. It can simply be referred to as an inside-out modeling of processing systems. In this approach, the fundamental structural knowledge implicitly embedded in feasible networks becomes explicit, serving as the formal basis for the P-graph framework. This setup serves both rigor and effectiveness, as well as the long-term development of the theory. The P-graph framework provides new methods for synthesizing complex systems that account for recently identified requirements for resilience, reliability, and controllability. The framework was originally developed for processing systems in the chemical industry; however, its application area now spans a wide range from engineering systems to supply chain management.
Exploring Hybrid Quantum–Classical Methods for P-Graph OptimizationMarton FritsThe P-graph methodology has found applications beyond process network synthesis in several combinatorial optimization domains, including scheduling problems. However, the explicit incorporation of temporal decision variables typically leads to a substantial increase in model size, thereby limiting the tractability of large-scale instances. This difficulty is commonly addressed through heuristic methods or multilevel modeling techniques. In this context, the ongoing development of quantum computing motivates the exploration of alternative computational strategies. Although no general-purpose quantum approach currently exists for the direct solution of P-graph models or for the full realization of Branch-and-Bound within a quantum framework, hybrid quantum-classical schemes may provide a viable research direction. In the proposed setting, the P-graph representation is retained to ensure structural feasibility and to reduce the effective search space, while B&B governs the systematic exploration of candidate solutions. The quantum component is restricted to selected hard subproblems arising at individual search nodes, which may be reformulated as Quadratic Unconstrained Binary Optimization problems. Solving such QUBO instances with quantum optimization subroutines may improve incumbent generation and enhance overall search efficiency in time-expanded P-graph optimization. The presentation will review related research and the proposed methodology.
Advanced geometrical test for optimality conditions in Interval Branch and Bound methodBoglárka G.-TóthThis study focuses on solving constrained nonlinear programming problems. We consider the Fritz-John (FJ) optimality conditions from a geometric perspective. A new, advanced geometrical optimality test is introduced to precede the FJ optimality condition. The goal is to speed up the Interval Branch and Bound (IBB) method and eliminate unnecessary computations. In many cases, the test easily ensures that there is no local optimum in the box, or that we cannot reduce the size of the box by solving the optimality condition system. We will describe the theoretical results for the geometric test and its usefulness, as well as present experimental results demonstrating the effectiveness of the advanced geometrical test.
Completely positive reformulations for sparse quadratic optimizationMarkus Gabl, Bo Peng, Immanuel BomzeWe consider sparse quadratic optimization problems, which distinguish themselves either by a zero-norm term in the objective (soft sparsity) that promotes sparsity of the optimal solution, or by a so-called cardinality constraint (hard sparsity). Sparse solutions are valuable in portfolio optimization, as a sparse portfolio can be managed more cheaply, but also in statistical regression, since sparse regression coefficients are more easily interpreted. We propose copositive relaxations that have fewer variables than Burer's classic reformulation. For the soft sparsity case, we can show that the relaxation is tight, while for the hard sparsity case, we identify cases where it is tight as well. We also propose a hierarchy of cheaper relaxations, whose strength can be understood in terms of the decomposition gap of convex envelopes.
An advanced Interval Branch and Bound Algorithm in the Julia Programming LanguageMihály Gencsi, Boglárka G.-TóthReliably solving nonlinear global optimization problems is essential for some scientific applications. This presentation introduces a Branch and Bound algorithm based on interval arithmetic that provides a mathematical guarantee for finding the global optimum. The algorithm establishes strict lower and upper bounds on the objective function within the search space by applying interval extensions to the functions. This approach effectively handles uncertainties arising from floating-point rounding errors and reliably eliminates irrelevant subregions. Additionally, it naturally ensures that the search does not get stuck in local optima. To accelerate the pruning process, we also evaluated various contractor-based approaches and optimality conditions. Implementing the algorithm in the modern Julia programming language ensures the fast execution of computationally intensive interval operations. We demonstrate the efficiency and robustness of the proposed method using standard constrained nonlinear optimization test functions.
A stochastic model for the spread of epidemic via self-exiting point processesLászló Gerencsér, Zsuzsanna Vágó, Simon OláhWe consider an epidemic that affect a finite population of agents located on a plane, identified as points of that plane. Infection spreads according to a stochastic dynamics defined by a self-exiting point processes introduced by A. Hawkes back in 1971. The terminology points to the fact that the counting measure associated with point process is defined via a closed loop system. Applications in epidemiology call for multivariate Hawkes processes, in which the infection patterns of individual agents have mutual impact on each others’ intensity. We consider a class of multi-variate linear Hawkes processes allowing reinfection which is expected to stochastically dominate more realistic, but unmanageable models. A remarkable feature of our model is that, it can be recursively simulated very efficiently. Simulation results are visualized by animation and plotting the unit time counting process for different scenarios defined by varying the transmission probability and the critical distance around accepted standard values.
Pearl: Perfectly 2-resilient Skipping Routing with Few Header Bits via Cut DecompositionBecsó GergelyTo meet stringent dependability requirements, modern communication networks incorporate local fast rerouting to quickly respond to link failures. However, designing rerouting mechanisms that are resilient to multiple failures is algorithmically challenging, as routing decisions must rely solely on local information. A rerouting mechanism is called perfectly k-resilient if it delivers a packet to the destination for any set of at most k failed links not separating the source from the destination. Achieving perfect 2-resilience is impossible without packet header rewriting: connectivity at the routing layer cannot be guaranteed in the presence of two simultaneous link failures. This paper demonstrates that perfectly 2-resilient rerouting can be achieved if routers are allowed to rewrite a small number of packet header bits. Our approach, Pearl, leverages a cut decomposition of the network. We introduce a novel metric, L, which represents the number of relevant 2-edge cuts from the routing perspective. We propose an efficient forwarding mechanism that ensures perfectly 2-resilient routing using only logarithmic number of header bits. Our method is efficient to compute and builds on skipping routing, where routers only need to store a small number of routing rules. Extensive simulations on real-world networks reveal that the parameter L can be bounded by 6; in practice, resulting in a perfectly 2-resilient skipping routing mechanism with 4, header bits.
Smoothing unadjusted Langevin algorithm for Kurdyka-{\L}ojasiewicz potential functionsSusan Ghaderi, Yves Moreau, Masoud AhookhoshThis paper builds on the theoretical foundation of the smoothing unadjusted Langevin algorithm (SULA), focusing on its ability to sample from posterior distributions that involve nonsmooth potential functions. Specifically, we study functions of the composite form $f+g$, where $f$ is $L$-smooth and $g$ is weakly convex. We first generate a smooth variant of the potential via forward-backward envelope and establish a non-asymptotic convergence of the sequence generated by SULA under the Kurdyka-{\L}ojasiewicz (KL) condition. To demonstrate the practical value of these theoretical results, we apply SULA to matrix completion problems, an area where weak convexity is a common structural feature. Our numerical experiments back up the theoretical claims, highlighting SULA's effectiveness in this key application.
Bernstein–Doetsch-type theorems for generalized convex functionsAttila Gilanyi, Zsolt PalesOne of the fundamental results of the classical theory of convex functions is the Bernstein–Doetsch theorem, which states that if a real-valued Jensen-convex function defined on an open interval is locally bounded from above at a point in its domain, then it is continuous. In this talk, we present such types of statements for generalized convex functions. As our main result, we prove a generalization of the theorem above in the situation when the arithmetic means on the left-hand side and the right-hand side in the defining inequality of Jensen-convexity are replaced by suitable continuous, strict means.
Stochastic Three Points Method with an Inexact Oracle and Its Application to Steady-State OptimizationGeovani GrapigliaWe consider unconstrained derivative-free optimization problems in which only inexact function evaluations are available. The oracle returns function values with partially controllable inexactness, whose error is bounded linearly in a user-specified accuracy parameter, with an unknown proportionality constant. This framework captures optimization problems arising from approximate simulations or experimental evaluations with adjustable fidelity. We propose a variant of the Stochastic Three-Point method that adaptively balances oracle accuracy and stepsizes without requiring prior knowledge of the error bound. We derive complexity bounds on the expected number of oracle calls required to obtain approximate stationary points. As an application, we study model-free steady-state optimization in control systems and show that the resulting oracle satisfies the proposed assumptions.
From Trees to Treewidth: Inventory Management in Complex Supply Chain Networks through parametrized LPsGeorgina Hall, Andre Calmon, Philippe BlaettchenWe propose an exact solution approach to the Guaranteed Service Model (GSM), one of the most widely applied models for optimizing safety stock placement in supply chain networks. Based on linear programming (LP), our approach handles any directed acyclic network and any cost function that depends on a stage's incoming and outgoing service times. It scales polynomially in the number of nodes n in the network, and exponentially in its treewidth, which quantifies how tree-like a network is, and can be much smaller than n. This contrasts with existing approaches, which scale exponentially in n. The proof of exactness of our approach relies crucially on showing that the join of transportation-like polytopes remains integral, and it is more broadly applicable to other Operations Management problems. The use of linear programming makes for straightforward implementation, including when incorporating additional operational constraints. It also enables sensitivity analyses and the construction of principled bounds on the GSM's optimal value. Finally, it allows for the use of standard LP optimization software, resulting in considerable gains in solving time. In particular, we demonstrate that, on real-world data from Willems (2008), we achieve consistent and significant optimization speed-ups compared to the state-of-the-art approach for the GSM and commercial all-purpose solvers.
Enforcing shape constraints using sum of squares polynomialsGeorgina HallMany of the most useful priors in optimization-such as submodularity or convexity-share a common challenge: testing whether a function satisfies these properties, or optimizing over functions subject to them, is computationally intractable. In this talk, we develop a unifying perspective in which such properties are certified using sum-of-squares (sos) polynomials. In the first part, we introduce t-sos submodularity, a hierarchy of sufficient algebraic conditions for certifying submodularity of set functions. For fixed t, each level of the hierarchy can be verified via a semidefinite program of size polynomial in the ground set. We develop algebraic characterizations of t-sos-submodular functions, study when the hierarchy exactly coincides with submodularity, and demonstrate applications to submodular regression, difference-of-submodular programming, and approximate submodular maximization. In the second part, we revisit sos convexity and then focus on convex regression, which involves fitting a convex polynomial to noisy evaluations of an unknown convex function. We study sos-convex polynomial regressors defined via a hierarchy of semidefinite programs and show that these regressors are consistent estimators of the underlying convex function. As a byproduct, we prove that sos-convex polynomials are dense in the set of polynomials convex over a box. We also compare our approach with existing methods, identifying settings in which the sos framework is particularly effective.
From efficiency to stability: A new robustness measure for multiobjective LPMilan HladíkWe study robustness in multiobjective linear programming from the perspective of solution stability under perturbations of cost coefficients. Rather than assuming a fixed uncertainty set, we evaluate how much the costs can vary while preserving optimality of a given efficient solution for some weighted aggregation of objectives. To this end, we introduce the concept of a robustness quotient, which quantifies the largest admissible variation in costs that maintains optimality. We present several equivalent characterizations of this measure and analyze its computational properties. While exact computation is efficient for nondegenerate cases, it becomes computationally hard in general settings. To address this computational hardness, we propose practical lower and upper bounds based on geometric insights and optimization techniques. These approximations are scalable and provide reliable estimates even for large and highly degenerate problems. We also identify conditions under which robustness is trivial or unbounded, both of which can be detected efficiently.
Parabolic Target-Space Interior-Point Algorithm for Weighted Monotone Linear Complementarity ProblemTibor IllésIn this talk we present a generalization of the result of Nesterov (2008), the primal–dual interior-point algorithm (IPA) for LP problems. Similarly to the paper of Nesterov, our approach is based on the concept of parabolic target space (PTS). The concept of weighted central path (WCP) in the literature of LCPs, first occurs in a paper of Illés, Roos, Terlaky (1997). We introduce a relaxation of WCP and show that the solution set of the relaxed problem is convex. Later an additional (convex) constraint on the duality gap of the MLCP has been added. Finally, we arrived at a convex feasibility problem (CFP) that has original variables of the MLCP, and those related to the relaxation and the additional constraint. The new variables, naturally satisfies an extra condition leading to the observation of a PTS. The use of the PTS allows us to discuss the new IPA for both the weighted and classical MLCP at the same time. The solution of an MLCP reduces to the solution of a sequence of CFPs. The driving forth of our new IPA lies in the structure of CFPs and the assigned self-concordant barrier function of CFP, and its properties. This talk is based on the paper: E.-Nagy, M., Illés, T., Nesterov, Yu., and Rigó, P.R.: Parabolic Target Space Interior-Point Algorithms for Weighted Monotone Linear Complementarity Problem. Math. Prog., online: 12 August 2025.
Hypergraph representation of all matroidsÁron JánosikThe Crapo-Rota conjecture suggests that the asymptotic fraction of paving matroids on n elements tends to 1 as n tends to infinity. A consequence of this conjecture would be that almost all matroids share a similar underlying hypergraph structure. This raises the question: is there a similar, even more general underlying structure for all matroids? Building upon a definition by Balcan and Harvey, we demonstrate that with a slight modification, the resulting class, which we introduce as cuptroids, provides such a structure. Furthermore, we define the class of captroids and examine various extensions of these concepts. We prove that cuptroids and captroids are duals of each other and are closed under taking minors while keeping the original structure. Finally, we establish additional properties concerning submodularity-modularity and the cyclic flat lattice, while highlighting several open problems that remain for these new matroid classes.
Difference of high-order Moreau envelopes for DC optimizationAlireza Kabgani, Moslem Zamani, Masoud AhookhoshWe introduce a high-order envelope framework for nonsmooth difference-of-convex (DC) optimization based on generalized proximal regularization. Extending the classical Moreau envelope, we define a p-order DC envelope that preserves key structural properties while enabling smooth reformulations of nonsmooth and nonconvex problems. We establish differentiability of the envelope and derive an explicit gradient representation via high-order proximal mappings. A central result is a precise correspondence between critical points of the envelope and DC-stationary points of the original problem. We further analyze local minimizers, showing that every local minimizer of the DC objective induces a local minimizer of the envelope, and under mild regularity such as local surjectivity of the proximal mapping or differentiability of one component, the converse also holds. Building on these properties, we propose an inexact high-order proximal algorithm and prove convergence under standard descent conditions. The framework provides a unified and flexible approach to smoothing, with potential applications in large-scale and nonconvex optimization.
Production Scheduling Optimization in Cheese Manufacturing Using P-graph MethodologyKároly Kalauz, Erika Lakatos, Anikó VadászEfficient production scheduling in dairy processing, particularly in cheese manufacturing, constitutes a complex decision-making problem involving product mix selection, shift allocation, and resource utilization under persistently high demand. This study addresses the key operational questions of product prioritization and optimal shift configuration. In an industrial context where all produced goods are consistently sold and expiration losses are negligible, the primary objective shifts from demand satisfaction to maximizing production capacity and yield. The research focuses on optimizing existing production processes without immediate capital investment by systematically analyzing current workflows to enhance throughput using available machinery and human resources. The P-graph methodology, a rigorous combinatorial optimization framework derived from Process Network Synthesis (PNS), is employed to model and solve the scheduling and resource allocation problem. The proposed approach enables the identification of optimal production structures, including product prioritization and shift schedules, while revealing process inefficiencies and bottlenecks. Results demonstrate that significant capacity improvements can be achieved through optimized scheduling and process reconfiguration, providing actionable insights and supporting data-driven development decisions.
MORSE: a novel robust multi-objective regression method with genetic algorithm based variable selectionJános Gyula Kisházi, Tamás Kegyes, Tibor DulaiPredictive supervised machine learning models rely on the assumption that the relationships identified within the training data will remain stable and therefore valid during future use. However, in real-world applications, the relationships between explanatory variables and the target variable—as well as their underlying structures and magnitudes—often change. Empirical evidence suggests that the degradation in predictive performance is often more pronounced than the magnitude of the environmental change itself. One way to mitigate this degradation and achieve better parameter balance is by selecting the most stable explanatory variables. We propose a new combined objective function which used by a multi-objective genetic algorithm to select a robust model with the most appropriate input features. Our approach simultaneously maximizes the predictive power weighting classical predictive indicators and newly introduced indicators such as correlation sign consistency metric. Since this consistency metric is a non-differentiable, step-like constraint, it strictly necessitates advanced metaheuristic optimization. Experiments on real-world datasets demonstrate that exploring the Pareto-front yields a highly robust, sparse model. The algorithm effectively filters features, guaranteeing interpretability and long-term stability without sacrificing predictive accuracy.
Directional t-convexity in ordered normed spacesTibor KissDirectional convexity of sets plays a significant role in the theory of convex integration. In this setting, the line segment determined by two points of the set is again contained in the set, provided that the difference of the points belongs to a fixed set, typically a convex cone. Existing results in this area are typically formulated in finite dimensions. In the talk, we present results that hold in normed spaces of arbitrary dimension, further generalize this conditional notion of convexity, and investigate the topological properties of sets that are convex in this extended sense. We also examine the connection with the classical framework and provide a procedure for computing the corresponding convex hull.
QUBO-solving heuristics based on physics: the perspective of simulated bifurcationMátyás KoniorczykThe appearance and availability of DWave quantum annealer has attracted a relevant attention in the applications of quadratic binary optimization and the development of various classical and physics-motivated solvers. While quantum hardware, in spite of its tremendous development, has not lead to a really convincing breakthrough, it motivated the development of various interesting alternatives. The present work focuses on simulated bifurcation machines proposed by Goto et al. recently. We briefly revise the operating principles of the algorithm. Using a cloud GPU implementation by quantumz.io and address certain QUBO problems, including mixed Hamming packings and k-sparsest subgraphs using this solver. Our experiments show that this approach is a very efficient and powerful heuristic for QUBO problems that could readily address problems of practical relevance.
On the robust bilevel toll setting problemAndrás Kovács, Tamas KisThis talk addresses the robust bilevel toll setting problem in which a leader sets edge tolls in a network while multiple followers choose their shortest paths between given source–target pairs. Followers’ edge costs are uncertain and originate from a polyhedral uncertainty set. The leader seeks to maximize its worst-case revenue, anticipating the most adverse realization of followers’ costs and their optimal routing responses. The talk provides a comprehensive analysis of the problem, covering complexity results and showing that its supremum is, in general, not attained. Then, a recent generic framework for robust bilevel optimization is applied for solving the problem, combining (i) a single-level MILP reformulation over a discrete uncertainty set, (ii) a worst-case follower response problem, and (iii) computing a characteristic uncertainty realization to be added to the discrete uncertainty set. These steps are iterated until the solution approaches the supremum on the original polyhedral uncertainty set with a given, arbitrary small margin. Computational experiments on networks with up to 100 vertices and 10 followers demonstrate that small instances are solved within seconds, while larger instances remain challenging. The main computational bottleneck is the discrete-uncertainty subproblem, showing a significant complexity increase compared to the deterministic case. The talk concludes with directions for future research aimed at improving computational efficiency.
The blooming of the Cherry TreesEdith KovácsCherry tree probability distributions were introduced in [1] and [2]. The talk will begin with a reflection on some of our fundamental results that integrate ideas from graph theory, information theory, and probability theory. From these early contributions, numerous research directions and applications have emerged, influencing subsequent work related to this field. The presentation will also offer a personal perspective on the joint work carried out with Tamás Szántai, honoring his contributions and memory. [1] Kovács, Edith, and Tamás Szántai. On the approximation of a discrete multivariate probability distribution using the new concept of t-cherry junction tree. Coping with Uncertainty: Robust Solutions. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 39-56. [2] Szántai, Tamás, and Edith Kovács. Hypergraphs as a mean of discovering the dependence structure of a discrete multivariate probability distribution. Annals of Operations Research 193.1 (2012): 71-90.
Algorithms for Identifying the Crucial Decisions and Generating Strategic N-best Process StructuresBertalan Kovács, Botond BertokWhen synthesizing process networks, P-graph algorithms have the practical benefit of resulting in the N-best optimal and near-optimal process structures efficiently. However, the N-best often include a set of networks differing only marginally from the optimal one. For instance, two alternative routes between the same locations may differ only by a single turn. In contrast, in most applications, we expect alternative networks to be substantially different from each other. In multilevel optimization, strategic decisions at the upper levels substantially limit the availability of resources in the lower levels of alternative cases or constructive time periods. In most decision support systems the aim is to analyze N-best strategic decision alternatives instead of the N-best incomplete utilization of already available resources. In this work, first a modified branch and bound algorithm is proposed for efficient enumeration of the strategically N-best process networks by modifying both the decision variable selection and branching. Second, we propose an algorithm to identify those elements in the initial maximal structure whose inclusion or exclusion have significant consequences for the rest of the network, which can reduce the need for domain-specific knowledge when selecting strategic operating units. The proposed methods generate more diverse alternatives when synthesizing the N-best networks of a given process network synthesis problem and will be illustrated by case studies.
Comparison of heuristic solution methods for the Merge Scheduling ProblemMiklós Krész, Daniil Baldouski, Balazs DavidIn laboratory quality assurance environments, products undergo a series of analyses on specialized machines within strict time constraints, with each analysis overseen by a qualified supervisor. The Merge Scheduling Problem (MSP) is introduced as a generalization of the open-shop scheduling problem in which operations of the same category may be merged and processed jointly on a compatible machine, subject to supervisor capacity and qualification constraints. Each operation belongs to a job with an arrival time and a deadline. A merged operation must be supervised throughout its processing by a qualified supervisor, and each supervisor can oversee a limited number of jobs simultaneously. Two objectives are considered: minimization of makespan and minimization of total tardiness. An exact mixed-integer linear programming formulation is proposed that integrates the merging of operations, machine scheduling, and supervisor assignment. To address the computational intractability of the exact model on larger instances, a two-phase decomposition heuristic is developed. The first phase merges compatible operations and assigns the merged operations to machines and supervisors using a polynomial-time graph-based procedure. The second phase schedules the resulting merged operations on the fixed resource assignment through a metaheuristic search. Various search procedures are considered and the resulted two phase MSP solution methods are evaluated on a dedicated benchmark instance set.
Adaptive heavy-ball-like stochastic gradient methods with reshuffling for unconstrained finite sum problemsNataša Krklec Jerinkić, Federica Porta, Simone RebegoldiWe consider unconstrained finite sum problems, nonconvex in general, and propose a first order method based on mini-batch stochastic gradients sampled by reshuffling techniques. The Armijo-like line search is performed over the sliding window along the direction that estimates the overall gradient by combining the current and the previous approximates, resembling the heavy-ball approach. We prove almost sure convergence result under assumptions that cover a wide range of machine learning problems. A constant step size variant of the method is also analyzed, providing some complexity bounds for the strongly convex case. The conducted numerical study on multi-class image classification tasks shows efficiency of the proposed methods and their advantages with respect to the relevant existing approaches.
Augmented Lagrangian method for solving the sparsest k-subgraph problem as a QUBORoman Kuzel, Mátyás Koniorczyk, Janez PovhRecently there has been a renewed research interest in quadratic unconstrained binary optimization (QUBO) problems, partly driven by the appearance new quantum devices and quantum-motivated heuristics to solve them efficiently. However, most of the practically relevant binary optimization problems are constrained, and even though there is a relevant literature on constrained binary problem to QUBO transformation, there is still no royal way. In the present contribution we employ the augmented Lagrangian Method for a particular problem: the k-sparsest subgraph, in which there is an equality constraint on the Hamming-weight of the solution vector. We derive necessary and sufficient conditions for an augmented Lagrangian QUBO formulation of the problem to be equivalent with the constrained quadratic binary formulation for this case, which serves as the basis for the practically implementable iterative method. We present extensive experimentation with randomly generated instances solved both with classical QUBO heuristics and D-Wave quantum annealers, illustrating the efficiency and the details of the behavior of our algorithm.
Connecting Europe Through Hydrogen: Cost Allocation Analysis of Cross-Border Pipeline Coalition under Varying Subsidy PoliciesArthur Emmanuel Kwesi, Tamás SolymosiOne of EU’s ambitious targets is to develop hydrogen (H2) pipeline network of 53,000 km across the whole of Europe by 2040. The vision is to repurpose 60% of the existing gas pipelines and create 40% new pipelines that will transport green hydrogen from regions of abundance renewable energy sources potential to regions that require imports to meet their demand. While this vision, championed by European Hydrogen Backbone (EHB) promises the flow of 14M tonnes of low-carbon hydrogen energy within the continent, its infrastructure deployment requires huge capital costs. Subsidies are essential to de-risk such investments and to foster collaboration among EU countries and stakeholders. The absence of a coordinated pipeline may lock regions into localized hydrogen ‘islands’, limit trade, increase H2 price volatility and slow down overall hydrogen economy. As a result, we model cross-border hydrogen pipeline development as a cooperative game theory with transferable utility to investigate how varying financial subsidy rates incentivize full cooperation. Maximum subsidy rates of 30% and 50% were adjusted exogenously for different coalition sizes to examine the grand coalition formation. We show that under progressive subsidy designs, grand coalition formation is beneficial to all players. Our work suggests that a uniform rate subsidy structure may inadvertently disincentivize cooperation by favoring bilateral agreements or smaller coalition groupings
Complexity analysis of Interior-Point Methods for P ∗ (κ)-LCPs based on Standard Kernel FunctionsGoran Lesaja, Zsolt Darvay, Marianna E.-Nagy, Anita VargaWe present an interior-point algorithm for P ∗ (κ)-Linear Complementarity Problems, based on a barrier function defined by a new class of univariate kernel functions, called Standard Kernel Functions (SKFs). A comprehensive and unified complexity analysis of the algorithm is provided, and a general procedure is developed to determine the iteration bounds for long-step and short-step versions of the method for the entire class of SKFs. We illustrate the general procedure by determining the iteration bounds for several parametric SKFs, including, as special cases, all eligible kernel functions from the literature with rational or exponential barrier terms. In all cases, we match the best-known iteration bounds from the literature for these special cases of SKFs.
Problems regarding the geometry of Pareto efficient weight vectorsEmma Lukács, Kristóf Ábele-Nagy, Sándor BozókiPairwise comparisons are a corner stone of several fields, such as multicriteria decision making and psychology. A weight vector obtained from a pairwise comparison matrix (PCM) is Pareto efficient if its approximation of the matrix cannot be improved for any element of the matrix without worsening it for another element. Some of the popular weight calculation techniques (e.g., the eigenvector method) do not provide Pareto efficient weight vectors, making the puzzling problem of Pareto efficiency even more important in the area. The presented results regarding the geometry of Pareto efficient weight vectors are threefold. First, the geometric meaning of the Pareto domination of a vector is demonstrated for smaller matrices. Second, the geometry of Pareto efficient weight vectors in the case of 5 alternatives are considered. Finally, the algebraic and geometric approaches investigated in the literature regarding Pareto efficient weight vectors are connected.
Mirror descent with barriersYura MalitskyThere are two primary ways of analyzing the mirror descent algorithm for smooth optimization: one based on the descent lemma and the other on relative smoothness. However, neither approach can handle the case when the mirror map is a barrier function, due to its blow-up on the boundary — such as the popular log-barrier. In this talk, we will suggest a new way of analyzing the algorithm for when the mirror map is a self-concordant barrier. As a side note, this approach leads to a different interpretation of interior point methods, which is of independent interest.
Efficient computation of the classical bound of Bell correlation and prepare-and-measure witnessesIstván MártonWe present a program that speeds up the large-scale computation of the local bound of correlation Bell inequalities, as well as the classical dit bound of prepare-and-measure witnesses with binary outputs. The associated norms are also relevant in communication complexity, the study of the Grothendieck constant, and graph theory. The efficiency of our implementation relies on specialized mathematical and programming techniques, including the use of Gray codes and a customized Branch-and-Bound method commonly employed for solving NP-hard problems.
A Las-Vegas Pruned Cutting-Plane Method for Highly Constrained Convex OptimizationBalázs Miavecz, Balázs CsájiThis work addresses the computational difficulties of solving highly constrained convex optimization problems, where the number of constraints vastly exceeds the number of original decision variables (there could also be auxiliary slack variables). Such problems naturally arise in machine learning and control theory, e.g., in reinforcement learning (RL), support vector machines (SVMs), and stochastic model predictive control (MPC). Here, we introduce Batch Optimization via Softmax Selection (BOSS), a novel randomized cutting-plane algorithm designed for this highly-constrained setting. Unlike traditional methods that process the entire constraint set at once or rely on complex machine learning surrogates for active cuts, BOSS iteratively constructs the support constraint set using only geometric pruning heuristics, a probabilistic exponentially-weighted (softmax) sampling method over constraint violations, and a dynamically growing bounded truncation domain for subproblems. Although BOSS is randomized, it always terminates with an optimal solution, making it a Las Vegas-type algorithm. We present numerical experiments with over a million constraints on random Linear Programs (LPs) and soft-margin SVM problems (using the 1-slack formulation) to demonstrate that, for these problems, BOSS can significantly outperform general purpose state-of-the-art solvers, such as Gurobi, Clarabel and HiGHS. This work was supported by NKFIH via the ADVANCED project 153390.
Mixed Hamming-packings for benchmarking QUBO solversPéter Naszvadi, Mátyás Koniorczyk, Marcell TukoraIn a recent work (Naszvadi, Adam and Koniorczyk, Mathematics 2025, 13(16), 2633) we have introduced an ILP model for solving the code-theoretic problem of finding the maximal cardinality of codes with a minimum codeword Hamming distance. Our method is not based on algebraic structure of the alphabets, it is suitable for decomposing bigger problem instances into equivalent smaller ones, and can be rewritten to a quadratic binary unconstrained optimization (QUBO) problem in a straightforward manner. Owing to the recent development in hardware and software QUBO heuristics and exact solvers, our aim was to find a set of useful problems which can be suitable as a benchmark in the meantime. Our problem is well-studied in code theory, the relevant bounds are known, and the instances are often hard even in the case of small problem sizes. It also gives room for comparison of ILP solvers' behavior with QUBO solvers. Here we present an analysis of our problem instances when solving with exact and heuristic QUBO solvers, including the DWave quantum annealer.
QUBO formulations for minimizing breaks in sports timetablingViktória Nemkin, Levente GegőScheduling sports leagues is an interesting combinatorial optimization problem with many real-world applications. A common format is the double round-robin tournament, in which every team plays every other team twice, once at home and once away. Various constraints may be imposed, such as requiring specific teams to play on a given date at the request of broadcasters. A natural objective is to minimize breaks (when a team plays two consecutive home or away games), improving fairness for players and revenue for stakeholders. Over the past thirty years, this problem and its variants have been studied using Integer Programming (IP), Constraint Programming (CP) and Quadratic Unconstrained Binary Optimization (QUBO), among other approaches. For harder instances, multi-phase methods have been proposed, in which home-away patterns and team pairings are generated in separate steps. In this paper, we present and compare two single-phase QUBO formulations for break minimization in double round-robin tournaments: a permutation matrix encoding and a sorting-network encoding based on recent work. The sorting-network formulation uses asymptotically fewer variables and sparser interactions, but requires ten times more variables for practical problem sizes due to large constant factors. While the permutation matrix encoding is more compact in practice, the sorting-network formulation has substantially lower vertex degrees, which may benefit minor embedding on future hardware.
Universal Complexity Bounds for Universal Gradient Methods in Nonlinear OptimizationYurii NesterovIn this talk, we provide the universal first-order methods of Composite Optimization with new complexity analysis. It delivers some universal convergence guarantees, which are not linked directly to any parametric problem class. However, they can be easily transformed into the rates of convergence for the particular problem classes by substituting the corresponding upper estimates for the Global Curvature Bound of the objective function. We analyze in this way the simple gradient methods for convex composite optimization and their accelerated variant. For them, the only input parameter is the required accuracy of the approximate solution. The accelerated variant of our scheme automatically ensures the best possible rate of convergence simultaneously for all parametric problem classes containing the smooth part of the objective function.
Synthesis of Processing Systems with Various Reliability RequirementsÁkos Orosz, Zoltán Kovács, Ferenc FriedlerProcessing systems are networks of operating units designed to perform a desired transformation. Reliability is a key indicator in industrial processes, as it defines the probability of operation through a given time horizon. To satisfy the required reliability, designers of processing systems introduce redundant operating units. Considering a processing system as binary is not beneficial in real applications. Thus, previous works have introduced redundant operating units with reduced capacities, resulting in systems capable of reduced operation in case of failures. This, however presents novel challenges for process synthesis due the need to determine redundant capacities. The current work exploits the capabilities of the P-graph framework to design processing systems where different reliability requirements are defined for multiple operation levels of the processing system. Furthermore, the proposed method does not restrict the operating units to discrete capacities, instead algorithmically determines the capacities as part of the synthesis procedure. The proposed method simultaneously performs processing systems synthesis for the desired levels of production while satisfying the constraints on reliability by systematic enumeration of feasible networks via a customized branch-and-bound algorithm. Demonstration via a case study shows the capabilities of the method for generating not only a single solution, but the n-best solutions which satisfy the reliability constraints.
AS-BOX: Additional Sampling Method for Weighted Sum Problems with Box ConstraintsTijana Ostojić, Natasa Krejic, Nataša Krklec JerinkićWe consider a class of optimization problems characterized by a weighted finite-sum objective function subject to box constraints. We propose a novel stochastic optimization method, named AS-BOX (Additional Sampling for BOX constraints), that combines projected gradient directions with adaptive variable sample size strategies and nonmonotone line search. The method dynamically adjusts the batch size based on structural consistency of the projected direction, enabling efficient progress toward stationary points while reducing the number of costly full gradient evaluations. We establish almost sure convergence under standard assumptions and provide complexity bounds. Numerical experiments demonstrate the efficiency and competitiveness of the proposed method compared to state-of-the-art stochastic interior-point algorithms.
Separation theorem for nonlinear inverse images of convex setsZsolt PálesIn this talk we deal with first- and higher-order necessary conditions for the local disjointness of a finite system of sets that are nonlinear inverse images of convex sets. The proof is based on the characterizations of α-admissible and alpha-tangent variations to nonlinear inverse images of convex sets and a necessary condition for the local disjointness in terms of these variations. As an application, the results are used to obtain first- and higher-order necessary conditions of optimality in constrained nonlinear optimization problems.
Learning continuous Generalized Naïve Bayes from dataAbraham Papp, Botond Szilagyi, Edith KovácsWe introduce the Generalized Naïve Bayes structure for the case of continuous explanatory variables. This work is an extension of earlier works [1], [2], [3]. We discuss separately the case when the explanatory variables have a joint Gaussian distribution respectively the general continuous case. We introduce algorithms for learning this structure from data to be used for the classification task. We illustrate the algorithms on real datasets and compare the results with other machine learning algorithms used for classification. [1] Kovács, Edith, and Tamás Szántai. On the approximation of a discrete multivariate probability distribution using the new concept of t-cherry junction tree. Coping with Uncertainty: Robust Solutions. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. 39-56. [2] Szántai, Tamás, and Edith Kovács. Hypergraphs as a mean of discovering the dependence structure of a discrete multivariate probability distribution. Annals of Operations Research 193.1 (2012): 71-90. [3] Kovács, E. A., Ország, A., Pfeifer, D., & Benczúr, A. (2025). Generalized Naive Bayes. Pattern Recognition, 112927.
Integrated Optimization of Land Use and Supply Chain Structures for Regional Agricultural ProductsJean Pimentel, Erika Lakatos, Rita Székelyhidi, Botond BertokThe extraction of valuable products from agricultural resources constitutes a relevant economic and societal pillar in various countries. This sector typically operates within complex supply chains that involve numerous producers, intermediaries, and final consumers. Productivity in this sector depends on effectively coordinating the limited resources available in the region, such as land and labor, while minimizing costs and ensuring continuous production. In this work, we propose an optimization approach designed to identify the most efficient supply-chain configurations for generating additives and spices from regional vegetable species. First, we develop a mixed-integer programming optimization model that supports decision-making regarding the elements that should be integrated in the supply chain. This model considers not only production, transportation, and manufacturing costs but also the planning of land use for distinct crops and seasonal variations. Subsequently, we solve the mixed-integer programming model via a graph-theoretical approach that enables the identification of the best alternative supply-chain structures, thus providing decision-makers with additional insights into the problem. This methodology can be potentially extended across regions and become a valuable tool to support sustainable regional development efforts.
Global convergence of scaled Polyak subgradient method for robust phase retrievalMorteza Rahimi, Masoud AhookhoshThis study is devoted to the class of weakly convex functions satisfying quadratic growth condition. The convergence analysis of the subgradient algorithm with scaled Polyak’s step-size to global minima for this class of functions is studied. The preliminary numerical experiments on the robust phase retrieval problem indicate promising behavior for the method, validating our theoretical foundations.
Interior-point algorithm based on a universal tangent directionPetra Renáta Rigó, Marianna E.-Nagy, Tibor IllésWe introduce a parabolic target space interior-point algorithms for solving linear programming problems which is based on a universal tangent direction. The method works in a lifted space and it is based on a parabolic barrier function. We prove that the proposed algorithm has the best known worst-case complexity bound.
Efficient Gradient Methods for Functions with Super-Quadratic CurvatureAnton Rodomanov, Nikita DoikovWe study the problem of minimizing a convex function by gradient methods when the function is continuously differentiable but may grow faster than a quadratic at infinity (for instance, a polynomial of degree greater than two). In this setting, the objective is not Lipschitz-smooth, and the traditional complexity theory of gradient methods does not provide meaningful efficiency guarantees. One possible approach with provable complexity bounds is the Bregman method based on the framework of relative smoothness. However, this approach has several drawbacks: constructing a suitable prox-function typically requires detailed prior knowledge of the objective's structure and additional problem-dependent data, and each iteration requires solving a nontrivial nonlinear equation. We show that this problem can instead be solved using more classical gradient methods with much simpler iterations while still achieving comparable efficiency guarantees. One particularly interesting example is the $\epsilon$-Polyak method, which requires knowing only the target accuracy $\epsilon$ and no other problem-dependent parameters.
Machine Learning-Driven Optimization Framework for Freight EV Charging Infrastructure Planning Using Traffic Forecasting DataMaryam RoudneshinThe transition toward low-emission freight transportation requires strategic deployment of electric vehicle (EV) charging infrastructure under increasing uncertainty in traffic demand. This study proposes an integrated machine learning and optimization framework for EV charging infrastructure planning using traffic forecasting and spatial transport data. Traffic datasets obtained from national road monitoring systems are used to develop predictive models capable of estimating future transport demand across road networks and mobility corridors. The forecasted demand values are incorporated into a facility location optimization model to identify suitable charging station locations while avoiding excessive spatial clustering of infrastructure. The proposed methodology is applied to a national-scale transport dataset to evaluate the effectiveness of combining predictive analytics and optimization techniques for sustainable mobility planning. Results demonstrate that integrating forecasted transport demand into infrastructure planning can improve the spatial allocation and coverage of charging facilities compared with static approaches based solely on historical
Learning-Based Estimation of Traveling Salesman Route LengthAndrea Rožnjik, Karlo Bala, Nebojša GvozdenovićEfficient evaluation of route costs is a key challenge in large-scale Vehicle Routing Problems (VRPs), where solution procedures require repeated cost recomputation for many routes. Individual routes in a VRP solution are equivalent to, or generalizations of, Traveling Salesman Problem (TSP) solutions, making TSP optimization a fundamental yet computationally expensive component, and thus a major bottleneck. In this paper, we propose a learning-based approach for estimating TSP route length directly from the set of assigned locations, without explicit route construction. The model uses a binary encoding of locations and a fully connected neural network to predict route length. It is trained on synthetically generated samples of locations from a fixed set of 2682 locations from the CVRPLIB benchmark, with diverse spatial distributions including random, clustered, and angular patterns. The approach is evaluated using multiple metrics, including pairwise ranking accuracy, with additional analysis across route sizes and data types. Results show well-calibrated predictions with balanced overestimation and underestimation. We observe that unbiased estimation leads to partial error cancellation in multi-vehicle settings. The proposed model provides a fast surrogate for TSP evaluation, enabling more efficient exploration of the solution space in complex routing problems.
Stochastic and derivative-free optimization with trust regionsSara Shashaani There is growing interest in optimizing noisy black-box objectives that are non-convex in expectation, a setting that arises broadly in engineering and machine learning. A key goal is to develop methods that, beyond strong convergence and sample-complexity guarantees, also provide clear implementation guidance for reliable finite-time performance. Trust-region methods offer a principled framework for nonconvex stochastic and derivative-free optimization through adaptive step sizes and model-based exploitation of curvature. This talk highlights how trust-region schemes can be used to construct sample-efficient algorithms with almost-sure complexity guarantees that match second-order rates in deterministic derivative-free settings. I will also discuss practical advantages and theoretical trade-offs associated with strategies for quadratic regularization, variance reduction, and mitigating curse-of-dimensionality.
Comprehensive model generation and solution method for chemical engineering process design including separation network synthesis and heat integration by P-graphsSzonja Sipos, Botond BertokChemical engineering processes always include at least one reaction which takes place in a medium, consequently additional operations are needed to separate the product from the byproducts. The separation is often realized by distillation. Due to the heating and cooling needs, separators may have high energy demands, the cost of which can be reduced by heat integration. The aim of the process design is to determine the most optimal network leading to the final products from the raw materials with minimal cost. To get a global optimal solution, not only a mathematical programming model and solution method is required, but also a model generator algorithm which provides a model mathematically proven to include at least one optimal solution. Such rigorous model generation is provided by the P-graph framework for conceptual process design, and algorithm SNS-LMSG for separation network synthesis. The current paper introduces a model generator algorithm for the heat integration component of the process design problem introduced above. The model resulting is in the form of a P-graph. As a result, a comprehensive algorithmic solution method is given. The proposed method guarantees the globally optimal solution of a practical problem within the framework of P-graphs, and has potential to result practically better solutions than sequential approaches. The model generation, solution, and analysis of the results will be illustrated by a case study of vinyl-chloride monomer production.
Coalition formation and cost allocation in subsidized pipeline developmentsTamás Solymosi, Emmanuel Kwesi ArthurInspired by a case study of a European cross-border hydrogen pipeline development project, we apply linear optimization and cooperative game theory to model and analyze the potential for incentivizing cross-border collaboration through external financial support. We examine various objectives of the external financier for subsidy rate schemes that support the formation of the grand coalition of all involved nations. The situation is modeled as a cooperative cost game where only groups of countries that develop both the internal and cross-border segments of the pipeline are eligible for subsidies. The main question is: under which subsidy rate schemes is the core of the resulting pipeline cost game non-empty? We also utilize refinements of the core, specifically, the least core and the nucleolus, to recommend allocations of the total subsidized cost that ensure stable incentives for countries to participate in the pipeline development project.
A human resource allocation problem considering time periods and uncertaintyTamás Storcz, Zsolt Ercsey, Nándor VinczeHuman resource allocation is the appropriate scheduling and assignment of available people within the organisation to tasks. The solution should meet the business requirements while labour constraints should also be satisfied. Further, there are sometimes comfort expectations of the people which should also be considered. Here a human resource allocation problem is defined and solved where uncertainty of the business requirements arose in the form of uncertain amount of workload during various time periods within the considered time horizon. A regular task is to suggest the minimum number of people required in house. It is often difficult, however, to estimate the actual workload sharply beforehand for a given time period. This means that in a given period it is possible that more (or less) people are required in house than planned to properly finish all and every activity. Obviously, this uncertainty also needs to be managed. Here, we are looking for the answer when to call in workers with different competencies in-house, and for how long, while the primary goal is to minimize unnecessary in-house labor for a given period. The solution presented is based on a p-graph model, where the completion of work of a time period is represented by a product. Based on the process network, a fuzzy MILP model is given. An example illustrates the efficacy of the method.
The subsets of comparisons of complete pairwise comparison matrices with the same cardinality and the logarithmic least squares methodZsombor Szádoczki, Sándor Bozóki, Vitaliy TsyganokPairwise comparisons are widely used in preference modeling, multicriteria decision making, sports and ranking problems. The collected comparisons are often represented by undirected graphs, and the minimal set of comparisons that result in a unique weight vector are represented by spanning trees. It has been previously proven that the weight vector determined by the popular logarithmic least squares method (LLSM) can be calculated as the geometric mean of the weight vectors obtained from all the spanning trees of the graph of comparisons in the case of complete and incomplete pairwise comparison matrices (PCMs) as well. Here, we prove and demonstrate that the same result is true not only for the spanning trees, but for the geometric mean of the weight vectors calculated from the connected subgraphs of the graph of comparisons with the same cardinality (number of edges) for any such cardinality for complete PCMs. However, it is also shown that this is (in general) not true in the case of incomplete pairwise comparison matrices.
Parameter Robustness Of Neural NetworksAttila Szász, Balázs BánhelyiArtificial neural networks (ANNs) are widely used across various domains, such as image and speech recognition. While their accuracy has continuously improved, these networks remain vulnerable to errors. Most current methods address this by focusing on input space vulnerabilities, aiming to make networks robust against input perturbations (often referred to as adversarial examples). However, a less studied issue is vulnerability within the parameter domain. Parameter robustness is crucial not only for defending against direct attacks but also when networks are deployed in different numerical environments, such as during quantization. In this work, we propose a novel algorithm that trains neural networks to be robust against both parameter and input perturbations simultaneously. We trained several networks using our approach and compared the outcomes to state-of-the-art methods. The results demonstrate that our proposed algorithm achieves superior performance across multiple comparisons.
A P-graph-based Exact Approach for Agile Project SchedulingTünde Tarczali, Marton Frits, Zoltan SuleAgile project scheduling becomes particularly challenging when precedence constraints, activity selection, and resource limitations must be addressed simultaneously. In such cases, heuristic and metaheuristic approaches are often applied, especially when projects involve alternative execution paths. This paper proposes an exact scheduling approach based on the P-graph framework. The proposed model combines a matrix-based project representation with a time-indexed P-graph superstructure, in which activities are represented by feasible start-time alternatives over a discrete planning horizon. Precedence requirements are enforced through completion-state nodes, while resource constraints are incorporated through time-dependent resource states and transfer activities. Token-based constructs ensure that each task is selected at most once, thus integrating activity selection, scheduling, and resource allocation. The applicability of the approach is illustrated through a small example and evaluated on a benchmark set derived from 133 real-life project plans. The results indicate that the model reproduces the reference values with negligible deviation, while the observed computation times remain within a practically acceptable range. The findings confirm that the P-graph-based exact approach constitutes a viable alternative to metaheuristic methods in agile project scheduling, particularly where accuracy and transparency are important.
On the 70+ Years of Interior Point MethodsTamás Terlakyn 1954, Ragnar Frish proposed a “Logarithmic Potential Method” to solve Linear Optimization (LO) problems, and he also extended the methodology to solve convex optimization problems. In the 1960’s Fiacco and McCormick studied and expanded the logarithmic barrier methodology as SUMT: Sequential Unconstrained Minimization Technique. The modern age of polynomial time Interior Point Methods (IPMs) has been launched by Karmarkar’s 1984 paper. In the past four decades IPMs transformed the way we think of optimization; expanded the scope of efficiently solvable optimization problems from linear to smooth-convex and conic LO. The powerful methodology of IPMs impacted most areas of optimization, including general nonlinear and combinatorial optimization, and most recently emerged as key methodology in quantum computing optimization. This talk reviews the major milestones of the 7 decades of the Interior Point Revolution.
A human resource allocation problem as a well solvable, k-wide l-hierarchical PNS problemMóric Váradi, Zsolt Ercsey, Tamás StorczA process graph or P-Graph in short is a unique bipartite graph representing the structure of a process system. It is well known in the field of chemical engineering as well as in allied industries. In case we consider the process network design problem from the structural point of view, the corresponding combinatorial optimization problem is called PNS problem. Industrial problems may be complex and difficult to solve, therefore it is of high importance to identify well solvable subclasses offering fast solutions. An example of a well solvable class is called k-wide l-hierarchical PNS problem, introduced by Cs. Imreh. In the field of human resource management, there is a problem of finding work assignments for employees within a given time horizon in a company using a multicommodity network flow model. There, in the multicommodity network flow model, the product of each arc of the graph identifies a work force and the direction of the flow represents the time between starting work and completion of work. In the current work, this multicommodity network flow model is transformed into a PNS problem. As a crucial step of the model transformation, the multicommodity network is first mapped into a p-graph, which includes cycles. As the next step, this network is further transformed into a cycle-free p-graph. It is shown, how this final graph meets the criteria of k- wide l-hierarchical PNS problems, a proved well solvable class of PNS problems.
Dual certificates of primal cone membershipAnita Varga, David PappIn this talk, we introduce dual certificates of membership in a cone, which are easily verifiable and rigorous certificates represented by vectors in the dual cone. This concept complements the classical duality theory, where members of the dual cone are associated with separating hyperplanes and are thus interpreted as certificates of non-membership. We show that dual certificates can be efficiently computed numerically, using interior-point algorithms. Applying this concept to conic optimization problems enables the computation of both rigorously certifiable lower and upper bounds from the same strictly feasible dual solution. The gap between these bounds tends to zero as the dual solution approaches optimality. Besides presenting the definitions and most important properties of dual certificates, we also briefly discuss possible applications.
Nonmonotone Line Search and Additional Sampling in Penalty Methods for Nonlinear Equality-Constrained Finite SumsNemanja Vučićević, Natasa Krejic, Nataša Krklec JerinkićWe present a projection-free algorithm for nonconvex nonlinear equality-constrained finite-sum optimization. The method embeds an additional sampling mechanism into a quadratic penalty framework, yielding an adaptive sample-size policy. A nonmonotone line-search controls step sizes, and the penalty parameter is updated adaptively to enforce feasibility while maintaining progress in the objective. We prove almost-sure convergence under standard assumptions and report experiments on academic and real-data machine-learning problems, showing that the proposed strategy is competitive with state-of-the- art methods.
Heuristic Approaches for the Mothership–Drone Routing Problem with a Fixed Mothership RouteAstrid Wibowo, Boglárka G.-Tóth, József BékésiThis study considers a mothership–drone routing problem in which multiple drones are deployed from a moving mothership to visit a set of targets. In this work, the mothership follows a fixed route, and drones can be launched from and retrieved at any points along this route, when the mothership is there. Each drone performs a sequence of visits under operational constraints such as limited flight range, synchronization with the mothership, and timing restrictions. The problem has been formulated as a mixed-integer nonlinear programming (MINLP) model, which can produce high-quality solutions but becomes computationally expensive as the number of targets increases. To address this limitation, we propose heuristic approaches to construct feasible routes efficiently while coordinating drone operations with the mothership trajectory. The proposed heuristics are designed to find good solutions in a shorter time. Initial results show that it can reduce computation time while still producing solutions close to those obtained by the optimization model. Therefore, the method is suitable for larger problem instances where exact approaches are difficult to apply.
Parameter Estimation in Population Balance Models with Irregular Feasible RegionsDiana Wiederschitz, Edith Kovács, Botond SzilagyiParameter estimation in population balance models (PBMs) can be formulated as a constrained stochastic optimization problem with a highly irregular feasible set. [1] Large regions of the hyper-rectangular parameter space yield numerically unstable or physically infeasible solutions, causing standard optimizers to become inefficient or wasteful in practice. Given this irregularity, we address the problem by learning and exploiting the geometry of the feasible region. First, discrete sampling is used to classify parameter vectors by admissibility, approximating the feasible manifold. Then, a tailored coordinate transformation is applied on selected, strongly coupled parameter subsets, yielding a better-conditioned optimization problem. This method effectively replaces complex, nonlinear constraints with a well-defined, bounded search space, enabling the efficient use of Bayesian optimization in the transformed space, a surrogate-based global method that balances exploration and exploitation. Results indicate that this transformation of the parameter space significantly improves the stability of the optimization process, suggesting that the structure of the feasible set beyond the choice of optimizer is a key determinant of performance in stochastic parameter estimation problems. Reference: [1] B. Szilagyi, A. Eren, J. L. Quon, C. D. Papageorgiou, Z. K. Nagy, Crystal Growth & Design 2020, 20, 3979–3996.
On Bregman–Moreau Envelope Reformulations of DC ProgramsMoslem ZamaniIn this paper, we investigate a class of nonsmooth and nonconvex difference-of-convex (DC) programming. Our approach is based on the use of Bregman–Moreau envelopes, which provide a smooth surrogate framework for handling nonsmooth structures. We introduce and study both left and right Bregman–Moreau envelope formulations of DC functions, and we rigorously establish that these envelope-based problems preserve the optimal value of the original DC formulation. Building on this foundation, we develop a comprehensive theoretical analysis of the relationship between the original DC problem and its envelope counterparts. In particular, we show that stationary points of the envelope formulations correspond to critical points of the original DC problem. In addition, local minimizers are preserved under this transformation, provided that certain conditions are satisfied. These results provide a solid justification for solving the envelope problems as proxies for the original nonsmooth and nonconvex program. On the algorithmic side, we propose gradient-based methods tailored to the structure of the Bregman–Moreau envelopes. These methods exploit the smoothness properties induced by the envelope while retaining the essential features of the underlying DC problem. Finally, we support our theoretical findings with numerical experiments, which demonstrate the effectiveness of the proposed approaches in solving nonsmooth nonconvex optimization problems.
Bounds and exact values of some domination parameters on cylindrical graphsJanez Žerovnik Domination is among the most popular topics in graph theory, both due to its combinatiorial appel and a number of practical applications. Cylindrical graphs and torus grid graphs are naturally constructed from subgraphs of the infinite grid by certain identifications of boundary vertices. Considering various domination type problems, it is usually possible to find an optimal solution on the infinite grid. To the contrary, exact values of invariants for the cylindrical and torus grid graphs are typically only known for special subfamilies, and are in general hard to compute. I will discuss some recent and new results including exact values and lower/upper bounds for invariants that are varieties of the graph domination.
Copositive approach to adjustable robust optimization with inexact decision rulesJohannes Zischg, Markus GablCopositive optimization deals with convex reformulations of nonconvex quadratic optimization problems. Adjustable robust optimization (ARO) deals with two-stage optimization problems under uncertainty, where we look for a first-stage decision such that the second-stage response to the realization optimizes the worst-case performance overall. Xu and Burer exploited a quadratic reformulation of ARO problems with uncertain right-hand sides and provided an exact copositive reformulation, while de Reuter et al. proposed an extension of ARO with inexact decision rule, introducing second-stage uncertainty. In this work, we seek to extend the Xu/Burer reformulation to the latter setting, adapting a recently proposed algorithm by Anstreicher and Gabl, which contains a copositivity test as a core component. Potential benefits include the ability to handle a larger family of second-stage uncertainty sets (for example, mixed integer uncertainty sets), since all the difficulty can be deferred to the copositivity test.
|
