Search

We analyze applications of biform games to linear production (LP) and sequencing processes. Biform games apply to problems in which strategic decisions are followed by some cooperative game, where the specific environment of the cooperative game is in turn determined by these strategic decisions. In biform LP-processes, we allow firms to compete for resources, rather than assuming the resource bundles are simply given. With strategy dependent resource bundles that can be obtained from two locations, we show that the induced strategic game has a (pure) Nash equilibrium, using the Owen set or any game-theoretic solution concept that satisfies anonymity to solve the cooperative LP-game. In biform sequencing processes, we no longer assume an initial processing order is given. Instead, this initial order is strategically determined. Solving the second-stage cooperative sequencing game using a gain splitting rule, we fully determine the set of Nash equilibria of the induced strategic game.

We introduce the half-cycle formulation (HCF), a new integer programming (IP) model for the kidney exchange problem, which has life-saving applications. In HCF, a cycle (i.e., set of kidney swaps) is represented by two compatible halves. After giving several algorithmic enhancements for HCF, we show through extensive computational experiments with an IP solver that our new model outperforms existing formulations when the cycle size limit is set to 4, 5, or 6, depending on the density of the compatibility graph.

We study the inter-temporally optimal innovation strategies of incumbent manufacturing firms that compete in an established market and can extend their product line through product innovation. Firms invest in production capacity and R&D knowledge stock, where the R&D knowledge stock and the current R&D investment determine the hazard rate of innovation. Our findings show that the firms’ optimal R&D strategies are driven by a subtle interplay between the relative positions of their R&D knowledge stocks and their current relative positions on the established market. First, we find that under symmetric investment costs the knowledge leader should spend more on R&D than the knowledge laggard only if it has a substantially smaller market share on the established market. If the knowledge leader’s market share is sufficiently large, its optimal investment in R&D is so small that its innovation rate is lower than the knowledge laggard’s. Second, optimal investment in R&D knowledge is negatively affected by the opponent’s production capacity on the established market if the competitor has not innovated yet. However, we find that this effect is reversed after the competitor has successfully introduced the new product on the submarket. Third, the manufacturing firm with higher costs of adjusting production capacity for the established product has a higher incentive to engage in product innovation and might even achieve a higher total discounted profit than its more efficient competitor.

We consider the two bar charts packing problem (2-BCPP), a recent combinatorial optimization problem whose aim is to pack a set of one-dimensional items into the minimum number of bins. As opposed to the well-known bin packing problem, pairs of items are grouped to form bar charts, and a solution is only feasible if the first and second items of every bar chart are packed in consecutive bins. After providing a complete picture of the connections between the 2-BCPP and other relevant packing problems, we show how we can use these connections to derive valid lower and upper bounds for the problem. We then introduce two new integer linear programming (ILP) models to solve the 2-BCPP based on a nontrivial extension of the arcflow formulation. Even though both models involve an exponential number of constraints, we show that they can be solved within a constraint generation framework. We then empirically evaluate the performance of our bounds and exact approaches against an ILP model from the literature and demonstrate the effectiveness of our techniques on both benchmarks inspired by the literature and new classes of instances that are specifically designed to be hard to solve. The outcomes of our experiments are important for the packing community because they indicate that arcflow formulations can be used to solve targeted packing problems with precedence constraints and also that some of these formulations can be solved with constraint generation. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms–Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.1256 .

Due to their relation to the linear complementarity problem, absolute value equations have been intensively studied recently. In this paper, we present error bound conditions for absolute value equations. Along with the error bounds, we introduce a condition number. We consider general scaled matrix p-norms, as well as particular p-norms. We discuss basic properties of the condition number, including its computational complexity. We present various bounds on the condition number, and we give exact formulae for special classes of matrices. Moreover, we consider matrices that appear based on the transformation from the linear complementarity problem. Finally, we apply the error bound to convergence analysis of two methods for solving absolute value equations.

The price of anarchy is the most well-known measure for quantifying the inefficiency of equilibrium flows in traffic networks and routing games. In this work, we give unifying price of anarchy bounds for atomic and non-atomic parallel link routing games with polynomial cost functions under various cost objectives including the arithmetic mean, geometric mean and worst-case cost objective. We do this through the study of the generalized p-mean as cost objective, and obtain upper bounds on the price of anarchy in terms of this parameter p. Our bounds unify existing results from the literature, and, in particular, give alternative proofs for price of anarchy results in parallel link routing games with polynomial cost functions under the geometric mean objective obtained by Vinci et al. (ACM Trans Econ Comput 10(2):41, 2022). We recover those simply as a limiting case. To the best of our knowledge, these are the first price of anarchy bounds that capture multiple cost objectives simultaneously in a closed-form expression.

This paper studies the existence and uniqueness of equilibrium prices in a model of the banking sector in which banks trade contingent convertible bonds with stock price triggers among each other. This type of financial product was proposed as an instrument for stabilizing the global banking system after the financial crisis. Yet it was recognized early on that these products may create circularity problems in the definition of stock prices—even in the absence of trade. We find that, if conversion thresholds are such that bond holders are indifferent about marginal conversions, there exists a unique equilibrium irrespective of the network structure. When thresholds are lower, the existence of equilibrium breaks down, whereas higher thresholds may lead to multiplicity of equilibria. Moreover, there are complex network effects. One bank’s conversion may trigger further conversions—or prevent them, depending on the constellations of asset values and conversion triggers.

