The problem (LFP) of finding a feasible solution to a given linear
semi-infinite system arises in different contexts. This paper provides
an empirical comparative study of relaxation algorithms for (LFP).
In this study we consider, together with the classical algorithm, imple-
mented with different values of the fixed parameter (the step size), a
new relaxation algorithm with random parameter which outperforms
the classical one in most test problems whatever fixed parameter is
taken. This new algorithm converges geometrically to a feasible so-
lution under mild conditions. The relaxation algorithms under com-
parison have been implemented using the Extended Cutting Angle
Method (ECAM) for solving the global optimization subproblems.
In order to study voting situations when voters can also abstain and the output is binary, i.e., either approval or rejection, a new extended model of voting rule was defined. Accordingly, indices of power, in particular Banzhaf’s index, were considered. In this paper we argue that in this context a power index should be a pair of real numbers, since this better highlights the power of a voter in two different cases, i.e., her being crucial when switching from being in favor to abstain, and from abstain to be contrary. We also provide an axiomatization for both indices, and from this a characterization as well of the standard Banzhaf index (the sum of the former two) is obtained. Some examples are provided to show how the indices behave.
The final publication is available at Springer via http://dx.doi.org/10.1007/s10479-016-2124-5
This paper is a twofold contribution. First, it contributes to the problem of enumerating some classes of simple games and in particular provides the number of weighted games with minimum and the number of weighted games for the dual class as well. Second, we focus on the special case of bipartite complete games with minimum, and we compare and rank these games according to the behavior of some efficient power indices of players of type 1 (or of type 2). The main result of this second part establishes all allowable rankings of these games when the Shapley-Shubik power index is used on players of type 1.
This paper describes our work on applying novel techniques based on propositional satisfiability (SAT) solvers and optimizers to the Curriculum-based Course Timetabling problem.; Out of 32 standard benchmark instances derived from the Second International Timetabling Competition held in 2007, our techniques yield the best known solutions for 21 of them (19 of them being optimal), improving the previously best known solutions for 9.; In addition, we obtain 18 new lower bounds for this benchmark set by applying a new full (Weighted) Partial MaxSAT approach of the Curriculum-based Course Timetabling problem.
We study the Set Covering Problem with uncertain costs. For each cost coefficient, only an interval estimate is known, and it is assumed that each coefficient can take on any value from the corresponding uncertainty interval, regardless of the values taken by other coefficients. It is required to find a robust deviation (also called minmax regret) solution. For this strongly NP-hard problem, we present and compare computationally three exact algorithms, where two of them are based on Benders decomposition and one uses Benders cuts in the context of a Branch-and-Cut approach, and several heuristic methods, including a scenario-based heuristic, a Genetic Algorithm, and a Hybrid Algorithm that uses a version of Benders decomposition within a Genetic Algorithm framework.
We investigate voting systems with two classes of voters, for which there is a hierarchy giving each member of the stronger class more influence or important than each member of the weaker class. We deduce for voting systems one important counting fact that allows determining how many of them are for a given number of voters. In fact, the number of these systems follows a Fibonacci sequence with a smooth polynomial variation on the number of voters. On the other hand, we classify by means of some parameters which of these systems are weighted. This result allows us to state an asymptotic conjecture which is opposed to what occurs for symmetric games.
This paper focuses on the Vehicle Routing Problem with Stochastic Demands (VRPSD) and discusses how Parallel and Distributed Computing Systems can be employed to efficiently solve the VRPSD. Our approach deals with uncertainty in the customer demands by considering safety stocks, i.e. when designing the routes, part of the vehicle capacity is reserved to deal with potential emergency situations caused by unexpected demands. Thus, for a given VRPSD instance, our algorithm considers different levels of safety stocks. For each of these levels, a different scenario is defined. Then, the algorithm solves each scenario by integrating Monte Carlo simulation inside a heuristic-randomization process. This way, expected variable costs due to route failures can be naturally estimated even when customers’ demands follow a non-normal probability distribution. Use of parallelization strategies is then considered to run multiple instances of the algorithm in a concurrent way. The resulting concurrent solutions are then compared and the one with the minimum total costs is selected. Two numerical experiments allow analyzing the algorithm’s performance under different parallelization schemas.
A basic problem in the theory of simple games and other fields is to study whether
a simple game (Boolean function) is weighted (linearly separable). A second related problem
consists in studying whether a weighted game has a minimum integer realization. In this
paper we simultaneously analyze both problems by using linear programming.
For less than 9 voters, we find that there are 154 weighted games without minimum
integer realization, but all of them have minimum normalized realization. Isbell in 1958 was
the first to find a weighted game without a minimum normalized realization, he needed to
consider 12 voters to construct a game with such a property. The main result of this work
proves the existence of weighted games with this property with less than 12 voters
Production flexibility is essential for industrial companies that have to deal with seasonal demand. Human resources are one of the main sources of flexibility. Annualising working hours (i.e., the possibility of irregularly distributing the total number of working hours over the course of a year) is a tool that provides organisations with flexibility; it enables a firm to adapt production capacity to fluctuations in demand. However, it can involve a worsening of the staff working conditions. To take this into account, the planning and scheduling of working time should comply with constraints derived from the law or from a collective bargaining agreement. Thus, new and more difficult working-time and production planning and scheduling problems are arising. This paper proposes two mixed-integer linear program models for solving the problem of planning the production, the working hours and the holiday weeks of the members of a human team operating in a multi-product process in which products are perishable, demand can be deferred and temporary workers are hired to stand in for employees. The results of a computational experiment are presented.