The multiperiod assignment problem: A multicommodity network flow model and specialized branch and bound algorithm

The multiperiod assignment problem, a specialization of the three dimensional assignment problem, is an optimization model that describes the situation of assigning people to activities, or jobs over time. We consider the most general case which has both a cost of assigning a person to an activity in each time period, and a cost of transferring the person from one activity in each period to another activity in the next period. In general, the number of time periods need not equal the number of persons and activities. We present a new formulation of the multiperiod assignment problem, that of an integer, multicommodity network flow model. The special structure of the model allows us to find a good feasible solution relatively quickly by a shortest path heuristic algorithm. We discuss a new branch and bound algorithm for solving this problem to optimality. The subproblems of the branch and bound tree are evaluated by solving a set of special-structured, shortest path problems all of which can be solved in order n²T time, where n is the number of persons and activities, and T is the number of time periods. We present computational tests of the algorithm on moderately sized problems.     

An O(T log T) Algorithm for the Dynamic Lot Size Problem with Limited Storage and Linear Costs

In this paper the dynamic lot size problem with time varying storage capacities and linear costs is addressed. Like in the uncapacitated version, this problem can be formulated as a network flow problem. Considering the properties of the underlying network, we devise an O(T log T) greedy algorithm to obtain optimal policies and we report computational results for randomly generated problems.     

A mixed integer linear programming formulation of the optimal mean/Value-at-Risk portfolio problem

In this paper, we consider an extension of the Markovitz model, in which the variance has been replaced with the Value-at-Risk. So a new portfolio optimization problem is formulated. We showed that the model leads to an NP-hard problem, but if the number of past observation T or the number of assets K are low, e.g. fixed to a constant, polynomial time algorithms exist. Furthermore, we showed that the problem can be formulated as an integer programming instance. When K and T are large and α^VaR is small—as common in financial practice—the computational results show that the problem can be solved in a reasonable amount of time.     

An efficient approach for solving the lot-sizing problem with time-varying storage capacities

We address the dynamic lot size problem assuming time-varying storage capacities. The planning horizon is divided into T periods and stockouts are not allowed. Moreover, for each period, we consider a setup cost, a holding unit cost and a production/ordering unit cost, which can vary through the planning horizon. Although this model can be solved using O(T³) algorithms already introduced in the specialized literature, we show that under this cost structure an optimal solution can be obtained in O(T log T) time. In addition, we show that when production/ordering unit costs are assumed to be constant (i.e., the Wagner–Whitin case), there exists an optimal plan satisfying the Zero Inventory Ordering (ZIO) property.     

Uncapacitated two-level lot-sizing

For the uncapacitated two-level production-in-series T period lot-sizing model, a dynamic program with running time O(T²logT) and a compact and tight extended formulation with O(T³) variables and O(T²) equality constraints are presented. Limited computational comparisons of various formulations of two-level production/transportation problems with multiple clients are reported.     

Economic optimization in a fixed sequence of unreliable inspections

Given a fixed sequence of unreliable inspection operations with known costs and inspection error probabilities of two types (classifying good items as defective and vice versa), we develop a model for selecting the set of inspections that should be activated in order to minimize expected total costs (inspection and penalties). We present an efficient branch and bound algorithm for finding the optimal solution, and two variations of a greedy heuristic that can be applied jointly to provide very good solutions at a O(n²) computational complexity. The conclusions are backed by a factorial experiment that included 1440 problem instances.     

Safe scheduling: Setting due dates in single-machine problems

We consider single-machine stochastic scheduling models with due dates as decisions. In addition to showing how to satisfy given service-level requirements, we examine variations of a model in which the tightness of due-dates conflicts with the desire to minimize tardiness. We show that a general form of the trade-off includes the stochastic E/T model and gives rise to a challenging scheduling problem. We present heuristic solution methods based on static and dynamic sorting procedures. Our computational evidence identifies a static heuristic that routinely produces good solutions and a dynamic rule that is nearly always optimal. The dynamic sorting procedure is also asymptotically optimal, meaning that it can be recommended for problems of any size.     

An O(T) algorithm for the capacitated lot sizing problem with minimum order quantities

