Combinatorial Optimization

Food Regulated Pareto Multi-Species: a new ACO Approach for the Multi-objective Shortest Path Problem

Categories Meta Heuristics, Multi-Criteria Optimization, Transportation Tags , , , ,

The use of metaheuristics in Multi-objective Combinatorial Optimization, particularly Ant Colony Optimization (ACO), has grown recently. This paper proposes an approach where multi-species ants compete for food resources. Each species has its own search strategy and do not access pheromone information of other species. As in nature, successful ant populations are allowed to grow, whereas … Read more

On Minimizing the Energy Consumption of an Electrical Vehicle

Categories Applications - Science and Engineering, Branch and Cut Algorithms, Control Applications Tags , , , , ,

The electrical vehicle energy management can be expressed as a Bang-Bang optimal control problem. In this work, we discuss on a new formulation and about the way to approximate this optimal control problem of Bang-Bang type via a discretization technique associated with a Branch-and-Bound algorithm. The problem that we focus on, is the minimization of … Read more

On Minimizing the Energy Consumption of an Electrical Vehicle

Categories Applications - Science and Engineering, Branch and Cut Algorithms, Control Applications Tags , , , , ,

The electrical vehicle energy management can be expressed as a Bang-Bang optimal control problem. In this work, we discuss on a new formulation and about the way to approximate this optimal control problem of Bang-Bang type via a discretization technique associated with a Branch-and-Bound algorithm. The problem that we focus on, is the minimization of … Read more

A biased random-key genetic algorithm for job-shop scheduling

Categories Combinatorial Optimization, Meta Heuristics, Scheduling Tags

This paper presents a local search, based on a new neighborhood for the job-shop scheduling problem, and its application within a biased random-key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based … Read more

A biased random-key genetic algorithm for job-shop scheduling

Categories Combinatorial Optimization, Meta Heuristics, Scheduling Tags

This paper presents a local search, based on a new neighborhood for the job-shop scheduling problem, and its application within a biased random-key genetic algorithm. Schedules are constructed by decoding the chromosome supplied by the genetic algorithm with a procedure that generates active schedules. After an initial schedule is obtained, a local search heuristic, based … Read more

On implementation of local search and genetic algorithm techniques for some combinatorial optimization problems

Categories Approximation Algorithms, Combinatorial Optimization, Meta Heuristics Tags , , , , ,

In this paper we propose the approach to solving several combinatorial optimization problems using local search and genetic algorithm techniques. Initially this approach was developed in purpose to overcome some difficulties inhibiting the application of above-mentioned techniques to the problems of the Questionnaire Theory. But when the algorithms were developed it became clear that them … Read more

On the impact of symmetry-breaking constraints on spatial Branch-and-Bound for circle packing in a square

Categories Combinatorial Optimization, Global Optimization, Nonlinear Optimization Tags , , , ,

We study the problem of packing equal circles in a square from the mathematical programming point of view. We discuss different formulations, we analyse formulation symmetries, we propose some symmetry breaking constraints and show that not only do they tighten the convex relaxation bound, but they also ease the task of local NLP solution algorithms … Read more

Efficient Solutions for the Far From Most String Problem

Categories Basic Sciences Applications, Combinatorial Optimization, Meta Heuristics Tags , , , ,

Computational molecular biology has emerged as one of the most exciting interdisciplinary fields. It has currently benefited from concepts and theoretical results obtained by different scientific research communities, including genetics, biochemistry, and computer science. In the past few years it has been shown that a large number of molecular biology problems can be formulated as … Read more

Job-Shop Scheduling in a Body Shop

Categories Approximation Algorithms, Scheduling Tags , , ,

We study a generalized job-shop problem called the body shop scheduling problem (bssp). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. bssp corresponds to a job-shop problem where the operations of a job have to follow … Read more