A decomposition approach for a new test-scenario in complex problem solving

Over the last years, psychological research has increasingly used computer-supported tests, especially in the analysis of complex human decision making and problem solving. The approach is to use computer-based test scenarios and to evaluate the performance of participants and correlate it to certain attributes, such as the participant's capacity to regulate emotions. However, two important questions can only be answered with the help of modern optimization methodology. The first one considers an analysis of the exact situations and decisions that led to a bad or good overall performance of test persons. The second important question concerns performance, as the choices made by humans can only be compared to one another, but not to the optimal solution, as it is unknown in general.Additionally, these test-scenarios have usually been defined on a trial-and-error basis, until certain characteristics became apparent. The more complex models become, the more likely it is that unforeseen and unwanted characteristics emerge in studies. To overcome this important problem, we propose to use mathematical optimization methodology not only as an analysis and training tool, but also in the design stage of the complex problem scenario.We present a novel test scenario, the IWR Tailorshop, with functional relations and model parameters that have been formulated based on optimization results. We also present a tailored decomposition approach to solve the resulting mixed-integer nonlinear programs with nonconvex relaxations and show some promising results of this approach.     

A Benders decomposition approach for a distribution network design problem with consolidation and capacity considerations

We develop a model for a strategic freight-forwarding network design problem in which the design decisions involve the locations and capacities of consolidation and deconsolidation centers, and capacities on linehaul linkages as well as the shipment routes from origins to destinations through centers. We devise a solution approach based on Benders decomposition and conduct a computational study that illustrates the efficiency and the effectiveness of the approach.     

An approach for solving a modification of the extended rapid transit network design problem

In this paper we deal with a slight modification of the extended rapid transit network design problem to allow circular lines. A two-stage approach is proposed for solving this problem. In the first stage, an integer model is solved for selecting the stations to be constructed and the links between them. It drastically reduces the dimension of a modification of a 0–1 model given in the literature to adapt it to our problem. In the second stage, the line design problem is solved by means of a procedure that assigns each selected link to exactly one line under certain constraints. We report some computational experiments that show that our approach also produces a drastic reduction on the computational effort required for solving the modification of the 0–1 model given in the literature.     

Hybrid meta-heuristic algorithms for solving network design problem

Network design problem has been, and is, an important problem in transportation. Following an earlier effort in designing a meta-heuristic search technique by an ant system, this paper attempts to hybridize this concept with other meta-heuristic concepts such as genetic algorithm, simulated annealing, and tabu search. Seven hybrids have been devised and tested on the network of Sioux Falls. It has been observed that the hybrids are more effective to solve the network design problem than the base ant system. Application of the hybrid containing all four concepts on a real network of a city with over 2 million population has also proved to be more effective than the base network, in the sense of finding better solutions sooner.     

A decomposition method for solving multicommodity network equilibria

We consider the numerical aspect of the multicommodity network equilibrium problem proposed by Rockafellar in 1995. Our method relies on the flexible monotone operator splitting framework recently proposed by Combettes and Eckstein.     

Modelling and solving the perfect edge domination problem

Optimization Letters - A formulation is proposed for the perfect edge domination problem and some exact algorithms based on it are designed and tested. So far, perfect edge domination has been...     

A matheuristic approach for solving a home health care problem

We deal with a Home Health Care Problem (HHCP) which objective consists in constructing the optimal routes and rosters for the health care staffs. The challenge lies in combining aspects of vehicle routing and staff rostering which are two well known hard combinatorial optimization problems. To solve this problem, we initially propose an integer linear programming formulation (ILP) and we tested this model on small instances. To deal with larger instances we develop a matheuristic based on the decomposition of the ILP formulation into two problems. The first one is a set partitioning like problem and it represents the rostering part. The second problem consists in the routing part. This latter is equivalent to a Multi-depot Traveling Salesman Problem with Time Windows (MTSPTW).     

A branch-and-price approach to the feeder network design problem

In this paper we consider the problem of designing a container liner shipping feeder network. The designer has to choose which port to serve during many rotations that start and end at a central hub. Many operational characteristics are considered, such as variable leg-by-leg speeds and cargo transit times. Realistic instances are generated from the LinerLib benchmark suite. The problem is solved with a branch-and-price algorithm, which can solve most instances to optimality within one hour. The results also provide insights on the cost structure and desirable features of optimal routes. These insights were obtained by means of an analysis where scenarios are generated varying internal and external conditions, such as fuel costs and port demands.     

An improved Benders decomposition applied to a multi-layer network design problem

Benders decomposition has been widely used for solving network design problems. In this paper, we use a branch-and-cut algorithm to improve the separation procedure of Gabrel et al. and Knippel et al. for capacitated network design. We detail experiments on bi-layer networks, comparing with Knippel’s previous results.     

A multi-heuristic approach for solving the pre-marshalling problem

Minimizing the number of reshuffling operations at maritime container terminals incorporates the pre-marshalling problem (PMP) as an important problem. Based on an analysis of existing solution approaches we develop new heuristics utilizing specific properties of problem instances of the PMP. We show that the heuristic performance is highly dependent on these properties. We introduce a new method that exploits a greedy heuristic of four stages, where for each of these stages several different heuristics may be applied. Instead of using randomization to improve the performance of the heuristic, we repetitively generate a number of solutions by using a combination of different heuristics for each stage. In doing so, only a small number of solutions is generated for which we intend that they do not have undesirable properties, contrary to the case when simple randomization is used. Our experiments show that such a deterministic algorithm significantly outperforms the original nondeterministic method. The improvement is twofold, both in the quality of found solutions, and in the computational effort.     