This paper explores a single-item capacitated lot sizing problem with minimum order quantity, which plays the role of minor set-up cost. We work out the necessary and sufficient solvability conditions and apply the general dynamic programming technique to develop an O(T³) exact algorithm that is based on the concept of minimal sub-problems. An investigation of the properties of the optimal solution structure allows us to construct explicit solutions to the obtained sub-problems and prove their optimality. In this way, we reduce the complexity of the algorithm considerably and confirm its efficiency in an extensive computational study.     

A modified greedy analysis pursuit algorithm for the cosparse analysis model

In the past decade, the sparse representation synthesis model has been deeply researched and widely applied in signal processing. Recently, a cosparse analysis model has been introduced as an interesting alternative to the sparse representation synthesis model. The sparse synthesis model pay attention to non-zero elements in a representation vector x, while the cosparse analysis model focuses on zero elements in the analysis representation vector Ωx. This paper mainly considers the problem of the cosparse analysis model. Based on the greedy analysis pursuit algorithm, by constructing an adaptive weighted matrix W _k?1, we propose a modified greedy analysis pursuit algorithm for the sparse recovery problem when the signal obeys the cosparse model. Using a weighted matrix, we fill the gap between greedy algorithm and relaxation techniques. The standard analysis shows that our algorithm is convergent. We estimate the error bound for solving the cosparse analysis model, and then the presented simulations demonstrate the advantage of the proposed method for the cosparse inverse problem.     

Using Lagrangian dual information to generate degree constrained spanning trees

In this paper, a Lagrangian-based heuristic is proposed for the degree constrained minimum spanning tree problem. The heuristic uses Lagrangian relaxation information to guide the construction of feasible solutions to the problem. The scheme operates, within a Lagrangian relaxation framework, with calls to a greedy construction heuristic, followed by a heuristic improvement procedure. A look ahead infeasibility prevention mechanism, introduced into the greedy heuristic, allowed us to solve instances of the problem where some of the vertices are restricted to having degrees 1 or 2. Furthermore, in order to cut down on CPU time, a restricted version of the original problem is formulated and used to generate feasible solutions. Extensive computational experiments were conducted and indicate that the proposed heuristic is competitive with the best heuristics and metaheuristics in the literature.     

Bound reduction using pairs of linear inequalities

We describe a procedure to reduce variable bounds in mixed integer nonlinear programming (MINLP) as well as mixed integer linear programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction procedure extends the feasibility based bound reduction technique on linear functions, used in MINLP and MILP. However, it can also be seen as a special case of optimality based bound reduction, a method to infer variable bounds from an LP relaxation of the problem. For an LP relaxation with m constraints and n variables, there are O(m ²) pairs of constraints, and a naïve implementation of our bound reduction scheme has complexity O(n ³) for each pair. Therefore, its overall complexity O(m ² n ³) can be prohibitive for relatively large problems. We have developed a more efficient procedure that has complexity O(m ² n ²), and embedded it in two Open-Source solvers: one for MINLP and one for MILP. We provide computational results which substantiate the usefulness of this bound reduction technique for several instances.     

Moderate deviations and hypothesis testing for signal detection problem

We use moderate deviations to study the signal detection problem for a diffusion model.We establish a moderate deviation principle for the log-likelihood function of the diffusion model.Then applying the moderate deviation estimates to hypothesis testing for signal detection problem we give a decision region such that its error probability of the second kind tends to zero with faster speed than the error probability of the first kind when the error probability of the first kind is approximated by e-αr(T),where α>0,r(T)=o(T) and r(T) →∞ as the observation time T goes to infinity.     

A polynomial time algorithm to solve the single-item capacitated lot sizing problem with minimum order quantities and concave costs

This paper deals with the single-item capacitated lot sizing problem with concave production and storage costs, and minimum order quantity (CLSP-MOQ). In this problem, a demand must be satisfied at each period t over a planning horizon of T periods. This demand can be satisfied from the stock or by a production at the same period. When a production is made at period t, the produced quantity must be greater to than a minimum order quantity (L) and lesser than the production capacity (U). To solve this problem optimally, a polynomial time algorithm in O(T⁵) is proposed and it is computationally tested on various instances.     

A Lagrangian relaxation approach to the edge-weighted clique problem

