Search

We study a newsvendor problem with greenhouse gas (GHG) emissions at the disposal stage regulated by a cap-and-trade policy. We first consider a synchronous version of the problem where the replenishment period and the emission assessment period are the same. For this problem, we propose simple algorithms to derive the optimal quantity and cost for both continuous and discrete demand distributions. We show that ignoring the carbon tax may lead to large overcost, especially when the GHG quota is small. For a normally distributed demand, we also show that the demand standard deviation has a non-linear and non-monotonic effect on the order quantity. We then investigate an asynchronous version of the problem where replenishment decisions occur at a higher frequency than the quota allocation. We formulate this lot sizing problem as a Markov decision process and solve it with a dynamic programming algorithm whose complexity is assessed. Through a numerical experimentation and theoretical results, we demonstrate how and when the flexibility of the optimal dynamic replenishment decisions allows to reduce costs. When approaching the end of the time horizon, the uncertainty reduction allows the decision maker to adopt a riskier policy and order larger quantities. [ABSTRACT FROM AUTHOR]

Genetic programming has achieved great success in project scheduling by generating Priority Rules (PRs) through evolution. However, the frequent disturbance factors in practice not only lead to the appropriate PR changes in different states, but also increase the calculation consumption in evaluation. In this paper, a novel Hyper-heuristic-based Surrogate-Assisted Dual-Tree Genetic Programming (HSDGP) framework is proposed for the Dynamic Resource Constrained Multi-Project Scheduling Problem with new project Insertions and resource Disruptions (DRCMPSP-ID). Uniquely, the proposed method automatically evolves two PRs for scheduling DRCMPSP-ID under normal and disruptive states respectively, and an expansion search mechanism based on neighbourhood is designed to improve PR generation ability by generating a large number of offspring and implement the search of dual-tree encoding. Furthermore, in order to estimate the fitness of new individuals, an activity-sequence based surrogate is proposed to deal with the input of activity sequence during schedule generation and reduce the evaluation calculation consumption. Based on the instances constructed by the existing benchmark, the experimental result shows the superiority of HSDGP and the impact of key parameters on its performance. [ABSTRACT FROM AUTHOR]

This paper explores the multitasking scheduling problem via alternate periods, which is common in manufacturing and service industries. The shift pattern comprises regular shifts interspersed with breaks, allowing job switching. We focus on two alternate periods consisting of odd periods and even periods. Each job is not only processed completely within odd periods or completely within even periods, but job switching is also allowed between alternate periods with additional overhead. For this problem, we propose two job switching models. The first model is alternate periods multitasking scheduling with switching time, where a fixed switching time is incurred whenever a job is switched from one period to its adjacent period. The second model is alternate periods multitasking scheduling with diverse speeds, where an urgent switching cost is produced if a job is processed through the alternate periods with different speeds. For the two models, we study three scheduling objectives including minimising the total completion time, minimising the maximum lateness, and minimising the number of tardy jobs, respectively. For each of the problems under consideration, we investigate the structural properties of the optimal schedule and develop the corresponding pseudo-polynomial time dynamic programming algorithm. Furthermore, we give examples to effectively illustrate the proposed algorithms. [ABSTRACT FROM AUTHOR]

We study scheduling problems on parallel dedicated machines. Thus, each job can be processed on one specific machine only. The option of job-rejection is considered, and the total permitted rejection cost of all the jobs is bounded. Six scheduling problems are solved: ( $ i $ i) minimising makespan, ( $ ii $ ii) minimising makespan with release-dates, ( $ iii $ iii) minimising total completion time, ( $ iv $ iv) minimising total weighted completion time, ( $ v $ v) minimising total load, and ( $ vi $ vi) minimising maximum tardiness. Pseudo-polynomial dynamic programming algorithms are introduced for all these NP-hard problems. [ABSTRACT FROM AUTHOR]

A solution approach is proposed for the interday problem of assigning chemotherapy sessions at a network of treatment centres with the goal of increasing the cost-efficiency of system-wide capacity use. This network-based scheduling procedure is subject to the condition that both the first and last sessions of a patient's treatment protocol are administered at the same centre the patient is referred to by their oncologist. All intermediate sessions may be administered at other centres. It provides a systematic way of identifying effective multi-appointment scheduling policies that exploit the total capacity of a networked system, allowing patients to be treated at centres other than their home centre. The problem is modelled as a Markov decision process which is then solved approximately using techniques of approximate dynamic programming. The benefits of the approach are evaluated and compared through simulation with the existing manual scheduling procedures at two treatment centres in Santiago, Chile. The results suggest that the approach would obtain a 20% reduction in operating costs for the whole system and cut existing first-session waiting times by half. A key conclusion, however, is that a network-based scheduling procedure brings no real benefits if it is not implemented in conjunction with a proactive assignment policy like the one proposed in this paper. [ABSTRACT FROM AUTHOR]

This paper studies a multi-period dynamic production planning problem in a hybrid manufacturing and remanufacturing system (HMRS), where new and remanufactured products are perfect substitutes. The HMRS encounters uncertain return amounts due to products' random usage durations. As returns are from previous sales, production planning in each period impacts both current sales and future returns. The random return amount and the correlation among different periods make it a complex system. To solve the problem, we first utilise the hazard rate function and in-use products' information to derive an estimator of the return amount. Then, we formulate a dynamic programming model and prove a threshold policy is optimal under uniformly distributed demand. We employ marginal analysis to derive an approximation of the optimal threshold value. Through simulating all alternatives, the derived threshold is verified to be a good approximation as it achieves more than 99% of the optimal revenue in most scenarios. In addition, the calculated return amount based on the hazard rate function is almost identical to the return amount obtained via simulation. Compared to other return measurements, our method achieves the highest revenue in all considered scenarios, including heterogeneous usage durations and general demand distributions. [ABSTRACT FROM AUTHOR]

