Authors:
Yajie Tian,
Nobuo Sannomiya,
Yuedong Xu,
Volume: 1, Page 4606 Paper number 1588
Abstract:
In this paper, a tabu search algorithm with a new neighborhood technique
is proposed for solving flow shop scheduling problems. An idea obtained
from a simulation study on the adaptive behavior of a fish school is
used to determine the neighborhood search technique. The cooperation
and the diversity of job data are defined for describing the data structure
by using the given information. According to the definitions, job data
are classified into four kinds, and two kinds of them are treated in
this paper. A large number of computational experiments are carried
out for investigating how to assign the local effort and the global
effort under a limited search time. The result shows that the allocation
of the local and the global effort depends on the job data characteristics,
such as cooperation and diversity. The validity of the tabu search
algorithm is examined by comparing it with the genetic algorithm. It
is found that the proposed tabu search algorithm has better convergence
and much sho
Authors:
Pablo A. Parrilo,
Volume: 1, Page 4612 Paper number 1777
Abstract:
In this paper, we present improved versions of the standard semidefinite
relaxation for quadratic programming, that underlies many important
results in robustness analysis and combinatorial optimization. It
is shown that the proposed polynomial time convex conditions are
at least as strong as the standard ones, and usually better, but
at a higher computational cost. Several applications of the new
relaxations are provided, including less conservative upper bounds
for the structured singular value µ and enhanced solutions for
the MAX CUT graph partitioning problem.
Authors:
Helene Frankowska,
Richard B. Vinter,
Volume: 1, Page 4618 Paper number 1093
Abstract:
In this paper, the value function for an optimal control problem with
endpoint and state constraints is characterized as the unique lower
semicontinuous generalized solution of the Hamilton-Jacobi Equation.
This is achieved under a constraint qualification (CQ) concerning the
interaction of the state and dynamic constraints. The novelty of the
results reported here is partly the nature of (CQ) and partly the proof
techniques employed, which are based on new estimates of the distance
of the set of state trajectories satisfying a state constraint from
a given trajectory which violates the constraint.
Authors:
Pablo A. Parrilo,
Volume: 1, Page 4624 Paper number 1747
Abstract:
The verification of matrix copositivity is a well known computationally
hard problem, with many applications in continuous and combinatorial
optimization. In this paper, we present a hierarchy of semidefinite
programming based sufficient conditions for a real matrix to be copositive.
These conditions are obtained through the use of a sum of squares
decomposition for multivariable forms. As can be expected, there
is a tradeoff between conservativeness of the tests and the corresponding
computational requirements. The proposed tests are shown to be exact
for a certain family of extreme copositive matrices.
|