The task of projecting onto norm balls is ubiquitous in statistics and machine learning, yet the availability of actionable algorithms for doing so is largely limited to the special cases of . In this paper, we introduce novel, scalable methods for projecting onto the -ball for general . For , we solve the univariate Lagrangian dual via a dual Newton method. We then carefully design a bisection approach For , presenting theoretical and empirical evidence of zero or a small duality gap in the non-convex case. The success of our contributions is thoroughly assessed empirically, and applied to large-scale regularized multi-task learning and compressed sensing. The code implementing our methods is publicly available on Github.

Health and convenience are two indispensable indicators of the society promotion. Nowadays, to improve community health levels, the comfort of patients and those in need of health services has received much attention. Providing Home Health Care (HHC) services is one of the critical issues of health care to improve the patient convenience. However, manual nurse planning which is still performed in many HHC institutes results in a waste of time, cost, and ultimately lower efficiency. In this research, a multi-objective mixed-integer model is presented for home health care planning so that in addition to focusing on the financial goals of the institution, other objectives that can help increase productivity and quality of services are highlighted. Therefore, four different objectives of the total cost, environmental emission, workload balance, and service quality are addressed. Taking into account medical staff with different service levels, and the preferences of patients in selecting a service level, as well as different vehicle types, are other aspects discussed in this model. The epsilon-constraint method is implemented in CPLEX to solve small-size instances. Moreover, a Multi-Objective Variable Neighborhood Search (MOVNS) composed of nine local neighborhood moves is developed to solve the practical-size instances. The results of the MOVNS are compared with the epsilon-constraint method, and the strengths and weaknesses of the proposed algorithm are demonstrated by a comprehensive sensitivity analysis. To show the applicability of the algorithm, a real example is designed based on a case study, and the results of the algorithm over real data are evaluated.

When an infectious disease spreads, how to quickly vaccinate with a limited budget per time step to reduce the impact of the virus is very important. Specifically, vaccination will be carried out in every time step, and vaccinated nodes will no longer be infected. Meanwhile, the protection from vaccination can spread to the neighbors of a vaccinated node. Our goal is to efficiently find optimal and approximation solutions to our problem with various algorithms. In this paper, we first design an integer linear program to solve this problem. We then propose approximation algorithms of (1) Linear programming (LP) deterministic threshold rounding, (2) LP dependent randomized rounding, and (3) LP independent randomized rounding. We prove that the LP independent randomized rounding algorithm has a high probability of finding a feasible solution that gives an approximation ratio of , where a small constant between 0 and 1 reduces the lower bound on the . We also provide experimental results for three different rounding algorithms to show that they perform numerically well in terms of approximation ratios. These analytical and numerical studies allow each individual to adopt the most appropriate approximation algorithm to efficiently resolve the vaccination problem when her reliance on commercial optimization solvers is costly.

Classical facility location models can generate solutions that do not maintain consistency in the set of utilized facilities as the number of utilized facilities is varied. We introduce the concept of nested facility locations, in which the solution utilizing facilities is a subset of the solution utilizing facilities, for all ≤ < ≤ , given some lower limit and upper limit on , the number of facilities that will be utilized in the future. This approach is demonstrated with application to the -median model, with computational testing showing these new models achieve reductions in both average regret and worst-case regret when ≠ facilities are actually utilized.

We consider the problem of minimizing a smooth convex objective function subject to the set of minima of another differentiable convex function. In order to solve this problem, we propose an algorithm which combines the gradient method with a penalization technique. Moreover, we insert in our algorithm an inertial term, which is able to take advantage of the history of the iterates. We show weak convergence of the generated sequence of iterates to an optimal solution of the optimization problem, provided a condition expressed via the Fenchel conjugate of the constraint function is fulfilled. We also prove convergence for the objective function values to the optimal objective value. The convergence analysis carried out in this paper relies on the celebrated Opial Lemma and generalized Fejér monotonicity techniques. We illustrate the functionality of the method via a numerical experiment addressing image classification via support vector machines.

This paper generalizes inverse optimization for multi-objective linear programming where we are looking for the least problem modifications to make a given feasible solution a weak efficient solution. This is a natural extension of inverse optimization for single-objective linear programming with regular "optimality" replaced by the "Pareto optimality". This extension, however, leads to a non-convex optimization problem. We prove some special characteristics of the problem, allowing us to solve the non-convex problem by solving a series of convex problems.

This paper addresses a real-life personnel scheduling problem in the context of Covid-19 pandemic, arising in a large Italian pharmaceutical distribution warehouse. In this case study, the challenge is to determine a schedule that attempts to meet the contractual working time of the employees, considering the fact that they must be divided into mutually exclusive groups to reduce the risk of contagion. To solve the problem, we propose a mixed integer linear programming formulation (MILP). The solution obtained indicates that optimal schedule attained by our model is better than the one generated by the company. In addition, we performed tests on random instances of larger size to evaluate the scalability of the formulation. In most cases, the results found using an open-source MILP solver suggest that high quality solutions can be achieved within an acceptable CPU time. We also project that our findings can be of general interest for other personnel scheduling problems, especially during emergency scenarios such as those related to Covid-19 pandemic.

The is a special case of the (BMEP) that consists of finding the assignment of a set of taxa to the leaves of a given unrooted binary tree so as to minimize the BMEP objective function. Deciding the computational complexity of the FT-BMEP has been an open problem for almost a decade. Here, we show that a few modifications to Fiorini and Joret's proof of the -hardness of the BMEP suffice to prove the general -hardness of the FT-BMEP as well as its strong inapproximability.