This paper addresses the problem of stochastic jointly scheduling of resumable jobs and preventive maintenance on a single machine, subject to random breakdowns, to minimise the earliness-tardiness cost. The main objective is to investigate using trending machine learning-based methods compared to stochastic optimisation approaches. We propose two different methods from both fields as we solve the same problem firstly with a stochastic dynamic programming model in an approximation way, then with an attention-based deep reinforcement learning model. We conduct a detailed experimental study according to solution quality, run time, and robustness to analyse their performances compared to those of an existing approach in the literature as a baseline. Both algorithms outperform the baseline. Moreover, the machine learning-based algorithm outperforms the stochastic dynamic programming-based heuristic as we report up to 30.5% saving in total cost, a reduction of computational time from 67 min to less than $ 1s $ 1 s on big instances, and a better robustness. These facts highlight clearly its potential for solving such problems. [ABSTRACT FROM AUTHOR]

In this paper, we address the problem of scheduling jobs on identical machines for minimising the maximum completion time (makespan). Each job requires a sequence-independent setup time, which represents the time needed to prepare the machines for job execution. Then, we introduce a dynamic programme to solve the case with two machines, and show that this problem admits a fully polynomial time approximation scheme. For the case of m machines, we propose heuristics and an adapted genetic algorithm. Some numerical experiments are done to evaluate the proposed algorithms. [ABSTRACT FROM AUTHOR]

The costs of foraging can be high while also carrying significant risks, especially for consumers feeding at the top of the food chain. To mitigate these risks, many predators supplement active hunting with scavenging and kleptoparasitic behaviours, in some cases specializing in these alternative modes of predation. The factors that drive differential utilization of these tactics from species to species are not well understood. Here, we use an energetics approach to investigate the survival advantages of hunting, scavenging and kleptoparasitism as a function of predator, prey and potential competitor body sizes for terrestrial mammalian carnivores. The results of our framework reveal that predator tactics become more diverse closer to starvation, while the deployment of scavenging and kleptoparasitism is strongly constrained by the ratio of predator to prey body size. Our model accurately predicts a behavioural transition away from hunting towards alternative modes of predation with increasing prey size for predators spanning an order of magnitude in body size, closely matching observational data across a range of species. We then show that this behavioural boundary follows an allometric power-law scaling relationship where the predator size scales with an exponent nearing 3/4 with prey size, meaning that this behavioural switch occurs at relatively larger threshold prey body size for larger carnivores. We suggest that our approach may provide a holistic framework for guiding future observational efforts exploring the diverse array of predator foraging behaviours.

Autonomous vehicle storage and retrieval systems (AVS/RSs) are widely used in e-commerce warehouses due to their high throughput and flexibility. In such systems, storage and retrieval transactions are performed by lifts and vehicles. This paper focuses on the sequencing retrievals problem in an AVS/RS, which is an important problem for daily operations. We formulate this sequencing problem as a mixed-integer program to determine a retrieval sequence for the lift and the vehicles, one that minimises the makespan. A dynamic programming approach is proposed to solve the sequencing problem to optimality. However, the solution time of the dynamic programming method is exponentially increasing in the number of retrieval requests. To be more practical, we present a beam search heuristic that can solve large-sized instances in reasonable time. Computational experiments verify that near-optimal solutions can be found by the beam search heuristic. Compared to commonly used heuristics and straightforward heuristics, the beam search decreases the makespan by up to 15%. Finally, we analyse how vehicle modes impact the makespan, showing evidence that a small makespan can be achieved when considering a realistic mode of vehicles. [ABSTRACT FROM AUTHOR]

Manufacturers experience random environmental fluctuations that influence their supply and demand processes directly. To cope with these environmental fluctuations, they typically utilise operational hedging strategies in terms of pricing, manufacturing, and procurement decisions. We focus on this challenging problem by proposing an analytical model. Specifically, we study an integrated problem of procurement, manufacturing, and pricing strategies for a continuous-review make-to-stock system operating in a randomly fluctuating environment with exponentially distributed processing times. The environmental changes are driven by a continuous-time discrete state-space Markov chain, and they directly affect the system's procurement price, raw material flow rate, and price-sensitive demand rate. We formulate the system as an infinite-horizon Markov decision process with a long-run average profit criterion and show that the optimal procurement and manufacturing strategies are of state-dependent threshold policies. Besides that, we provide several analytical results on the optimal pricing strategies. We introduce a linear programming formulation to numerically obtain the system's optimal decisions. We, particularly, investigate how production rate, holding cost, procurement price and demand variabilities, customers' price sensitivity, and interaction between supply and demand processes affect the system's performance measures through an extensive numerical study. Furthermore, our numerical results demonstrate the potential benefits of using dynamic pricing compared to that of static pricing. In particular, the profit enhancement being achieved with dynamic pricing can reach up to 15%, depending on the problem parameters. [ABSTRACT FROM AUTHOR]

We study the single item capacitated lot sizing problem with multiple resources and periodic carbon emission constraints that impose an upper bound for the average emission per product produced in any period. Although the uncapacitated version of this problem can be solved in polynomial time, generalisation of the problem including the resource capacities is NP-Hard, in general. We present important structural properties for the optimal solutions of the problem. We consider the special cases with two resources and under non-speculative costs, construct the piecewise linear total production cost function when the resource capacities, and the emission and cost parameters are time-invariant, and develop a polynomial time dynamic programming algorithm (DP) to solve them. Then, we generalise the procedure to construct the total production cost function and the DP for the general setting with fixed number of capacitated resources. We test our algorithm for different problem instances, and compare it with a commercial solver and a DP available in the literature for solving the lot sizing problem with piecewise concave production cost functions. The results reveal that our DP outperforms the other one, and it performs better than the commercial solver when the number of breakpoints of the total production cost function is small. [ABSTRACT FROM AUTHOR]

Dispersive early life stages are common in nature. Although many dispersing organisms (propagules) are passively moved by outside forces, some improve their chances of successful dispersal through weak movements that exploit the structure of the environment to great effect. The larvae of many coastal marine invertebrates, for instance, swim vertically through the water column to exploit depth-varying currents, food abundance, and predation risk. Several swimming behaviors and their effects on dispersal between habitats are characterized in the literature, yet it remains unclear when and why these behaviors are advantageous. We addressed this gap using a mathematical model of larval dispersal that scored how well behaviors allowed larvae to simultaneously locate habitats, avoid predators, and gather energy. We computed optimal larval behaviors through dynamic programming, and compared those optima against passive floating and three well documented behaviors from the literature. Optimal behaviors often (but not always) resembled the documented ones. However, our model predicted that the behaviors from the literature performed robustly well, if not optimally, across many conditions. Our results shed light on why some larval behaviors are widespread geographically and across species, and underscore the importance of carefully considering the weak movements of otherwise passive propagules when studying dispersal.

