Search

The separable convex resource allocation problem with nested bound constraints aims to allocate B units of resources to n activities to minimize a separable convex cost function, with lower and upper bounds on the total amount of resources that can be consumed by nested subsets of activities. We develop a new combinatorial algorithm to solve this model exactly. Our algorithm is capable of solving instances with millions of activities in several minutes. The running time of our algorithm is at most 73% of the running time of the current best algorithm for benchmark instances with three classes of convex objectives. The efficiency of our algorithm derives from a combination of constraint relaxation and divide and conquer based on infeasibility information. In particular, nested bound constraints are relaxed first; if the solution obtained violates some bound constraints, we show that the problem can be divided into two subproblems of the same structure and smaller sizes according to the bound constraint with the largest violation. Summary of Contribution. The resource allocation problem is a collection of optimization models with a wide range of applications in production planning, logistics, portfolio management, telecommunications, statistical surveys, and machine learning. This paper studies the resource allocation model with prescribed lower and upper bounds on the total amount of resources consumed by nested subsets of activities. These nested bound constraints are motivated by storage limits, time-window requirements, and budget constraints in various applications. The model also appears as a subproblem in models for green logistics and machine learning, and it has to be solved repeatedly. The model belongs to the class of computationally challenging convex mixed-integer nonlinear programs. We develop a combinatorial algorithm to solve this model exactly. Our algorithm is faster than the algorithm that currently has the best theoretical complexity in the literature on an extensive set of test instances. The efficiency of our algorithm derives from the combination of an infeasibility-guided divide-and-conquer framework and a scaling-based greedy subroutine for resource allocation with submodular constraints. This paper also showcases the prevalent mismatch between the theoretical worst-case time complexity of an algorithm and its practical efficiency. We have offered some explanations of this mismatch through the perspectives of worst-case analysis, specially designed instances, and statistical metrics of numerical experiments. The implementation of our algorithm is available on an online repository.

Two critical yet frequently conflicting objectives for logistics and transportation service companies are improving customer satisfaction and reducing transportation cost. In particular, given a network of customer requests with preferred service times, it is very challenging to find vehicle routes and service schedules simultaneously that respect all operating constraints and minimize the total transportation and customers’ inconvenience costs. In this paper, we introduce the vehicle routing problem with time windows and convex node costs (VRPTW-CNC), in which we model each customer’s inconvenience cost as a convex function of the service start time at that customer. The VRPTW-CNC combines and extends both the standard vehicle routing problem with time windows and some previous results on the optimal service scheduling problem over a fixed route. We propose a branch-and-cut-and-price algorithm to solve the VRPTW-CNC with general convex inconvenience cost functions. To solve the pricing problem, our labeling algorithm only generates labels that possibly lead to optimal schedule times over a route, which significantly improves the effectiveness of pricing. Extensive computational results demonstrate the effectiveness of our approach.

The speed optimization problem over a path aims to find a set of speeds over each arc of the given path to minimize the total cost, while respecting the time-window constraint at each node and speed limits over each arc. In maritime transportation, the cost represents fuel cost or air pollutant emissions, so study of this problem has significant economic and environmental impacts. To accommodate different fuel and emission models, we allow the dependence of the cost on the speed to be a general continuously differentiable and strictly convex function, and different across the arcs. We develop an efficient algorithm that is able to solve instances of 1000 nodes in less than a second. The algorithm is 20 to 100 times faster than a general convex optimization solver on test instances and requires much less memory. The solutions found at intermediate steps of our algorithm also provide some insights to ship planners on how to balance the operating cost and service quality.

The pollution-routing problem (PRP) aims to determine a set of routes and speed over each leg of the routes simultaneously to minimize the total operational and environmental costs. A common approach to solve the PRP exactly is through speed discretization, i.e., assuming that speed over each arc is chosen from a prescribed set of values. In this paper, we keep speed as a continuous decision variable within an interval and propose new formulations for the PRP. In particular, we build two mixed-integer convex optimization models for the PRP, by employing tools from disjunctive convex programming. These are the first arc-based formulations for the PRP with continuous speed. We also derive several families of valid inequalities to further strengthen both models. We test the proposed formulations on benchmark instances. Some instances are solved to optimality for the first time.

We study a variant of the capacitated vehicle routing problem where the cost over each arc is defined as the product of the arc length and the weight of the vehicle when it traverses that arc. We propose two new mixed-integer linear programming formulations for the problem: an arc-load formulation and a set partitioning formulation based on q-routes with additional constraints. A family of cycle elimination constraints are derived for the arc-load formulation. We then compare the linear programming (LP) relaxations of these formulations with the two-index one-commodity flow formulation proposed in the literature. In particular, we show that the arc-load formulation with the new cycle elimination constraints gives the same LP bound as the set partitioning formulation based on 2-cycle-free q-routes, which is stronger than the LP bound given by the two-index one-commodity flow formulation. We propose a branch-and-cut algorithm for the arc-load formulation, and a branch-cut-and-price algorithm for the set partitioning formulation strengthened by additional constraints. Computational results on instances from the literature demonstrate that a significant improvement can be achieved by the branch-cut-and-price algorithm over other methods.