During major infectious disease outbreak, such as COVID-19, the goods and parcels supply and distribution for the isolated personnel has become a key issue worthy of attention. In this study, we propose a delivery problem that arises in the last-mile delivery during major infectious disease outbreak. The problem is to construct a Hamiltonian tour over a subset of candidate parking nodes, and each customer is assigned to the nearest parking node on the tour to pick up goods or parcels. The aim is to minimize the total cost, including the routing, allocation, and parking costs. We propose three models to formulate the problem, which are node-based, flow-based and bilevel programing formulations. Moreover, we develop a variable neighborhood search algorithm based on the ideas from the bilevel programing formulations to solve the problem. Finally, the proposed algorithm is tested on a set of randomly generated instances, and the results indicate the effectiveness of the proposed approach.

In this paper, we propose optimization models to address flexible staff scheduling problems and some main issues arising from efficient workforce management during the Covid-19 pandemic. The adoption of precautionary measures to prevent the pandemic from spreading has raised the need to rethink quickly and effectively the way in which the workforce is scheduled, to ensure that all the activities are conducted in a safe and responsible manner. The emphasis is on novel optimization models that take into account demand requirements, employees' personal and family responsibilities, and anti-Covid-19 measures at the same time. It is precisely considering the anti-Covid-19 measures that the models allow to define the working mode to be assigned to the employees: working remotely or on-site. The last optimization model, which can be viewed as the most general and the most flexible formulation, has been developed to capture the specificity of a real case study of an Italian University. In order to improve employees' satisfaction and ensure the best work/life balance possible, an alternative partition of a workday into shifts to the usual two shifts, morning and afternoon, is proposed. The model has been tested on real data provided by the Department of Mechanical, Energy and Management Engineering, University of Calabria, Italy. The computational experiments show good performance and underline the potentiality of the model to handle worker safety requirements and practicalities and to ensure work activities continuity. In addition, the non-cyclic workforce policy, based on the proposed workday organization, is preferred by employees, since it allows them to better meet their needs.

Banjac et al. (J Optim Theory Appl 183(2):490-519, 2019) recently showed that the Douglas-Rachford algorithm provides certificates of infeasibility for a class of convex optimization problems. In particular, they showed that the difference between consecutive iterates generated by the algorithm converges to certificates of primal and dual strong infeasibility. Their result was shown in a finite-dimensional Euclidean setting and for a particular structure of the constraint set. In this paper, we extend the result to real Hilbert spaces and a general nonempty closed convex set. Moreover, we show that the proximal-point algorithm applied to the set of optimality conditions of the problem generates similar infeasibility certificates.

The spatial price equilibrium modeling framework, which emphasizes the importance of transportation costs between markets, has been utilized in agricultural, energy, mineral as well as financial applications. In this paper, we construct static and dynamic spatial price equilibrium networks with flow-dependent arc multipliers, which expand the reach of applications. The static model is formulated and analyzed as a variational inequality problem, whereas the dynamic one is formulated as a projected dynamical system, whose set of stationary points coincides with the set of solutions of the variational inequality. Qualitative results are presented, along with an algorithm, the Euler method, which yields a time-discretization of the continuous-time adjustment processes associated with the product shipments from supply markets to demand markets. The algorithm is implemented and applied to compute solutions to numerical examples with flow-dependent arc multipliers addressing losses and/or gains, inspired by perishable agricultural products, and by financial investments. The results in this paper add to the literature on generalized networks as well as that on commodity trade.

Mathematical approaches, such as compartmental models and agent-based models, have been utilized for modeling the spread of the infectious diseases in the computational epidemiology. However, the role of social network structure for transmission of diseases is not explicitly considered in these models. In this paper, the influence maximization problem, considering the diseases starting at some initial nodes with the potential to maximize the spreading in a social network, is adapted to model the spreading process. This approach includes the analysis of network structure and the modeling of connections among individuals with probabilities to be infected. Additionally, individual behaviors that change along the time and eventually influence the spreading process are also included. These considerations are formulated by integer optimization models. Simulation results, based on the randomly generated networks and a local community network under the COVID-19, are performed to validate the effectiveness of the proposed models, and their relationships to the classic compartmental models.

Portfolio risk management has become more important since some unpredictable factors, such as the 2008 financial crisis and the recent COVID-19 crisis. Although the risk can be actively managed by risk diversification, the high transaction cost and managerial concerns ensue by over diversifying portfolio risk. In this paper, we jointly integrate risk diversification and sparse asset selection into mean-variance portfolio framework, and propose an optimal portfolio selection model labeled as JMV. The weighted piecewise quadratic approximation is considered as a penalty promoting sparsity for the asset selection. The variance associated with the marginal risk regard as another penalty term to diversify the risk. By exposing the feature of JMV, we prove that the KKT point of JMV is the local minimizer if the regularization parameter satisfies a mild condition. To solve this model, we introduce the accelerated proximal gradient (APG) algorithm [Wen in SIAM J. Optim 27:124-145, 2017], which is one of the most efficient first-order large-scale algorithm. Meanwhile, the APG algorithm is linearly convergent to a local minimizer of the JMV model. Furthermore, empirical analysis consistently demonstrate the theoretical results and the superiority of the JMV model.

We will make a link between the steepest descent method for an unconstrained minimisation problem and fixed-point iterations for its Euler-Lagrange equation. In this context, we shall rediscover the preconditioned algebraic conjugate gradient method for the discretised problem. The benefit of the connection of those concepts will be illustrated by a numerical experiment.

We propose an extension of two-player zero-sum games, where one player may select available actions for themselves and the opponent, subject to a budget constraint. We present a mixed-integer linear programming (MILP) formulation for the problem, provide analytical results regarding its solution, and discuss applications in the security and advertising domains. Our computational experiments demonstrate that heuristic approaches, on average, yield suboptimal solutions with at least a 20% relative gap with those obtained by the MILP formulation.