Recent work in reinforcement learning has leveraged symmetries in the model to improve sample efficiency in training a policy. A commonly used simplifying assumption is that the dynamics and reward both exhibit the same symmetry; however, in many real-world environments, the dynamical model exhibits symmetry independent of the reward model. In this letter, we assume only the dynamics exhibit symmetry, extending the scope of problems in reinforcement learning and learning in control theory to which symmetry techniques can be applied. We use Cartan's moving frame method to introduce a technique for learning dynamics that, by construction, exhibit specified symmetries. Numerical experiments demonstrate that the proposed method learns a more accurate dynamical model.

Traffic congestion is a major concern in urban transportation in supply chain management. Road-based logistic companies can mitigate their Carbon dioxide (CO2) emissions effectively by optimising their operation. In this study, we observed a low-carbon, fixed-tour scheduling problem with time windows (LC-FTSP-TW) that is designed to consider the factors that can minimise the greenhouse-gas emissions of logistics systems. Through better planning of the delivery times, we delineated a system to control the schedules of two vehicle types: fossil-fuel-powered and electric-powered vehicles. We formulated the LC-FTSP-TW as a mixed-integer linear programming model that can take into consideration time-varying traffic conditions, customer time windows, and vehicle energy-consumption functions. The proposed model was observed to be convenient for practical use, as it could be solved directly using commercial optimisation toolboxes, such as CPLEX and Gurobi, with continuous optimal results. In addition, we developed an efficient dynamic programming algorithm for solving large-sized problems with discrete optimal results. Computational experiments were conducted on a group of test instances to verify the proposed model and algorithm, which demonstrated considerable reductions in CO2 emissions compared to non-optimised solutions for both the tested fossil-fuel-powered and electric-powered vehicles. [ABSTRACT FROM AUTHOR]

We seek to optimize the production planning of a three-echelon remanufacturing system under uncertain input data. We consider a multi-stage stochastic integer programming approach and use scenario trees to represent the uncertain information structure. We introduce a new dynamic programming formulation that relies on a partial nested decomposition of the scenario tree. We then propose a new approximate stochastic dual dynamic integer programming algorithm based on this partial decomposition. Our numerical results show that the proposed solution approach is able to provide near-optimal solutions for large-size instances with a reasonable computational effort. [ABSTRACT FROM AUTHOR]

A multi-armed bandit (MAB) problem is described as follows. At each time-step, a decision-maker selects one arm from a finite set. A reward is earned from this arm and the state of that arm evolves stochastically. The goal is to determine an arm-pulling policy that maximizes expected total discounted reward over an infinite horizon. We study MAB problems where the rewards are multivariate Gaussian, to account for data-driven estimation errors. We employ a percentile optimization approach, wherein the goal is to find an arm-pulling policy that maximizes the sum of percentiles of expected total discounted rewards earned from individual arms. The idea is motivated by recent work on percentile optimization in Markov decision processes. We demonstrate that, when applied to MABs, this yields an intractable second-order cone program (SOCP) whose size is exponential in the number of arms. We use Lagrangian relaxation to break the resulting curse-of-dimensionality. Specifically, we show that the relaxed problem can be reformulated as an SOCP with size linear in the number of arms. We propose three approaches to recover feasible arm-pulling decisions during run-time from an off-line optimal solution of this SOCP. Our numerical experiments suggest that one of these three method appears to be more effective than the other two. [ABSTRACT FROM AUTHOR]

In the path version of the Travelling Salesman Problem (Path-TSP), a salesman is looking for the shortest Hamiltonian path through a set of n cities. The salesman has to start his journey at a given city s , visit every city exactly once, and finally end his trip at another given city t. In this paper we show that a special case of the Path-TSP with a Demidenko distance matrix is solvable in polynomial time. Demidenko distance matrices fulfill a particular condition abstracted from the convex Euclidian special case by Demidenko (1979) as an extension of an earlier work of Kalmanson (1975). We identify a number of crucial combinatorial properties of the optimal solution and design a dynamic programming approach with time complexity O (n 6). [ABSTRACT FROM AUTHOR]

The deterioration of environment and the proposal of carbon neutrality are causing the transformation of port freight transportation. Fuel cell hybrid trucks (FCHTs) may be a promising solution for port logistic with the characteristics of low speed, heavy duty and frequent start-stops. How to achieve efficient energy management for FCHTs in ports is a key issue, which is still in the initial stage. The objective of this study is to investigate the effects of dynamic programming (DP) strategy on energy management of FCHTs. With the intention of calculating power demands, the FCHT structure and the models of each component are established. In the DP method, the state of charge (SOC) of the battery, the power supplied by the battery, and hydrogen fuel consumption are regarded as the state variable, the decision variable, and the objective function, respectively. The simulation results under two different typical working conditions in ports show that the proposed DP outperforms existing genetic algorithm (GA) and rule-based strategy for reducing hydrogen fuel consumption by over 10%. Moreover, a set of instances among several FCHTs with different parameters and conditions suggest different influences of key feature parameters on hydrogen fuel consumption and SOC. Nearly 50% cost reduction of the FCHT in the "quay crane-yard " (QCY) cycle compared with diesel trucks at the current price indicates wide application prospect of FCHTs. At last, the results under different conditions reconfirm that DP is an excellent strategy to tackle energy management of FCHTs in ports with frequent start-stops and heavy-load scenarios. •Attempt to adopt dynamic programming (DP) into energy management of fuel cell hybrid trucks (FCHTs) in ports. •Two typical working conditions of port freight transportation are investigated. •The impacts of key feature parameters on the energy management strategies (EMSs) are analyzed. •DP has obvious advantages in heavy-load and frequent start-stop conditions in ports. [ABSTRACT FROM AUTHOR]

Gradient-based neural dynamics (GND) models are a classical algorithm for solving optimization problems, but it has non-negligible flaws in solving dynamic problems. In this study, a novel GND model, namely the zeroing feedback gradient-based neural dynamics (ZF-GND) models, is proposed based on the original GND model for tracking down the exact solution of dynamic quadratic programming problem (DQP). Further, a nonlinear projection function is designed to accelerate the convergence of the model. An upper bound on the convergence time of the ZF-GND model is rigorously defined through theoretical analysis. The superior effect of the ZF-GND model in terms of convergence is verified through comparison experiments. Finally, an application of robot motion planning is introduced to verify the practicality of the ZF-GND model. [ABSTRACT FROM AUTHOR]