We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of $n\times n$ matrices and an $n$-dimensional vector, find a sequence of $K$ matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the $K$ matrices and the given vector. This simple problem has many applications in operations research and control, yet a moderate-sized instance is challenging to solve to optimality for state-of-the-art optimization software. We propose a simple exact algorithm for this problem. Our algorithm runs in polynomial time when the given set of matrices has the oligo-vertex property, a concept we introduce in this paper for a finite set of matrices. We derive several sufficient conditions for a set of matrices to have the oligo-vertex property. Numerical results demonstrate the clear advantage of our algorithm in solving large-sized instances of the problem over one state-of-the-art global optimization solver. We also propose several open questions on the oligo-vertex property and discuss its potential connection with the finiteness property of a set of matrices, which may be of independent interest.

The minimum concave cost network flow problem (MCCNFP) is NP-hard, but efficient polynomial-time algorithms exist for some special cases such as the uncapacitated lot-sizing problem and many of its variants. We study the MCCNFP over a grid network with a general nonnegative separable concave cost function. We show that this problem is polynomially solvable when all sources are in the first echelon and all sinks are in two echelons, and when there is a single source but many sinks in multiple echelons. The polynomiality argument relies on a combination of a particular dynamic programming formulation and an investigation of the extreme points of the underlying flow polyhedron. We derive an analytical formula for the inflow into any node in an extreme point solution, which generalizes a result of Zangwill (Manag Sci 14(7):429---450, 1968) for the multi-echelon lot-sizing problem.

Over the past decade, several targeted therapies (e.g. imatinib, dasatinib, nilotinib) have been developed to treat Chronic Myeloid Leukemia (CML). Despite an initial response to therapy, drug resistance remains a problem for some CML patients. Recent studies have shown that resistance mutations that preexist treatment can be detected in a substantial number of patients, and that this may be associated with eventual treatment failure. One proposed method to extend treatment efficacy is to use a combination of multiple targeted therapies. However, the design of such combination therapies (timing, sequence, etc.) remains an open challenge. In this work we mathematically model the dynamics of CML response to combination therapy and analyze the impact of combination treatment schedules on treatment efficacy in patients with preexisting resistance. We then propose an optimization problem to find the best schedule of multiple therapies based on the evolution of CML according to our ordinary differential equation model. This resulting optimization problem is nontrivial due to the presence of ordinary different equation constraints and integer variables. Our model also incorporates drug toxicity constraints by tracking the dynamics of patient neutrophil counts in response to therapy. We determine optimal combination strategies that maximize time until treatment failure on hypothetical patients, using parameters estimated from clinical data in the literature., Author Summary Targeted therapy using imatinib, nilotinib or dasatinib has become standard treatment for chronicle myeloid leukemia. A minority of patients, however, fail to respond to treatment or relapse due to drug resistance. One primary driving factor of drug resistance are point mutations within the driving oncogene. Laboratory studies have shown that different leukemic mutants respond differently to different drugs, so a promising way to improve treatment efficacy is to combine multiple targeted therapies. We build a mathematical model to predict the dynamics of different leukemic mutants with imatinib, nilotinib and dasatinib, and employ optimization techniques to find the best treatment schedule of combining the three drugs sequentially. Our study shows that the optimally designed combination therapy is more effective at controlling the leukemic cell burden than any monotherapy under a wide range of scenarios. The structure of the optimal schedule depends heavily on the mutant types present, growth kinetics of leukemic cells and drug toxicity parameters. Our methodology is an important step towards the design of personalized optimal therapeutic schedules for chronicle myeloid leukemia.

We study the minimum-concave-cost flow problem on a two-dimensional grid. We characterize the computational complexity of this problem based on the number of rows and columns of the grid, the number of different capacities over all arcs, and the location of sources and sinks. The concave cost over each arc is assumed to be evaluated through an oracle machine, i.e., the oracle machine returns the cost over an arc in a single computational step, given the flow value and the arc index. We propose an algorithm whose running time is polynomial in the number of columns of the grid, for the following cases: (1) the grid has a constant number of rows, a constant number of different capacities over all arcs, and sources and sinks in at most two rows; (2) the grid has two rows and a constant number of different capacities over all arcs connecting rows; (3) the grid has a constant number of rows and all sources in one row, with infinite capacity over each arc. These are presumably the most general polynomially solvable cases, since we show the problem becomes NP-hard when any condition in these cases is removed. Our results apply to abundant variants and generalizations of the dynamic lot sizing model, and answer several questions raised in serial supply chain optimization.

The sell or hold problem (SHP) is to sell k out of n indivisible assets over two stages, with known first-stage prices and random second-stage prices, to maximize the total expected revenue. We show that SHP is NP-hard when the second-stage prices are realized as a finite set of scenarios. We show that SHP is polynomially solvable when the number of scenarios in the second stage is constant. A max { 1 / 2 , k / n } -approximation algorithm is presented for the scenario-based SHP.