A new approach for solving the Stokes problem

In this paper, a new approach for finding the approximate solution of the Stokes problem is introduced. In this method the problem is transformed to an equivalent optimization problem. Then, by considering it as a distributed parameter control system, the theory of measure is used to approximate the velocity functions by piecewise linear functions. Then, the approximate values of pressure are obtained by a finite difference scheme.     

A neural network for solving a convex quadratic bilevel programming problem

A neural network is proposed for solving a convex quadratic bilevel programming problem. Based on Lyapunov and LaSalle theories, we prove strictly an important theoretical result that, for an arbitrary initial point, the trajectory of the proposed network does converge to the equilibrium, which corresponds to the optimal solution of a convex quadratic bilevel programming problem. Numerical simulation results show that the proposed neural network is feasible and efficient for a convex quadratic bilevel programming problem.     

Branch-and-bound decomposition approach for solving quasiconvex-concave programs

A class of branch-and-bound methods is proposed for minimizing a quasiconvex-concave function subject to convex and quasiconvex-concave inequality constraints. Several important special cases where the subproblems involved by the bounding-and-branching operations can be solved quite effectively include certain d.c. programming problems, indefinite quadratic programming with one negative eigenvalue, affine multiplicative problems, and fractional multiplicative optimization.This research was accomplished while the second author was a Fellow of the Alexander von Humboldt Foundation at the University of Trier, Trier, Germany.     

New bounds for the broadcast domination number of a graph

A dominating broadcast on a graph G = (V, E) is a function f: V → {0, 1, ..., diam G} such that f(v) ≤ e(v) (the eccentricity of v) for all v ∈ V and such that each vertex is within distance f(v) from a vertex v with f(v) > 0. The cost of a broadcast f is σ(f) = Σ _v∈V f(v), and the broadcast number λ _b (G) is the minimum cost of a dominating broadcast. A set X ? V(G) is said to be irredundant if each x ∈ X dominates a vertex y that is not dominated by any other vertex in X; possibly y = x. The irredundance number ir (G) is the cardinality of a smallest maximal irredundant set of G. We prove the bound λ_b(G) ≤ 3 ir(G)/2 for any graph G and show that equality is possible for all even values of ir (G). We also consider broadcast domination as an integer programming problem, the dual of which provides a lower bound for λ_b.     

A genetic algorithm approach on tree-like telecommunication network design problem

In the context of telecommunication networks, the network terminals involve certain constraints that are either related with the performance of the corresponding network or with the availability of some classes of devices. In this paper, we discuss a tree-like telecommunication network design problem with the constraint limiting the number of terminals. First, this problem is formulated as a leaf-constrained minimum spanning tree (lc-MST). Then we develop a tree-based genetic representation to encode the candidate solutions of the lc-MST problem. Compared with the existing heuristic algorithm, the numerical results show the high effectiveness of the proposed GA approach on this problem.     

An approach for solving of a moving boundary problem

In this paper we shall study moving boundary problems, and we introduce an approach for solving a wide range of them by using calculus of variations and optimization. First, we transform the problem equivalently into an optimal control problem by defining an objective function and artificial control functions. By using measure theory, the new problem is modified into one consisting of the minimization of a linear functional over a set of Radon measures; then we obtain an optimal measure which is then approximated by a finite combination of atomic measures and the problem converted to an infinite-dimensional linear programming. We approximate the infinite linear programming to a finite-dimensional linear programming. Then by using the solution of the latter problem we obtain an approximate solution for moving boundary function on specific time. Furthermore, we show the path of moving boundary from initial state to final state.     

A finite-element approach to solving a thermal conductivity problem for thick plates

A method is proposed for the numerical solution of a problem in the thermal conductivity a plate heated by a moving heat source, taking into account the dependence of the thermal properties of the material on temperature. A hypothesis of N. N. Rykalin concerning the state of the thermal field is adopted. The method is based on a spline variant of the finite-element method; this is based on the synthesis of parametrization and finite elements with splines. A FORTRAN algorithm is given for performing the method on an ES series computer.Translated from Matematichekie Metody i Fiziko-Mekhanicheskie Polya, No. 29, pp. 58–62, 1989.     

An approach for solving a fuzzy multiobjective programming problem

In this paper we present a new approach, based on the Nearest Interval Approximation Operator, for dealing with a multiobjective programming problem with fuzzy-valued objective functions.     

A DC programming approach for solving multicast network design problems via the Nesterov smoothing technique

This paper continues our recent effort in applying continuous optimization techniques to study optimal multicast communication networks modeled as bilevel hierarchical clustering problems. Given a finite number of nodes, we consider two different models of multicast networks by identifying a certain number of nodes as cluster centers, and at the same time, locating a particular node that serves as a total center so as to minimize the total transportation cost throughout the network. The fact that the cluster centers and the total center have to be among the given nodes makes these problems discrete optimization problems. Our approach is to reformulate the discrete problems as continuous ones and to apply Nesterov’s smoothing approximation techniques on the Minkowski gauges that are used as distance measures. This approach enables us to propose two implementable DCA-based algorithms for solving the problems. Numerical results and practical applications are provided to illustrate our approach.