Sparse PCA methods are used to overcome the difficulty of interpreting the solution obtained from PCA. However, constraining PCA to obtain sparse solutions is an intractable problem, especially in a high-dimensional setting. Penalized methods are used to obtain sparse solutions due to their computational tractability. Nevertheless, recent developments permit efficiently obtaining good solutions of cardinality-constrained PCA problems allowing comparison between these approaches. Here, we conduct a comparison between a penalized PCA method with its cardinality-constrained counterpart for the least-squares formulation of PCA imposing sparseness on the component weights. We compare the penalized and cardinality-constrained methods through a simulation study that estimates the sparse structure’s recovery, mean absolute bias, mean variance, and mean squared error. Additionally, we use a high-dimensional data set to illustrate the methods in practice. Results suggest that using cardinality-constrained methods leads to better recovery of the sparse structure.

We consider financial networks where agents are linked to each other by financial contracts. A centralized clearing mechanism collects the initial endowments, the liabilities and the division rules of the agents and determinesthe payments to be made. A division rule specifies how the assets of the agentsshould be rationed. Since payments made depend on payments received, weare looking for solutions to a system of equations. The set of solutions isknown to have a lattice structure, leading to the existence of a least and a greatest clearing payment matrix. Previous research has shown how decentralizedclearing selects the least clearing payment matrix. We present a centralizedapproach towards clearing in order to select the greatest clearing paymentmatrix. To do so, we formulate the determination of the greatest clearingpayment matrix as a programming problem. When agents use proportional division rules, this programming problem corresponds to a linear programmingproblem. We show that for other common division rules, it can be written asan integer linear programming problem.

This paper studies the nucleolus of graph-restricted games as an alternative for the Shapley value to evaluate communication situations. We focus on the inheritance of properties of cooperative games related to the nucleolus: strong compromise admissibility and compromise stability. These two properties allow for a direct, closed formula for the nucleolus. We characterize the families of graphs for which the graph-restricted games inherit these properties from the underlying games. Moreover, for each of these two properties, we characterize the family of graphs for which the nucleolus is invariant

We investigate questions related to the set $\mathcal{SEP}_d$ consisting of the linear maps $\rho$ acting on $\mathbb{C}^d\otimes \mathbb{C}^d$ that can be written as a convex combination of rank one matrices of the form $xx^*\otimes yy^*$. Such maps are known in quantum information theory as the separable bipartite states, while nonseparable states are called entangled. In particular we introduce bounds for the separable rank $\mathrm{rank_{sep}}(\rho)$, defined as the smallest number of rank one states $xx^*\otimes yy^*$ entering the decomposition of a separable state $\rho$. Our approach relies on the moment method and yields a hierarchy of semidefinite-based lower bounds, that converges to a parameter $\tau_{\mathrm{sep}}(\rho)$, a natural convexification of the combinatorial parameter $\mathrm{rank_{sep}}(\rho)$. A distinguishing feature is exploiting the positivity constraint $\rho-xx^*\otimes yy^* \succeq 0$ to impose positivity of a polynomial matrix localizing map, the dual notion of the notion of sum-of-squares polynomial matrices. Our approach extends naturally to the multipartite setting and to the real separable rank, and it permits strengthening some known bounds for the completely positive rank. In addition, we indicate how the moment approach also applies to define hierarchies of semidefinite relaxations for the set $\mathcal{SEP}_d$ and permits to give new proofs, using only tools from moment theory, for convergence results on the DPS hierarchy from (A.C. Doherty, P.A. Parrilo and F.M. Spedalieri. Distinguishing separable and entangled states. Phys. Rev. Lett. 88(18):187904, 2002).

We study bargaining models in discrete time with a finite number of players, stochastic selection of the proposing player, endogenously determined sets and orders of responders, and a finite set of feasible alternatives. The standard optimality conditions and system of recursive equations may not be sufficient for the existence of a subgame perfect equilibrium in stationary strategies (SSPE) in case of costless delay. We present a characterization of SSPE that is valid for both costly and costless delay. We address the relationship between an SSPE under costless delay and the limit of SSPEs under vanishing costly delay. An SSPE always exists when delay is costly, but not necessarily so under costless delay, even when mixed strategies are allowed for. This is surprising as a quasi SSPE, a solution to the optimality conditions and the system of recursive equations, always exists. The problem is caused by the potential singularity of the system of recursive equations, which is intimately related to the possibility of perpetual disagreement in the bargaining process.

Sandwich algorithms are commonly used to approximate the Pareto front of a multiobjective (MO) convex problem by enclosing it between an inner and outer approximation. By iteratively improving the approximations, the distance between them is minimized which gives an estimate of how well the Pareto front is approximated. A wellexplainable type of sandwich algorithm is based on weighted sum scalarization (WSS), where the next set of weights is determined by the most promising inner normal of the inner approximation. As these normals can contain negative values, not every optimization will result in finding an efficient point. In order to reduce the number of searches towards the dominated part, we propose an elegant modification of the criterion space which is an advancement on the formulation of Solanki et al. In addition to being well-explainable and easy to integrate within an existing optimization procedure, this modification is theoretically able to obtain all nondominated points of an MO linear programming problem in a finite number of expansions of the inner approximation. Furthermore, we propose two heuristic approaches to determine the distance between the inner and outer approximation that can be used as an alternative for the distance calculation of Solanki et al. These heuristics incorporate the ideas of Solanki et al. And Craft et al. to obtain straightforward and faster methods.

We consider a model of influence over a network with finite-horizon opinion dynamics. The network consists of agents that update their opinions via a trust structure as in the DeGroot dynamics (De Groot (1974)). The model considers two potential external influencers that have fixed and opposite opinions. They aim to maximally impact the aggregate state of opinions at the end of the finite horizon by targeting one agent in one specific time period. In the case of only one influencer, we characterize optimal targets on the basis of two features: shift and amplification. Also, conditions are provided under which a specific target is optimal: the maximum-amplification target. In the case of two influencers, we focus on the existence and characterization of pure strategy equilibria in the corresponding two-person strategic zero-sum game. Roughly speaking, if the initial opinions are not too much in favour of either influencer, the influencers’ equilibrium behaviour is also driven by the amplification of targets.