We provide a probabilistic comparison of split and type 1 triangle cuts for mixed-integer programs with two rows and two integer variables in terms of cut coefficients and volume cutoff. Under a specific probabilistic model of the problem parameters, we show that for the above measure, the probability that a split cut is better than a type 1 triangle cut is higher than the probability that a type 1 triangle cut is better than a split cut.

Parameter estimation for chaotic systems is an important issue in nonlinear science and has attracted increasing interests from various research fields, which could be essentially formulated as a multi-dimensional optimization problem. As a novel evolutionary computation technique, particle swarm optimization (PSO) has attracted much attention and wide applications, owing to its simple concept, easy implementation and quick convergence. However, to the best of our knowledge, there is no published work on PSO for estimating parameters of chaotic systems. In this paper, a PSO approach is applied to estimate the parameters of Lorenz system. Numerical simulation and the comparisons demonstrate the effectiveness and robustness of PSO. Moreover, the effect of population size on the optimization performances is investigated as well.

During the past decade, hybrid algorithms combining evolutionary computation and constraint-handling techniques have shown to be effective to solve constrained optimization problems. For constrained optimization, the penalty function method has been regarded as one of the most popular constraint-handling technique so far, whereas its drawback lies in the determination of suitable penalty factors, which greatly weakens the efficiency of the method. As a novel population-based algorithm, particle swarm optimization (PSO) has gained wide applications in a variety of fields, especially for unconstrained optimization problems. In this paper, a hybrid PSO (HPSO) with a feasibility-based rule is proposed to solve constrained optimization problems. In contrast to the penalty function method, the rule requires no additional parameters and can guide the swarm to the feasible region quickly. In addition, to avoid the premature convergence, simulated annealing (SA) is applied to the best solution of the swarm to help the algorithm escape from local optima. Simulation and comparisons based on several well-studied benchmarks demonstrate the effectiveness, efficiency and robustness of the proposed HPSO. Moreover, the effects of several crucial parameters on the performance of the HPSO are studied as well.

Many practical problems can be formulated as constrained optimization problems. Due to the simple concept and easy implementation, the penalty function method has been one of the most common techniques to handle constraints. However, the performance of this technique greatly relies on the setting of penalty factors, which are usually determined by manual trial and error, and the suitable penalty factors are often problem-dependent and difficult to set. In this paper, a differential evolution approach based on a co-evolution mechanism, named CDE, is proposed to solve the constrained problems. First, a special penalty function is designed to handle the constraints. Second, a co-evolution model is presented and differential evolution (DE) is employed to perform evolutionary search in spaces of both solutions and penalty factors. Thus, the solutions and penalty factors evolve interactively and self-adaptively, and both the satisfactory solutions and suitable penalty factors can be obtained simultaneously. Simulation results based on several benchmark functions and three well-known constrained design problems as well as comparisons with some existed methods demonstrate the effectiveness, efficiency and robustness of the proposed method.

Many engineering design problems can be formulated as constrained optimization problems. So far, penalty function methods have been the most popular methods for constrained optimization due to their simplicity and easy implementation. However, it is often not easy to set suitable penalty factors or to design adaptive mechanism. By employing the notion of co-evolution to adapt penalty factors, this paper proposes a co-evolutionary particle swarm optimization approach (CPSO) for constrained optimization problems, where PSO is applied with two kinds of swarms for evolutionary exploration and exploitation in spaces of both solutions and penalty factors. The proposed CPSO is population based and easy to implement in parallel. Especially, penalty factors also evolve using PSO in a self-tuning way. Simulation results based on well-known constrained engineering design problems demonstrate the effectiveness, efficiency and robustness on initial populations of the proposed method. Moreover, the CPSO obtains some solutions better than those previously reported in the literature.

How to balance the objective and constraints is always the key point of solving constrained optimization problems. This paper proposes a hybrid differential evolution with double populations (HDEDP) to handle it. HDEDP uses a two-population mechanism to decouple constraints from objective function: one population evolves by differential evolution only according to either objective function or constraint, while the other stores feasible solutions which are used to repair some infeasible solutions in the former population. Thus, this technique allows objective function and constraints to be treated separately with little costs involved in the maintenance of the double population. In addition, to enhance the exploitation ability, simplex method (SM) is applied as a local search method to the best feasible solution of the first population. Simulation results based on three well-known engineering design problems as well as comparisons with some existed methods demonstrate the effectiveness, efficiency and robustness of the proposed method.

Penalty function methods have been the most popular methods for nonlinear constrained optimization due to their simplicity and easy implementation. However, it is often not easy to set suitable penalty factors or to design adaptive mechanisms. By employing the notion of co-evolution to adapt penalty factors, we present a co-evolutionary particle swarm optimization approach (CPSO) for nonlinear constrained optimization problems, where PSO is applied with two kinds of swarms for evolutionary exploration and exploitation in spaces of both solutions and penalty factors. To enhance the performance of our proposed algorithm, three improvement strategies are proposed. The proposed algorithm is population-based and easy to implement in parallel, in which the penalty factors to evolve in a self-tuning way. Simulation results based on three famous engineering constrained optimization problems demonstrate the effectiveness, efficiency and robustness of the proposed enhanced CPSO (ECPSO).