This article proposes an H∞$$ {H}_{\infty } $$ optimal leader‐follower consensus control protocol with finite‐time prescribed performance for nonlinear multiagent systems suffering from the actuator fault based on the zero‐sum game framework. First, to guarantee the specified performance of the system within a finite time frame, a novel error transformation function (ETF) is constructed. The ETF proposed in this paper can adjust the mapping range of error transformation to achieve better error convergence performance, thereby enhancing the flexibility of the controller design. Then, to compensate for the negative impact of actuator fault, an error‐related item is separated from the optimal performance index function to design an online fault estimator, which can obtain a better error estimation accuracy. Furthermore, to lessen the need for difficult‐to‐verify persistent excitation signal in adaptive dynamic programming algorithm, both historical and real‐time data are applied to adjust the updating law of neural network weight. Moreover, it demonstrates that the signals within the closed‐loop system are bounded and the expected finite‐time prescribed performance can be ensured in the presence of faults. Finally, a numerical example of multiple single‐link robots manipulator system is executed to validate the efficacy of the developed scheme. [ABSTRACT FROM AUTHOR]

In this paper, we develop an integral reinforcement learning (IRL)‐based trajectory tracking control (TTC) scheme via firefly optimized neural networks for partially unknown multiplayer nonlinear systems. Under the developed TTC scheme, IRL is proved to be equivalent to the classical policy iteration, which guarantees the convergence of the IRL algorithm. By implementing the IRL method, the requirement of the drift dynamics is obviated. The TTC policy for each player is obtained by solving the coupled Hamilton–Jacobi equation with a critic neural network, whose weight vector is tuned by the firefly algorithm. The tracking error of the closed‐loop system is guaranteed to be stable via the Lyapunov's direct method. Simulation results illustrate the effectiveness and superiority of the present IRL‐based TTC scheme, and show that the success rate of system operation is increased by introducing the firefly algorithm. [ABSTRACT FROM AUTHOR]

High-throughput chromosome conformation capture (Hi-C) technology captures spatial interactions of DNA sequences into matrices, and software tools are developed to identify topologically associating domains (TADs) from the Hi-C matrices. With structural information theory, SuperTAD adopted a dynamic programming approach to find the TAD hierarchy with minimal structural entropy. However, the algorithm suffers from high time complexity. To accelerate this algorithm, we design and implement an approximation algorithm with a theoretical performance guarantee. We implemented a package, SuperTAD-Fast. Using Hi-C matrices and simulated data, we demonstrated that SuperTAD-Fast achieved great runtime improvement compared with SuperTAD. SuperTAD-Fast shows high consistency and significant enrichment of structural proteins from Hi-C data of human cell lines in comparison with the existing six hierarchical TADs detecting methods. [ABSTRACT FROM AUTHOR]

Motivated by computing duplication patterns in sequences, a new problem called the longest letter-duplicated subsequence (LLDS) is proposed. Given a sequence S of length n, a letter-duplicated subsequence is a subsequence of S in the form of x 1 d 1 x 2 d 2 ... x k d k with x i ∈ Σ , x j ≠ x j + 1 and d i ≥ 2 for all i in [k] and j in [ k - 1 ] . A linear time algorithm for computing a longest letter-duplicated subsequence (LLDS) of S can be easily obtained. In this paper, we focus on two variants of this problem: (1) 'all-appearance' version, i.e., all letters in Σ must appear in the solution, and (2) the weighted version. For the former, we obtain dichotomous results: We prove that, when each letter appears in S at least 4 times, the problem and a relaxed version on feasibility testing (FT) are both NP-hard. The reduction is from (3 + , 1 , 2 -) -SAT, where all 3-clauses (i.e., containing 3 lals) are monotone (i.e., containing only positive literals) and all 2-clauses contain only negative literals. We then show that when each letter appears in S at most 3 times, then the problem admits an O(n) time algorithm. Finally, we consider the weighted version, where the weight of a block x i d i (d i ≥ 2) could be any positive function which might not grow with d i . We give a non-trivial O (n 2) time dynamic programming algorithm for this version, i.e., computing an LD-subsequence of S whose weight is maximized. [ABSTRACT FROM AUTHOR]

• Temporary continuous observation task using non-customized constellation is studied. • A hybrid method for multi-satellite scheduling and task planning is proposed. • A joint simulation software system is developed via STK and Python. • The proposed technique has higher efficiency and target adaptability. This paper put forward a method to address the problem, of how to select multiple satellites from a given heterogeneous constellation and plan their tasks to implement a temporary mission for ground or aerial targets successive observation, while hardly affecting the constellation's original mission as much as possible. First, considering the observation geometric constraints of the satellite on the target, an observability analysis model for effective observation of the satellite on the target is established to characterize the observable spatio-temporal scope. Considering the time-length requirement of sustained observation on the target, a multi-satellite-to-target sustained observation model is constructed for the scheduling of satellites. Second, to address the problem of selecting task satellites in a given heterogeneous constellation, a mathematical model for task planning is established to maximize observation benefits and minimize task burdens. Third, a hybrid method of multi-satellite scheduling and task planning is designed with fault tolerance, based on dynamic programming and an improved contract network protocol algorithm. Next, a joint simulation software system is established through the secondary development of STK and Python, which includes satellite-target observability analysis, task satellite selection, task allocation and planning, and full process visible demonstration functions. Finally, simulation cases verified the effectiveness and superiority of the proposed technique. [ABSTRACT FROM AUTHOR]