This paper studies a new type of interactive Operations Research problem, called a graph machine scheduling problem (GMS-problem). A GMS-problem combines aspects from minimum cost spanning tree problems and sequencing problems. Given a graph, we aim to first establish a connection order on the players such that the total cost of connecting them to a source is minimal and second to find a cost allocation of such an optimal order among the players involved. We restrict attention to GMS-problems on trees and propose a recursive method to solve these tree GMS-problems integrated with an allocation approach. This latter mechanism consistently and recursively uses myopic reference orders to determine potential cost savings, which will then be appropriately allocated. Interestingly, the transition process from a myopic reference order to an optimal one will be smooth using the switching of blocks of agents based on the basic notion of merge segments.

Let $$S \subseteq \mathbb {R}^n$$ S ⊆ R n be a compact semialgebraic set and let f be a polynomial nonnegative on S. Schmüdgen’s Positivstellensatz then states that for any $$\eta > 0$$ η > 0 , the nonnegativity of $$f + \eta$$ f + η on S can be certified by expressing $$f + \eta$$ f + η as a conic combination of products of the polynomials that occur in the inequalities defining S, where the coefficients are (globally nonnegative) sum-of-squares polynomials. It does not, however, provide explicit bounds on the degree of the polynomials required for such an expression. We show that in the special case where $$S = [-1, 1]^n$$ S = [ - 1 , 1 ] n is the hypercube, a Schmüdgen-type certificate of nonnegativity exists involving only polynomials of degree $$O(1 / \sqrt{\eta })$$ O ( 1 / η ) . This improves quadratically upon the previously best known estimate in $$O(1/\eta )$$ O ( 1 / η ) . Our proof relies on an application of the polynomial kernel method, making use in particular of the Jackson kernel on the interval $$[-1, 1]$$ [ - 1 , 1 ] .

Logit dynamics is a form of randomized game dynamics where players have a bias towards strategic deviations that give a higher improvement in cost. It is used extensively in practice. In congestion (or potential) games, the dynamics converges to the so-called Gibbs distribution over the set of all strategy profiles, when interpreted as a Markov chain. In general, logit dynamics might converge slowly to the Gibbs distribution, but beyond that, not much is known about their algorithmic aspects, nor that of the Gibbs distribution. In this work, we are interested in the following two questions for congestion games: i) Is there an efficient algorithm for sampling from the Gibbs distribution? ii) If yes, do there also exist natural randomized dynamics that converges quickly to the Gibbs distribution? We first study these questions in extension parallel congestion games, a well-studied special case of symmetric network congestion games. As our main result, we show that there is a simple variation on the logit dynamics (in which we in addition are allowed to randomly interchange the strategies of two players) that converges quickly to the Gibbs distribution in such games. This answers both questions above affirmatively. We also address the first question for the class of so-called capacitated $k$-uniform congestion games. To prove our results, we rely on the recent breakthrough work of Anari, Liu, Oveis-Gharan and Vinzant (2019) concerning the approximate sampling of the base of a matroid according to strongly log-concave probability distribution., Accepted at the 22nd ACM Conference on Economics and Computation (EC 2021)

The subgame perfect equilibrium in stationary strategies (SSPE) is the most important solution concept in applications of stochastic games, making it imperative to develop efficient methods to compute an SSPE. For this purpose, this paper develops an interior-point differentiable path-following method (IPM), which establishes a connection between an artificial logarithmic barrier game and the stochastic game of interest by adding a homotopy variable. IPM brings several advantages over the existing methods for stochastic games. On the one hand, IPM provides a bridge between differentiable path-following methods and interior-point methods and remedies several issues of an existing homotopy method called the stochastic linear tracing procedure (SLTP). First, the starting stationary strategy profile can be arbitrarily chosen. Second, IPM does not need switching between different systems of equations. Third, the use of a perturbation term makes IPM applicable to all stochastic games rather than generic games only. Moreover, a well-chosen transformation of variables reduces the number of equations and variables by roughly one half. Numerical results show that the proposed method is more than three times as efficient as SLTP. On the other hand, the stochastic game can be reformulated as a mixed complementarity problem and solved by the PATH solver. We employ the proposed IPM and the PATH solver to compute SSPEs. Numerical results evince that for some stochastic games the PATH solver may fail to find an SSPE, whereas IPM is successful in doing so for all stochastic games, which confirms the reliability and stability of the proposed method. Summary of Contribution: This paper incorporates the interior-point methods into a differentiable path-following method for computing stationary equilibria for stochastic games. This novel method brings excellent computational advantages and remedies several issues with the existing methods for stochastic games. We prove the global convergence of the proposed method and employ this method to solve numerous randomly generated stochastic games with different scales. Numerical results further confirm the high efficiency, stability, and universality of this method for stochastic games.

This paper is an in-depth analysis of the generalized $\vartheta$-number of a graph. The generalized $\vartheta$-number, $\vartheta_k(G)$, serves as a bound for both the $k$-multichromatic number of a graph and the maximum $k$-colorable subgraph problem. We present various properties of $\vartheta_k(G)$, such as that the sequence $(\vartheta_k(G))_k$ is increasing and bounded from above by the order of the graph $G$. We study $\vartheta_k(G)$ when $G$ is the strong, disjunction or Cartesian product of two graphs. We provide closed form expressions for the generalized $\vartheta$-number on several classes of graphs including the Kneser graphs, cycle graphs, strongly regular graphs and orthogonality graphs. Our paper provides bounds on the product and sum of the $k$-multichromatic number of a graph and its complement graph, as well as lower bounds for the $k$-multichromatic number on several graph classes including the Hamming and Johnson graphs.