The b-clique polytope CPⁿ_b is the convex hull of the node and edge incidence vectors of all subcliques of size at most b of a complete graph on n nodes. Including the Boolean quadric polytope QPⁿ=CPⁿ_n as a special case and being closely related to the quadratic knapsack polytope, it has received considerable attention in the literature. In particular, the max-cut problem is equivalent with optimizing a linear function over CPⁿ_n. The problem of optimizing linear functions over CPⁿ_b has so far been approached via heuristic combinatorial algorithms and cutting-plane methods.We study the structure of CPⁿ_b in further detail and present a new computational approach to the linear optimization problem based on the idea of integrating cutting planes into a Lagrangian relaxation of an integer programming problem that Balas and Christofides had suggested for the traveling salesman problem. In particular, we show that the separation problem for tree inequalities becomes polynomial in our Lagrangian framework. Finally, computational results are presented.     

Capacitated dynamic lot-sizing problem with delivery/production time windows

In this paper we generalize the classical dynamic lot-sizing problem by considering production capacity constraints as well as delivery and/or production time windows. Utilizing an untraditional decomposition principle, we develop a polynomial-time algorithm for computing an optimal solution for the problem under the assumption of non-speculative costs. The proposed solution methodology is based on a dynamic programming algorithm that runs in O(nT⁴) time, where n is the number of demands and T is the length of the planning horizon.     

On the construction of bodies of constant width containing a given set

We discuss the problem of sparse representation of domains in ℝ ^d . We demonstrate how the recently developed general theory of greedy approximation in Banach spaces can be used in this problem. The use of greedy approximation has two important advantages: (1) it works for an arbitrary dictionary of sets used for sparse representation and (2) the method of approximation does not depend on smoothness properties of the domains and automatically provides a near optimal rate of approximation for domains with different smoothness properties. We also give some lower estimates of the approximation error and discuss a specific greedy algorithm for approximation of convex domains in ℝ².     

Minimum flow problem on network flows with time-varying bounds

In this paper, we consider the minimum flow problem on network flows in which the lower arc capacities vary with time. We will show that this problem for set {0, 1, … , T} of time points can be solved by at most n minimum flow computations, by combining of preflow-pull algorithm and reoptimization techniques (no matter how many values of T are given). Running time of the presented algorithm is O(n²m).     

A modified greedy algorithm for dispersively weighted 3-set cover

The set cover problem is that of computing a minimum weight subfamily F^′, given a family F of weighted subsets of a base set U, such that every element of U is covered by some subset in F^′. The k-set cover problem is a variant in which every subset is of size at most k. It has been long known that the problem can be approximated within a factor of by the greedy heuristic, but no better bound has been shown except for the case of unweighted subsets. In this paper we consider approximation of a restricted version of the weighted 3-set cover problem, as a first step towards better approximation of general k-set cover problem, where any two distinct subset costs differ by a multiplicative factor of at least 2. It will be shown, via LP duality, that an improved approximation bound of H(3)-1/6 can be attained, when the greedy heuristic is suitably modified for this case. A key to our algorithm design and analysis is the Gallai-Edmonds structure theorem for maximum matchings.     

A mathematical program to refine gene regulatory networks

In this paper, we propose a methodology for making sense of large, multiple time-series data sets arising in expression analysis. Specifically, we present a mathematical model to release a reduced and coherent regulatory system given a putative regulatory network. We give two equivalent formulations of the problem and prove that the problem is NP-complete. For solving large scale instances we implemented an Ant Colony Optimization procedure. A computational analysis on randomly generated test instances validates the proposed algorithm and the computations on real data concerning Saccharomyces cerevisiae show the practicability of the proposed methodology.     

Shelling Coxeter-like complexes and sorting on trees

In their work on ‘Coxeter-like complexes’, Babson and Reiner introduced a simplicial complex ΔT associated to each tree T on n nodes, generalizing chessboard complexes and type A Coxeter complexes. They conjectured that ΔT is (n−b−1)-connected when the tree has b leaves. We provide a shelling for the (n−b)-skeleton of ΔT, thereby proving this conjecture. In the process, we introduce notions of weak order and inversion functions on the labellings of a tree T which imply shellability of ΔT, and we construct such inversion functions for a large enough class of trees to deduce the aforementioned conjecture and also recover the shellability of chessboard complexes Mm,n with n?2m−1. We also prove that the existence or nonexistence of an inversion function for a fixed tree governs which networks with a tree structure admit greedy sorting algorithms by inversion elimination and provide an inversion function for trees where each vertex has capacity at least its degree minus one.