We use some recent developments in dynamics programming method to obtain the complete and theoretically justified solution of a differential game formulated and studied in Chen and Qiu (Abstr Appl Anal 2014:1–8, 2014. https://doi.org/10.1155/2014/837431) using the Lanchester equation. We use a certain refinement of Cauchy's method of characteristics for stratified Hamilton–Jacobi equations to describe a large set of admissible trajectories and identify a domain on which the value function exists and is generated by a pair of admissible feedback strategies. Its optimality is justified by using one of the well-known verification theorems as an argument for sufficient optimality conditions. [ABSTRACT FROM AUTHOR]

State-of-the-art methods for solving 2-player zero-sum imperfect information games rely on linear programming or regret minimization, though not on dynamic programming (DP) or heuristic search (HS), while the latter are often at the core of state-of-the-art solvers for other sequential decision-making problems. In partially observable or collaborative settings (e.g., POMDPs and Dec-POMDPs), DP and HS require introducing an appropriate statistic that induces a fully observable problem as well as bounding (convex) approximators of the optimal value function. This approach has succeeded in some subclasses of 2-player zero-sum partially observable stochastic games (zs-POSGs) as well, but how to apply it in the general case still remains an open question. We answer it by (i) rigorously defining an equivalent game to work with, (ii) proving mathematical properties of the optimal value function that allow deriving bounds that come with solution strategies, (iii) proposing for the first time an HSVI-like solver that provably converges to an ϵ -optimal solution in finite time, and (iv) empirically analyzing it. This opens the door to a novel family of promising approaches complementing those relying on linear programming or iterative methods. [ABSTRACT FROM AUTHOR]

This paper tests a theory of strategic multi-product choice (SMPC) using empirical evidence from a large-scale choice experiment, two smaller longitudinal choice experiments, and multi-market panel data. Multi-product choice involves two stages. In the first stage, the consumer chooses a set of substitutable products, where "set" refers to both the variety of alternatives and the quantities of each. In the second stage, the set is consumed. Assuming consumers are strategic, their consumption decisions will consider both the utility of whichever product is selected for consumption and the expected utility (i.e., value) of the set that remains. SMPC therefore requires a dynamic model. We test two such dynamic models in this paper. These models are derived from a basic random utility framework with a stochastic error term for the utility of each product alternative at the moment of consumption. Despite maintaining state variables for the quantity of every alternative, these SMPC dynamic models offer both a value function and optimal consumption policy in closed form. These structures allow us to test for strategic consumption in the second stage and for optimality of the choice sets selected in the first stage. Data from the large-scale choice experiment and the smaller longitudinal choice experiments support strategic consumer decision-making, consistent with SMPC theory. SMPC theory further predicts that the amount of variety consumers select will be higher for lower consumption rates and lower for higher consumption rates. Evidence from panel data of yogurt purchases supports this prediction. While we find that consumption choices are consistent with SMPC theory, they are not consistent with alternative explanations such as variety seeking or diversification bias. Viewed in its entirety, the empirical evidence presented in this paper confirms that both the choice set selected and the way it is consumed are consistent with dynamic models of future preference uncertainty. [ABSTRACT FROM AUTHOR]

This work considers a short‐term, continuous time setting characterized by a coupled power supply system controlled exclusively by a single provider and comprising a cascade of hydropower systems (dams), fossil fuel power stations, and a storage capacity modeled by a single large battery. Cascaded hydropower generators introduce time‐delay effects in the state dynamics, which are modeled with differential equations, making it impossible to use classical dynamic programming. We address this issue by introducing a novel Lagrangian relaxation technique over continuous‐time constraints, constructing a nearly optimal policy efficiently. This approach yields a convex, nonsmooth optimization dual problem to recover the optimal Lagrangian multipliers, which is numerically solved using a limited memory bundle method. At each step of the dual optimization, we need to solve an optimization subproblem. Given the current values of the Lagrangian multipliers, the time delays are no longer active, and we can solve a corresponding nonlinear Hamilton–Jacobi–Bellman (HJB) Partial Differential Equation (PDE) for the optimization subproblem. The HJB PDE solver provides both the current value of the dual function and its subgradient, and is trivially parallelizable over the state space for each time step. To handle the infinite‐dimensional nature of the Lagrange multipliers, we design an adaptive refinement strategy to control the duality gap. Furthermore, we use a penalization technique for the constructed admissible primal solution to smooth the controls while achieving a sufficiently small duality gap. Numerical results based on the Uruguayan power system demonstrate the efficiency of the proposed mathematical models and numerical approach. [ABSTRACT FROM AUTHOR]

This article addresses adaptive event‐triggered discrete‐time nonlinear Markov jump systems (MJs) with DoS attacks, where the introduced DoS attacks are considered as more general stochastic models with fixed trigger frequency and duration. To solve the optimal control problem, we use an adaptive dynamic programming (ADP) algorithm based on policy iteration (PI). The approximate process is as follows: the performance index function (PIF) is first updated by the iteration policy in advance, and the control policy is obtained from the PIF. Subsequently, an approximate estimation of the optimal PIF and the optimal control policy is made using the actor‐critic structure obtained through neural network techniques. In order to reduce the occupied communication resources required for control policy iteration, we introduce an adaptive event triggering mechanism with an adaptive triggering threshold, which reduces the conservatism of resource occupation by the PIF compared to the fixed‐threshold ETM. In addition, an observer identifying the unknown dynamics part of the system is designed. Finally, using the Lyapunov function, it is shown that the designed control policy ensures the stability and convergence of the MJS, and the designed observer is effective. Simulation examples are given to verify the feasibility of the controller and the observer. [ABSTRACT FROM AUTHOR]

In this article, a distributed controller based on adaptive dynamic programming is proposed to solve the minimum loss problem of flywheel energy storage systems (FESS). We first formulate a performance function aiming to reduce total losses of FESS in power distribution applications. Then we use the Hamilton–Jacobi–Bellman (HJB) equation to solve this optimal control problem. The solution of the HJB equation is approximated by neural networks. To achieve distributed control, we estimate the global variables in the HJB equation by using the dynamic average consensus algorithm. A barrier Lyapunov function and a saturation function are introduced to handle the issue of state and input constraints, respectively. Then the stability of the system is proved through the Lyapunov stability analysis. Finally the effectiveness of the proposed strategy is verified by simulations. Simulation results show that FESS can track the power command while minimizing total power losses by interacting with neighbors. The proposed algorithm leads to a loss reduction of 1.13%$$ 1.13\% $$ compared to the equal power distribution strategy. [ABSTRACT FROM AUTHOR]

This paper studies a novel social commerce practice known as "help-and-haggle," whereby an online consumer can ask friends to help her "haggle" over the price of a product. Each time a friend agrees to help, the price is cut by a random amount, and if the consumer cuts the product price down to zero within a time limit, she will get the product for free; otherwise, the product reverts to the original price. Help-and-haggle enables the firm to promote its product and boost its social reach as consumers effectively refer their friends to the firm. We model the consumer's dynamic referral behavior in help-and-haggle and provide prescriptive guidance on how the firm should randomize price cuts. Our results are as follows. First, contrary to conventional wisdom, the firm should not always reduce the (realized) price-cut amount if referrals are less costly for the consumer. In fact, the minimum number of successful referrals the consumer must make to have a chance to win the product can be nonmonotone in referral cost. Second, relative to the deterministic price-cut benchmark, a random price-cut scheme improves firm payoff, extracts more consumer surplus, and widens social reach. Additionally, in most instances, it also reduces the promotion expense while increasing profit from product sales at the same time. Third, help-and-haggle can be more cost effective in social reach than a reward-per-referral program that offers a cash reward for each successful referral. However, using the prospect of a free product to attract referrals cannibalizes product sales, potentially causing help-and-haggle to fall short. Yet, if consumers are heterogeneous in product valuations and referral costs or face increasing marginal referral costs, help-and-haggle can outperform the reward-per-referral program. This paper was accepted by Elena Katok, operations management. Funding: L. Yang acknowledges the Berkeley Haas Center for Growth Markets [2022 Grant Award]. C. Jin acknowledges the Singapore Ministry of Education Academic Research Fund [Tier 1 Grant 251RES2101]. Z. Shao acknowledges support from the National Natural Science Foundation of China [Grant 72071188]. All authors acknowledge the Networks, Electronic Commerce and Telecommunications (NET) Institute [2022 Summer Research Grant]. Supplemental Material: The data files and online appendix are available at https://doi.org/10.1287/mnsc.2023.4948. [ABSTRACT FROM AUTHOR]

U.S. K–12 school districts that traditionally utilized ongoing "formative" assessments of student progress increasingly rely on additional "interim" assessments to predict student performance on standardized tests. Moreover, some districts are experimenting with merit-based teacher bonuses tied to standardized test scores. We examine the relationship between interim assessments and teacher bonuses using a two-period principal–agent model. The school district (principal), operating under a limited budget, decides whether to implement interim assessments and how much merit pay to offer, and teachers (agents) choose how much effort to exert in each period. We use two-state (proficient versus not proficient) Markovian dynamics to describe the evolution of student test readiness, in which the transition probability in a given period depends on both teachers' effort decisions and the starting state. Our results indicate that, despite the popularity of interim assessments, their usefulness is far from guaranteed. In particular, the accuracy promised by these assessments is a double-edged sword: positive midyear results can make it easier to incentivize second period teacher effort, but negative results can have a demotivating effect. Moreover, even when an interim assessment does result in a higher probability of the school ending the year in the proficient state, the resulting higher expected costs of merit-based bonuses for the district may exceed the available budget. Thus, even a free interim assessment might be too expensive for the school district. This paper was accepted by Charles Corbett, operations management. Funding: This research was supported by the Risk Management Center Russell Ackoff Doctoral Student Fellowship and the Fishman-Davidson Center for Service and Operations Management, both at The Wharton School, University of Pennsylvania, Philadelphia, Pennsylvania. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2020.01547. [ABSTRACT FROM AUTHOR]

This paper primarily investigates a neural-network-based safe control scheme for solving the optimal control problem of continuous-time (CT) nonlinear systems with asymmetric input constraints under non-zero-sum (NZS) differential game scenarios. Initially, by constructing a novel non-quadratic function, the issue of asymmetric input constraints in the non-zero-sum differential game controllers is addressed. Subsequently, the safe Hamilton-Jacobi-Bellman (HJB) equation is derived from the direct integration of the control barrier function (CBF) into the traditional cost function, ensuring that the system states remain within a safe region. Then, the safe learning control scheme based on single critic neural network (NN) and adaptive dynamic programming (ADP) is proposed to approximate the optimal control strategy, differing from the dual-network update method commonly used in traditional ADP. Based on the constructed neural network weight adjustment rules, the optimal solution to the HJB equation can be derived within the safe learning control framework. Following this, Lyapunov's stability theory demonstrates that the errors in neural network weights and all signals within the closed-loop system are uniformly ultimately bounded (UUB). Finally, the effectiveness of the developed neural-network-based safe learning control method is validated through two simulation results. [ABSTRACT FROM AUTHOR]

This study investigates the prize-collecting single machine scheduling with bounds and penalties (PC-SMS-BP). In this problem, a set of n jobs and a single machine are considered, where each job J j has a processing time p j , a profit π j and a rejection penalty w j . The upper bound on the processing number is U. The objective of this study is to find a feasible schedule that minimizes the makespan of the accepted jobs and the total rejection penalty of the rejected jobs under the condition that the number of the accepted jobs does not exceed a given threshold U while the total profit of the accepted jobs does not fall below a specified profit bound Π . We first demonstrate that this problem is NP-hard. Then, a pseudo-polynomial time dynamic programming algorithm and a fully polynomial time approximation scheme (FPTAS) are proposed. Finally, numerical experiments are conducted to compare the effectiveness of the two proposed algorithms. [ABSTRACT FROM AUTHOR]

We consider a dynamic duopoly game where firms choose both the timing and size of their investments. The existing real options literature predominantly consists of contributions where firms have a single option to invest. This paper relaxes this assumption by giving Firm A multiple options to undertake further investments with the purpose to expand whereas Firm B only holds the option to enter the market. In this asymmetric setting we get the surprising result that, in equilibrium, Firm B invests first. If Firm A invests first, Firm A and Firm B keep on being involved in preemption games for subsequent investments until Firm B enters the market, which leads to inefficiently early investments of Firm A. When Firm B invests first, then only one preemption game is played, which leads to Firm A being free to choose its unrestricted optimal investment moments. [ABSTRACT FROM AUTHOR]

In the real world, one of the most common problems in project management is the unpredictability of resources and timelines. An efficient way to resolve uncertainty problems and overcome such obstacles is through an extended fuzzy approach, often known as neutrosophic logic. Our rigorous proposed model has led to the creation of an advanced technique for computing the triangular single-valued neutrosophic number. This innovative approach evaluates the inherent uncertainty in project durations of the planning phase, which enhances the potential significance of the decision-making process in the project. Our proposed method, for the first time in the neutrosophic set literature, not only solves existing problems but also introduces a new set of problems not yet explored in previous research. A comparative study using Python programming was conducted to examine the effectiveness of responsive and adaptive planning, as well as their differences from other existing models such as the classical critical path problem and the fuzzy critical path problem. The study highlights the use of neutrosophic logic in handling complex projects by illustrating an innovative dynamic programming framework that is robust and flexible, according to the derived results, and sets the stage for future discussions on its scalability and application across different industries. [ABSTRACT FROM AUTHOR]

We investigate the optimal decisions on investment, consumption and purchasing life insurance of a household with two consecutive generations, say parents and children. Parents can invest in risk-free and risky assets, with the risky asset's price driven by the Heston local-stochastic volatility model, better reflecting market conditions. Life insurance can be purchased to hedge against wealth loss from parents' unexpected death before retirement, especially if children have no income. Meanwhile, utility functions of the parents and children are individually considered in relation to the uncertain lifetime. The objective of the household is to appropriately maximize the weighted average of the respective utilities of parents and children. In order to derive the optimal strategies, we adopt a dual method, Legendre transformation, and an asymptotic expansion technique to solve the associated Hamilton–Jacobi–Bellman equation achieved by a dynamic programming approach. Finally, an asymptotic solution is obtained and numerical examples are provided to illustrate the impacts of some important parameters on the optimal strategies. [ABSTRACT FROM AUTHOR]

Double Roman domination (DRD) is a combinatorial optimization problem posed on undirected graphs. It can be interpreted as allocating certain service providers (e.g., military formations, fire brigades or ambulances) to chosen locations within a certain area. Thereby the whole service (i.e., response to enemy attacks, fire or medical urgencies) should be established in a least expensive way, while still assuring a required "double Roman" level of availability and redundancy of providers. The standard version of DRD treated in the literature identifies the total expense of service with the total number of needed providers. In this paper a new "minimum-cost" version of DRD is considered, which is more general and more realistic than the standard version. It takes into account the fact that the actual expenses of providing service can differ from one location to another. Thus, formally speaking, each vertex in our graph is given a cost that is intepreted as the cost of keeping one service provider at the corresponding location. First, it is noted that the considered minimum-cost DRD problem is NP-hard, not only for general graphs but also for many special graph classes. Next, a dynamic programming algorithm is constructed, which shows that the problem can still be solved in linear time if the involved graph is a tree. Finally, as a solution for general graphs, a heuristic is proposed based on greedy construction and local search. Performance of both algorithms is evaluated by experiments. [ABSTRACT FROM AUTHOR]

Summary This article considers the output regulation problem of continuous‐time linear systems subject to input saturation in the scenario that the system dynamics are unknown. Based on the low‐gain technique and the output feedback technique, we construct an output feedback control law to solve the output regulation problem with input saturation. Since the system dynamics are unknown, we estimate the feedback and feedforward terms in the control law with a two‐step data‐driven method. An output feedback adaptive dynamic programming algorithm is proposed to estimate the feedback term. An online updating algorithm based on output tracking error is proposed to estimate the feedforward term directly without solving the output regulation equations. Both algorithms don't rely on the measurement of the internal states of the exosystem and the original system. We show that the input saturation caused by the iterative feedforward gain matrix in the online updating algorithm doesn't affect the convergence of the algorithm. With these two data‐driven algorithms, the control law doesn't rely on the dynamics anymore. The low‐gain control law obtained by the model‐free method prevents input saturation from occurring and hence solves the output regulation problem. Finally, a numerical example is provided to validate the theoretical results. [ABSTRACT FROM AUTHOR]

This research is dedicated to developing a min–max robust control strategy for a dynamic game involving pursuers, evaders, and defenders in a multiple-missile scenario. The approach employs neural dynamic programming, utilizing multiple continuous differential neural networks (DNNs). The competitive controller devised addresses the robust optimization of a joint cost function that relies on the trajectories of the pursuer–evader–defender system, accommodating an uncertain mathematical model while adhering to control restrictions. The dynamic programming min–max formulation facilitates robust control by accounting for bounded modeling uncertainties and external disturbances for each game component. The value function of the Hamilton–Jacobi–Bellman (HJB) equation is approximated by a DNN, enabling the estimation of the closed-loop formulation for the joint dynamic game with state restrictions. The controller’s design is grounded in estimating the state trajectory under the worst possible uncertainties and perturbations, providing a robustness factor through the robust neural controller. The learning law class for the time-varying weights in the DNN is generated by studying the HJB partial differential equation for the missile motion for each player in the dynamic game. The controller incorporates the solution of the obtained learning laws and a time-varying Riccati equation, offering an online solution to the control implementation. A recurrent algorithm, based on the Kiefer–Wolfowitz method, adjusts the initial conditions for the weights to satisfy the final condition of the given cost function for the dynamic game. A numerical example is presented to validate the proposed robust control methodology, confirming the optimization solution based on the DNN approximation for Bellman’s value function. [ABSTRACT FROM AUTHOR]

To further improve the fuel economy of hybrid tractors, an energy management strategy based on model predictive control (MPC) solved by dynamic programming (DP) is proposed, taking into account the various typical operating conditions of tractors. A coupled dynamics model was constructed for a series diesel–electric hybrid tractor under three typical working conditions: plowing, rotary tillage, and transportation. Using DP to solve for the globally optimal SOC change trajectory under each operating condition of the tractor as the SOC constraint for MPC, we designed an energy management strategy based on DP-MPC. Finally, a hardware-in-the-loop (HIL) test platform was built using components such as Matlab/Simulink, NI-Veristand, PowerCal, HIL test cabinet, and vehicle controller. The designed energy management strategy was then tested using the HIL test platform. The test results show that, compared with the energy management strategy based on power following, the DP-MPC-based energy management strategy reduces fuel consumption by approximately 7.97%, 13.06%, and 11.03%, respectively, under the three operating conditions of plowing, rotary tillage, and transportation. This achieves fuel-saving performances of approximately 91.34%, 94.87%, and 96.69% compared to global dynamic programming. The test results verify the effectiveness of the proposed strategy. This research can provide an important reference for the design of energy management strategies for hybrid tractors. [ABSTRACT FROM AUTHOR]

The affine formation maneuver (AFM) control problem using the zero-sum differential game is studied for a second-order multi-agent system (MAS) against cyber-injection attacks on the actuators. First and foremost, the distributed control signals and the cyber-injected attack signals are viewed as two competing teams. Then, the leader-follower tracking error system is established where the followers aim to track the AFMs of the leaders. The leader-follower distributed optimal control policies and the cyber-attack attenuation policies are derived from the Nash equilibrium solution of the Hamilton-Jacobi-Isaac (HJI) equation. The solution of the HJI equation is estimated with the aid of the critic neural network. The weights of the critic system are learned online based on the adaptive dynamic programming (ADP) scheme. The uniformly ultimately bounded stability of the closed-loop system under the formulated zero-sum differential game control strategy has been proven by the Lyapunov stability theorem. A simulation example illustrates that the presented control method can attenuate cyber-injection attacks on the actuators and maintain the AFMs of the agents. [ABSTRACT FROM AUTHOR]

In this paper, the model‐free robust control problem is investigated for nonlinear systems with a relaxed condition of initial admissible control. An advanced integral reinforcement learning method is developed, which merges the adaptive network‐based fuzzy inference system (ANFIS) and pre‐training of the initial weights. To loose the condition for choosing the initial control law, pre‐training of initial weights is established by utilizing the ANFIS to provide the information corresponding to the system model, which is applicable to the model‐free issue. Based on the actor‐critic structure, the approximate optimal control law is obtained by employing adaptive dynamic programming. Redesigning the obtained control law, the robust controller can be derived to stabilize the system with the uncertain term. Eventually, two examples are utilized to verify the effectiveness of the constructed algorithm. [ABSTRACT FROM AUTHOR]

AbstractIn this article, we analyze a robust optimal reinsurance and investment problem in a model with default risks and jumps for a general company which holds shares of an insurer and a reinsurer. The insurer’s surplus is characterized by a diffusion model and the insurer has the opportunity to buy proportional reinsurance from the reinsurer. Moreover, the insurer can invest in a risk-free asset (bank account), a risky asset (stock), and a defaultable bond. Meanwhile, the reinsurer can also invest in a risk-free asset and another risky asset. The price dynamics of the risky asset is assumed to follow a jump-diffusion model. What is more, the general company is concerned about the ambiguity and aims to find a robust optimal reinsurance and investment strategy. The objective of the general company is to maximize the minimal expected exponential utility of the weighted sums of the insurer’s and the reinsurer’s terminal wealth. Applying stochastic dynamic programming approach, we first establish the robust HJB (Hamilton-Jacobi-Bellman) equations for the post-default case and the pre-default case, respectively. Furthermore, we obtain the robust optimal strategy explicitly and present the corresponding verification theorem. Finally, we give some numerical examples to demonstrate the influences of model parameters on the robust optimal strategy. [ABSTRACT FROM AUTHOR]

The problem of computing the longest common subsequence of two sequences (LCS for short) is a classical and fundamental problem in computer science. In this article, we study four variants of LCS : the Repetition-Bounded Longest Common Subsequence problem (RBLCS), the Multiset-Restricted Common Subsequence problem (MRCS), the Two-Side-Filled Longest Common Subsequence problem (2FLCS), and the One-Side-Filled Longest Common Subsequence problem (1FLCS). Although the original LCS can be solved in polynomial time, all these four variants are known to be NP-hard. Recently, an exact, O (1. 4422 5 n) -time, dynamic programming (DP) based algorithm for RBLCS was proposed, where the two input sequences have lengths n and p o l y (n). Here, we first establish that each of MRCS , 1FLCS , and 2FLCS is polynomially equivalent to RBLCS. Then, we design a refined DP-based algorithm for RBLCS that runs in O (1. 4142 2 n) time, which implies that MRCS , 1FLCS , and 2FLCS can also be solved in O (1. 4142 2 n) time. Finally, we give a polynomial-time 2-approximation algorithm for 2FLCS. [ABSTRACT FROM AUTHOR]

Summary: In the paper, we compute some lower bounds on time of parallel solving of the subset sum problem on a big number of processors by several versions of dynamic programming algorithm Balsub proposed before by Pisinger. Based on these lower bounds, we propose a version of Balsub which could be possibly effectively parallelized. [ABSTRACT FROM AUTHOR]

The transformation of energy structure has brought about new changes in the power system, and the environmentally friendly gas switchgear with the goal of low carbon and environmental protection has been widely spread and applied, but due to its short application time and the accumulation of related research, it continues to carry out life prediction to improve the related operation and maintenance system. The article proposes the environmental protection gas switchgear data processing technology based on data enhancement technology, proposes the environmental protection gas switchgear life prediction technology based on approximate dynamic planning, and verifies the algorithm through case analysis, which proves the effectiveness and accuracy of the proposed method. [ABSTRACT FROM AUTHOR]

As countries worldwide strive to implement energy conservation and emission reduction measures, modeling consumers’ low-carbon preferences and purchasing decisions has become a crucial factor in implementing dynamic pricing strategies for firms. This paper investigates the dynamic pricing problems for a single perishable product and substitutable perishable products, respectively, where consumer is affected by low-carbon preference. We first propose the decision framework of consumer choice with low-carbon preference based on the multinomial logit model. On this basis, we establish dynamic pricing models by the dynamic programming method and obtain the optimal pricing strategies. We analytically show that consumer’s low-carbon preference has a positive effect on the optimal price for a single perishable product. Meanwhile, numerical examples illustrate that consumer’s low-carbon preference has a positive effect on the optimal prices for substitutable perishable products. Finally, we give some suggestions to increase firm’s revenue when consumer’s low-carbon preference is present. [ABSTRACT FROM AUTHOR]

In this paper, we propose a multidimensional statistical model of intraday electricity prices at the scale of the trading session, which allows all products to be simulated simultaneously. This model, based on Poisson measures and inspired by the Common Shock Poisson Model, reproduces the Samuelson effect (intensity and volatility increases as time to maturity decreases). It also reproduces the price correlation structure, highlighted here in the data, which decreases as two maturities move apart. This model has only three parameters that can be estimated using a moment method that we propose here. We demonstrate the usefulness of the model on a case of storage valuation by dynamic programming over a trading session. [ABSTRACT FROM AUTHOR]