This paper provides a multi-actor perspective on the realization of new infrastructures, motivated by the necessity for infrastructures to support the ongoing climate and energy transition in general, and CO2 transport infrastructures for carbon capture, utilization and storage (CCUS) in particular. We develop a general model to represent infrastructures that allows for a unique decomposition into `elementary infrastructure components' based on heterogeneous user requirements. Notably, it incorporates a cost function with a very generic and adaptable structure, for which we can still explicitly determine the costs of each individual component. As a direct consequence an intuitive cost allocation rule is obtained: equal component cost sharing. This allocation rule is in line with existing game-theoretic concepts and satisfies the desirable properties of advantageous scaling and coalitional rationality. Advantageous scaling guarantees that the costs allocated to each existing user do not increase if the number of users grows larger and coalitional rationality ensures that there is no subgroup of infrastructure users that would have a financial reason to object to the cost allocation. Additionally, we examine the application of our model to a prospective CO2 transport infrastructure for CCUS in the port of Rotterdam and the adjoining industry area.

The graph partition problem (GPP) aims at clustering the vertex set of a graph into a fixed number of disjoint subsets of given sizes such that the sum of weights of edges joining different sets is minimized. This paper investigates the quality of doubly nonnegative (DNN) relaxations, i.e., relaxations having matrix variables that are both positive semidefinite and nonnegative, strengthened by additional polyhedral cuts for two variations of the GPP: the k-equipartition and the graph bisection problem. After reducing the size of the relaxations by facial reduction, we solve them by a cutting-plane algorithm that combines an augmented Lagrangian method with Dykstra's projection algorithm. Since many components of our algorithm are general, the algorithm is suitable for solving various DNN relaxations with a large number of cutting planes. We are the first to show the power of DNN relaxations with additional cutting planes for the GPP on large benchmark instances up to 1,024 vertices. Computational results show impressive improvements in strengthened DNN bounds.

This paper studies a firm’s investment decision in production capacity where product demand follows a product life cycle (PLC), implying that demand first grows and then declines. The starting point of the decline phase is uncertain. The investment decision involves deciding about the timing and the size of the investment. We make a distinction between the firm being a product life cycle leader and a product life cycle follower. A PLC-leader will always first experience demand growth before the decline kicks in. In case of a PLC-follower, the firm enters an existing product life cycle, implying that the decline can already start before this firm even has invested. It turns out that it makes a major difference whether the firm is a PLC-leader or PLC-follower. To benefit from a period of demand growth, the PLC-follower has an incentive to invest early, thus when the current demand level is still low. This forces the firm to limit the investment size. The PLC-leader, on the contrary, always chooses the investment size corresponding to demand growth throughout, where the probability of demand decline simply delays the moment of investment.

We consider financial networks where agents are linked to each other via mutualliabilities. In case of bankruptcy, there are potentially many bankruptcy rules, ways to distribute the assets of a bankrupt agent over the other agents. One common approach is to first apply pairwise netting of agents that have mutual liabilities and next use the proportional rule to determine the payments on the basis of the net liabilities. We refer to this as the pairwise netting proportional rule. The pairwise netting proportional rule satisfies the basic requirements of claims boundedness, limited liability, priority of creditors, and continuity. It also satisfies the desirable properties of net impartiality, an agent that has two creditors with the same net claims pays the same amount to both creditors on top of pairwise netting, and invariance to mitosis, an agent that splits into a number of identical agents is not a_ecting the payments of the other agents. We demonstrate that if net impartiality and invariance to mitosis, together with the basic requirements, are regarded as imperative properties, then payments should be determined by the pairwise netting proportional rule.

Kidney exchange programmes (KEPs) across the world help match donors and recipients to identify kidney transplantations. Almost all KEPs use a hierarchical set of objectives to determine an optimal set of transplants to perform, and integer linear programming is often used to find such optimal matchings. In this work, we identify the barriers in existing mathematical models and we propose innovative techniques to remove these barriers, vastly reducing solution times and allowing us to significantly increase the potential size of KEPs. Our techniques include two methods to avoid unnecessary variables, as well as a diving algorithm that reduces the need to solve multiple complex integer linear programming models while still guaranteeing the optimality of a final solution. We also show that it is possible to transition between two distinct existing formulations (namely the cycle formulation and the position-indexed chain-edge formulation) between the optimisation of two successive objective functions. We use this technique to devise a new algorithm which, among other features, intelligently exploits the different advantages of the prior two models. We demonstrate the performance of our new algorithms with extensive computational experiments modelling the UK KEP, where we show that our improvements reduce running times by three orders of magnitude compared to the cycle formulation. We also provide substantial empirical evidence that the new methodology offers equally spectacular improvements when applied to modelling the objectives used by Spain and the Netherlands, suggesting that our approach is not just viable, but a significant performance improvement, for many different KEPs across the globe.

We study bankruptcy problems in financial networks in the presence of general bankruptcy laws. The set of clearing payment matrices is shown to be a lattice, which guarantees the existence of a greatest and a least clearing payment. Multiplicity of clearing payment matrices is both a theoretical and a practical concern. We present a new condition for uniqueness that generalizes all the existing conditions proposed in the literature. Our condition depends on the decomposition of the financial network into strongly connected components. A strongly connected component which contains more than one agent is called a cycle and the involved agents are called cyclical agents. If there is a cycle without successors, then one of the agents in such a cycle should have a positive endowment. The division rule used by a cyclical agent with a positive endowment should be positive monotonic and the rule used by a cyclical agent with a zero endowment should be strictly monotonic. Since division rules involving priorities are not positive monotonic, uniqueness of the clearing payment matrix is a much bigger concern for such division rules than for proportional ones. We also show how uniqueness of clearing payment matrices is related to continuity of bankruptcy rules.

In this paper, we investigate the relationships between proper efficiency and the solutions of a general scalarization problem in multi-objective optimization. We provide some conditions under which the solutions of the dealt with scalar program are properly efficient and vice versa. We also show that, under some conditions, if the considered general scalar problem is unbounded, then the original multi-objective problem does not have any properly efficient solution. In another part of the work, we investigate a general transformation of the objective functions which preserves proper efficiency. We show that several important results existing in the literature are direct consequences of the results of the present paper.

We consider the problem of allocating procurement quantities for a required input to multiple suppliers in advance of a selling season with uncertain demand. Planning complexity is compounded by uncertainty in whether each supplier will deliver on time, in addition to the existence of an option for reserving capacity with a perfectly reliable supplier and the presence of a spot market for the input with an uncertain price. We apply analytical methods including two-stage stochastic programming with recourse, nonlinear optimization, and exact and efficient model-based heuristic solution methods. We show that for a selected supplier, the newsvendor’s conditional service level, given that the supplier delivers on time, equals a critical ratio value determined by the supplier’s cost and reliability parameters. Post-optimality analysis reveals interesting insights on the way reliability and cost parameters interact to determine whether a supplier receives a positive order allocation, as well as the impact of payment schemes on supplier selection decisions. The analysis clarifies an insightful relationship between the conditional service level and a critical ratio value for each selected supplier. The results also sharpen insights on the way relative supplier reliability and cost parameter values interact to determine an optimal supply portfolio. Furthermore, the ability to interpret a perfectly reliable supplier with a capacity reservation cost as an equivalent unreliable supplier reveals additional insights on the relative value of capacity reservation and facilitates direct comparison among seemingly disparate supply options.

The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. To simplify these relaxations, we exploit the symmetry arising from permuting the colors, as well as the symmetry of the given graphs when applicable. We also show how to exploit invariance under permutations of the subsets for other partition problems and how to use the MkCS problem to derive bounds on the chromatic number of a graph. Our numerical results verify that the proposed relaxations provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Summary of Contribution: The maximum k-colorable subgraph (MkCS) problem is to find an induced k-colorable subgraph with maximum cardinality in a given graph. The MkCS problem has a number of applications, such as channel assignment in spectrum sharing networks (e.g., Wi-Fi or cellular), very-large-scale integration design, human genetic research, and so on. The MkCS problem is also related to several other optimization problems, including the graph partition problem and the max-k-cut problem. The two mentioned problems have applications in parallel computing, network partitioning, floor planning, and so on. This paper is an in-depth analysis of the MkCS problem that considers various semidefinite programming relaxations, including their theoretical and numerical comparisons. Further, our analysis relates the MkCS results with the stable set and the chromatic number problems. We provide extended numerical results that verify that the proposed bounding approaches provide strong bounds for the MkCS problem and that those outperform existing bounds for most of the test instances. Moreover, our lower bounds on the chromatic number of a graph are competitive with existing bounds in the literature.

The switch Markov chain has been extensively studied as the most natural Markovchain Monte Carlo approach for sampling graphs with prescribed degree sequences. In this work westudy the problem of uniformly sampling graphs for which, in addition to the degree sequence, jointdegree constraints are given. These constraints specify how many edges there should be between twogiven degree classes (i.e., subsets of nodes that all have the same degree). Although the problem wasformalized over a decade ago, and despite its practical significance in generating synthetic networktopologies, small progress has been made on the random sampling of such graphs. In the case of onedegree class, the problem reduces to the sampling of regular graphs (i.e., graphs in which all nodeshave the same degree), but beyond this very little is known. We fully resolve the case of two degreeclasses, by showing that the switch Markov chain is always rapidly mixing. We do this by combininga recent embedding argument developed by the authors in combination with ideas of Bhatnagar et al.[Algorithmica, 50 (2008), pp. 418--445] introduced in the context of sampling bichromatic matchings.

We consider a large-scale service system where incoming tasks have to be instantaneously dispatched to one out of many parallel server pools. The user-perceived performance degrades with the number of concurrent tasks and the dispatcher aims at maximizing the overall quality-of-service by balancing the load through a simple threshold policy. We demonstrate that such a policy is optimal on the fluid and diffusion scales, while only involving a small communication overhead, which is crucial for large-scale deployments. In order to set the threshold optimally, it is important, however, to learn the load of the system, which may be unknown. For that purpose, we design a control rule for tuning the threshold in an online manner. We derive conditions which guarantee that this adaptive threshold settles at the optimal value, along with estimates for the time until this happens. In addition, we provide numerical experiments which support the theoretical results and further indicate that our policy copes effectively with time-varying demand patterns., Comment: 51 pages, 6 figures

We give lower bounds on the size and total size of clique partitions of a graph in terms of its spectral radius and minimum degree, and derive a spectral upper bound for the maximum number of edge-disjoint t-cliques. The extremal graphs attaining the bounds are exactly the block graphs of Steiner 2-designs and the regular graphs with K t -decompositions, respectively.

We present the closed-form solution to the problem of hedging price and quantity risks for energy retailers (ER), using financial instruments based on electricity price and weather indexes. Our model considers an ER who is intermediary in a regulated electricity market. ERs buy a fixed quantity of electricity at a variable cost and must serve a variable demand at a fixed cost. Thus ERs are subject to both price and quantity risks. To hedge such risks, an ER could construct a portfolio of financial instruments based on price and weather indexes. We construct the closed form solution for the optimal portfolio for the mean-VaR model in the discrete setting. Our model does not make any distributional assumption.

In this work, we study the problem of scheduling jobs and maintenance activities on a set of unrelated parallel machines, by considering that the processing time of a job increases according to a deterioration factor that depends both on the machine and on the set of jobs the machine has processed since its last maintenance. The objective we consider is to minimize the makespan. We introduce four mixed integer linear programming models, two of which using big-M constraints and the other two using an exponential number of variables. We also propose an iterated local search metaheuristic to tackle large size instances and we provide empirical evidence of the performance of the proposed approaches by means of extensive computational experiments.

We study the computation and efficiency of pure Nash equilibria in combinatorial congestion games, where the strategies of each player i are given by the binary vectors of a polytope $$P_i$$ P i . Our main goal is to understand which structural properties of such polytopal congestion games enable us to derive an efficient equilibrium selection procedure to compute pure Nash equilibria with attractive social cost approximation guarantees. To this aim, we identify two general properties of the underlying aggregation polytope$$P_N = \sum _i P_i$$ P N = ∑ i P i which are sufficient for our results to go through, namely the integer decomposition property (IDP) and the box-totally dual integrality property (box-TDI). Our main results for polytopal congestion games satisfying IDP and box-TDI are as follows: (i) we show that pure Nash equilibria can be computed in polynomial time. In fact, we obtain this result through a general framework for separable convex function minimization, which might be of independent interest. (ii) We bound the inefficiency of these equilibria and show that this provides a tight bound on the price of stability. (iii) We also prove that these results extend to strong equilibria for the “bottleneck variant” of polytopal congestion games. Examples of polytopal congestion games satisfying IDP and box-TDI include common source network congestion games, symmetric totally unimodular congestion games, non-symmetric matroid congestion games and symmetric matroid intersection congestion games (in particular, r-arborescences and strongly base-orderable matroids).

We study the quadratic cycle cover problem (QCCP), which aims to find a node-disjoint cycle cover in a directed graph with minimum interaction cost between successive arcs. We derive several semidefinite programming (SDP) relaxations and use facial reduction to make these strictly feasible. We investigate a nontrivial relationship between the transformation matrix used in the reduction and the structure of the graph, which is exploited in an efficient algorithm that constructs this matrix for any instance of the problem. To solve our relaxations, we propose an algorithm that incorporates an augmented Lagrangian method into a cutting-plane framework by utilizing Dykstra’s projection algorithm. Our algorithm is suitable for solving SDP relaxations with a large number of cutting-planes. Computational results show that our SDP bounds and efficient cutting-plane algorithm outperform other QCCP bounding approaches from the literature. Finally, we provide several SDP-based upper bounding techniques, among which is a sequential Q-learning method that exploits a solution of our SDP relaxation within a reinforcement learning environment. Summary of Contribution: The quadratic cycle cover problem (QCCP) is the problem of finding a set of node-disjoint cycles covering all the nodes in a graph such that the total interaction cost between successive arcs is minimized. The QCCP has applications in many fields, among which are robotics, transportation, energy distribution networks, and automatic inspection. Besides this, the problem has a high theoretical relevance because of its close connection to the quadratic traveling salesman problem (QTSP). The QTSP has several applications, for example, in bioinformatics, and is considered to be among the most difficult combinatorial optimization problems nowadays. After removing the subtour elimination constraints, the QTSP boils down to the QCCP. Hence, an in-depth study of the QCCP also contributes to the construction of strong bounds for the QTSP. In this paper, we study the application of semidefinite programming (SDP) to obtain strong bounds for the QCCP. Our strongest SDP relaxation is very hard to solve by any SDP solver because of the large number of involved cutting-planes. Because of that, we propose a new approach in which an augmented Lagrangian method is incorporated into a cutting-plane framework by utilizing Dykstra’s projection algorithm. We emphasize an efficient implementation of the method and perform an extensive computational study. This study shows that our method is able to handle a large number of cuts and that the resulting bounds are currently the best QCCP bounds in the literature. We also introduce several upper bounding techniques, among which is a distributed reinforcement learning algorithm that exploits our SDP relaxations.

This paper considers sequencing situations with non-linear cost functions under optimal order consistency. Specifically, we study sequencing situations with discounting cost functions and logarithmic cost functions of the completion time. In both settings, we show that the neighbor switching gains are non-negative and non-decreasing for every misplaced pair of players. We derive new conditions on the time-dependent neighbor switching gains in a sequencing situation under optimal order consistency to guarantee convexity of the associated sequencing game. Furthermore, we define two types of gain splitting rules for the class of sequencing situations under optimal order consistency. Each one of them is based on a procedure that specifies a path from the initial order to an optimal order, dividing the neighbor switching gains in every step among the two involved players. We prove that these allocations are stable under the same conditions that are required for convexity. These requirements are fulfilled for discounting and logarithmic sequencing situations, as well as in other settings, such as in sequencing situations with exponential cost functions. Ministerio de Ciencia, Innovación y Universidades | Ref. MTM2017-87197-C3-2-P Ministerio de Ciencia, Innovación y Universidades | Ref. MTM2017-87197- C3-3-P Xunta de Galicia | Ref. ED431C- 2016-040 Xunta de Galicia | Ref. ED431C-2017/38 Xunta de Galicia | Ref. ED431C2020-03

IntroductionLinear programming (LP) is often used within diet optimization to find, from a set of available food commodities, the most affordable diet that meets the nutritional requirements of an individual or (sub)population. It is, however, not always possible to create a feasible diet, as certain nutritional requirements are difficult to meet. In that case, goal programming (GP) can be used to minimize deviations from the nutritional requirements in order to obtain a near feasible diet. With GP the cost of the diet is often overlooked or taken into account using the ε-constraint method. This method does not guarantee to find all possible trade-offs between costs and nutritional deficiency without solving many uninformative LPs.MethodsWe present a method to find all trade-offs between any two linear objectives in a dietary LP context that is simple, does not solve uninformative LPs and does not need prior input from the decision maker (DM). This method is a bi-objective algorithm based on the NonInferior Set Estimation (NISE) method that finds all efficient trade-offs between two linear objectives.ResultsIn order to show what type of insights can be gained from this approach, two analyses are presented that investigate the relation between cost and nutritional adequacy. In the first analysis a diet with a restriction on the exact energy intake is considered where all nutrient intakes except energy are allowed to deviate from their prescription. This analysis is especially helpful in case of a restrictive budget or when a nutritionally adequate diet is either unaffordable or unattainable. The second analysis only relaxes the exact energy intake, where the other nutrients are kept within their requirements, to investigate how the energy intake affects the cost of a diet. Here, we describe in what situations the so-called more-for-less paradox takes place, which can be induced by requiring an exact energy intake.ConclusionTo the best of our knowledge, we are the first to address how to obtain all efficient trade-offs of two linear objectives in a dietary LP context and how this can be used for analyses.

Service systems often face task-server assignment-constraints due to skill-based routing or geographical conditions. Redundancy scheduling responds to this limited flexibility by replicating tasks to specific servers in agreement with these assignment constraints. We gain insight from product-form stationary distributions and weak local stability conditions to establish a state space collapse in heavy traffic. In this limiting regime, the parallel-server system with redundancy scheduling operates as a multi-class single-server system, achieving full resource pooling and exhibiting strong insensitivity to the underlying assignment constraints. In particular, the performance of a fully flexible (unconstrained) system can be matched even with rather strict assignment constraints., 53 pages, 4 figures

Consider the problem of minimizing a polynomial $f$ over a compact semialgebraic set ${\mathbf{X} \subseteq \mathbb{R}^n}$. Lasserre introduces hierarchies of semidefinite programs to approximate this hard optimization problem, based on classical sum-of-squares certificates of positivity of polynomials due to Putinar and Schm\"udgen. When $\mathbf{X}$ is the unit ball or the standard simplex, we show that the hierarchies based on the Schm\"udgen-type certificates converge to the global minimum of $f$ at a rate in $O(1/r^2)$, matching recently obtained convergence rates for the hypersphere and hypercube $[-1,1]^n$. For our proof, we establish a connection between Lasserre's hierarchies and the Christoffel-Darboux kernel, and make use of closed form expressions for this kernel derived by Xu., Comment: v2: implemented minor changes based on reviewer comments. 22 pages, 3 figures

An important development in the real options theory is the notion that an investment decision is not only about timing but also about size. This plays for instance a crucial role when the firm has market power, implying that quantity affects the output price. Analyzing the resulting problem requires the inclusion of a demand function in the real options model. The present paper analyzes the general problem, and gives an overview of possible demand functions and its implications for the optimal investment decision. We carry out an extensive comparative statics analysis of the uncertainty parameter, the market trend, and the discount rate, thereby distinguishing between net present value (NPV), option, and quantity effects.

While eigenvalues of graphs are well studied, spectral analysis of complex unit gain graphs is still in its infancy. This thesis considers gain graphs whose gain groups are gradually less and less restricted, with the ultimate goal of classifying gain graphs that are characterized by their spectra. In such cases, the eigenvalues of a gain graph contain sufficient structural information that it might be uniquely (up to certain equivalence relations) constructed when only given its spectrum. First, the first infinite family of directed graphs that is – up to isomorphism – determined by its Hermitian spectrum is obtained. Since the entries of the Hermitian adjacency matrix are complex units, these objects may be thought of as gain graphs with a restricted gain group. It is shown that directed graphs with the desired property are extremely rare. Thereafter, the perspective is generalized to include signs on the edges. By encoding the various edge-vertex incidence relations with sixth roots of unity, the above perspective can again be taken. With an interesting mix of algebraic and combinatorial techniques, all signed directed graphs with degree at most 4 or least multiplicity at most 3 are determined. Subsequently, these characterizations are used to obtain signed directed graphs that are determined by their spectra. Finally, an extensive discussion of complex unit gain graphs in their most general form is offered. After exploring their various notions of symmetry and many interesting ties to complex geometries, gain graphs with exactly two distinct eigenvalues are classified.

The Diet Optimization Problem is a classical Linear Programming problem which finds, from a set of available food commodities, the most affordable diet that meets an individual’s nutritional requirements. It is, however, not always possible to create a feasible diet, as certain nutritional requirements are difficult to be met (e.g. iron for adolescent females). In that case, Goal Programming is used to minimize nutritional deviations in order to obtain a near feasible diet. The cost of the diet is, however, often overlooked or neglected. Therefore, we focus in our paper on finding all tradeoffs between the cost and nutritional adequacy of a diet. To do so, we present a bi-objective approach based on the NISE method that is able to find all efficient tradeoffs between two linear objectives. To the best of our knowledge, this approach bridges the current gap between diet optimization and multicriteria optimization, as we are the first to address how to obtain all efficient trade-offs of two linear objectives in a dietary context. In order to show what type of insights can be gained from this approach, two analyses are presented using data collected in Ebonyi, Nigeria. In the first analysis a diet with a restriction on the exact energy intake is considered where all nutrient intakes except energy are allowed to deviate from their prescription. This analysis is especially helpful when one needs to make decisions in case there is a restrictive budget or when a nutritionally adequate diet is either unaffordable or unattainable. The second analysis only relaxes the exact energy intake, where the other nutrients are kept within their requirements, to investigate how the energy intake affects the cost of a diet. Here, we describe in what situations the so-called more-for-less paradox takes place, which can be induced by the exact energy intake.

In this paper, we study the absolute value equation (AVE) $$Ax-b=|x|$$ . One effective approach to handle AVE is by using concave minimization methods. We propose a new method based on concave minimization methods. We establish its finite convergence under mild conditions. We also study some classes of AVEs which are polynomial time solvable.

The goal of a mathematical optimization problem is to maximize an objective (or minimize a cost) under a given set of rules, called constraints. Optimization has many applications, both in other areas of mathematics and in the real world. Unfortunately, some of the most interesting problems are also very hard to solve numerically. To work around this issue, one often considers relaxations: approximations of the original problem that are much easier to solve. Naturally, it is then important to understand how (in)accurate these relaxations are. This thesis consists of three parts, each covering a different method that uses semidefinite programming to approximate hard optimization problems. In Part 1 and Part 2, we consider two hierarchies of relaxations for polynomial optimization problems based on sums of squares. We show improved guarantees on the quality of Lasserre's measure-based hierarchy in a wide variety of settings (Part 1). We establish error bounds for the moment-SOS hierarchy in certain fundamental special cases. These bounds are much stronger than the ones obtained from existing, general results (Part 2).In Part 3, we generalize the celebrated Lovász theta number to (geometric) hypergraphs. We apply our generalization to formulate relaxations for a type of independent set problem in the hypersphere. These relaxations allow us to improve some results in Euclidean Ramsey theory.

We study the existence of competitive equilibria in the presence of risk-loving preferences and incomplete markets. A crucial role is played by the initial endowments of an asset, the maximal possible supply of that asset by a consumer. We provide a lower bound on the aggregate initial endowments of an asset of the risk averse agents that is succient for competitive equilibria to exist. We apply our results to special cases where wealth is transferred to the future by means of a riskless bond and cases where all risk averters have constant relative risk aversion utility functions. We also provide some evidence that market incompleteness helps in ensuring equilibrium existence.

It is often argued that compared to a carbon tax, a volatile carbon price under an emissions trading system poses a problem in the transition towards a low carbon economy. However, this paper shows that, when sufficiently positively correlated with the electricity price, carbon price uncertainty diminishes overall volatility because of a diversification effect. To get this result, we develop a dynamic real options model to analyze the impact of positively correlated price uncertainty on the timing of an investment decision. In contrast to static models, we show that even when the carbon price is initially the same under both policy instruments, the timing of the investment decision will typically be different. More importantly, we find that multiple correlated price uncertainties under an emissions trading system encourages investment more than less uncertainty under a carbon tax. Hence, to stimulate a low carbon (or discourage a carbon intensive) investment, an emissions trading system (carbon tax) is preferred. The policy reverts for higher levels of uncertainty and low correlations.

In this paper, we study some bounds for nonconvex quadratically constrained quadratic programs. We propose two types of bounds for quadratically constrained quadratic programs, quadratic and cubic bounds. For quadratic bounds, we use affine functions as Lagrange multipliers. We demonstrate that most semi-definite relaxations can be obtained as the dual of a quadratic bound. In addition, we study bounds obtained by changing the ground set. For cubic bounds, in addition to affine multipliers we employ quadratic functions. We provide a comparison between the proposed cubic bound and typical bounds for standard quadratic programs. Moreover, we report comparison results of a quadratic and a cubic bound for some non-convex quadratically constrained quadratic programs.

PCA is a popular tool for exploring and summarizing multivariate data, especially those consisting of many variables. PCA, however, is often not simple to interpret, as the components are a linear combination of the variables. To address this issue, numerous methods have been proposed to sparsify the nonzero coefficients in the components, including rotation-thresholding methods and, more recently, PCA methods subject to sparsity inducing penalties or constraints. Here, we offer guidelines on how to choose among the different sparse PCA methods. Current literature misses clear guidance on the properties and performance of the different sparse PCA methods, often relying on the misconception that the equivalence of the formulations for ordinary PCA also holds for sparse PCA. To guide potential users of sparse PCA methods, we first discuss several popular sparse PCA methods in terms of where the sparseness is imposed on the loadings or on the weights, assumed model, and optimization criterion used to impose sparseness. Second, using an extensive simulation study, we assess each of these methods by means of performance measures such as squared relative error, misidentification rate, and percentage of explained variance for several data generating models and conditions for the population model. Finally, two examples using empirical data are considered. Supplementary Information The online version contains supplementary material available at 10.1007/s11336-021-09773-2.

We study capacity investment decisions among oligopoly firms under conditions of cost heterogeneity and output flexibility within capacity constraints. Output flexibility causes the value of the firm to be convex in the state of demand, which implies that the firm invests in larger capacity when the economic environment is more uncertain. Under cost heterogeneity among oligopoly firms, a lower-cost firm invests in larger capacity, while a less efficient rival chooses lower capacity as capacities are strategic substitutes. Consequently, higher uncertainty leads to more dispersion of equilibrium capacities and greater industry concentration. More competition thus induces a welfare loss when uncertainty and cost heterogeneity are high. (C) 2020 Elsevier B.V. All rights reserved.