# Questions tagged [optimization]

Questions about problems that entail selecting the best element from some set of available alternatives, and methods to solve them.

107 questions
Filter by
Sorted by
Tagged with
9k views

2k views

### Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...
1k views

### How to find the maximal set of elements $S$ of an array such that every element in $S$ is greater than or equal to the cardinality of $S$?

I have an algorithmic problem. Given an array (or a set) $T$ of $n$ nonnegative integers. Find the maximal set $S$ of $T$ such that for all $a\in S$, $a\geqslant |S|$. For example: If $T$=[1, 3, 4, ...
685 views

### Wiring Length Minimization

My Problem is like this: I have a physical layout represented as a graph. The Nodes represents hooks/ducts where a wire can anchor and Edges are the possible connection between 2 nodes from where ...
4k views

### How to identify when to use Genetic Algorithm/Programming

I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem. TSP is basically a permutation/combination problem, and I can understand how GA helps ...
5k views

For my case I have starting point and several cities. I want the shortest route to visit all cities without returning starting point. I have read several TSP algorithm and all include the return a ...
435 views

### Dynamic Shortest Path with Linear Programming

Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps. There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is ...
2k views

### Maximum degree of concurrency in task dependency graphs

I've been researching ways of modeling and executing tasks which are dependent on each other (but in an acyclic way) and came up with task graphs. But the question that's bugging me is how can I find ...
1k views

### Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...
653 views

### Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map): positively weighted undirected sparse with about 100 nodes My ...
899 views

### Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$. Note that the length of ...
2k views

### How to find the shortest path from some vertex in set $S$ to set $S'$

If i have a graph $G=(V,E)$, a subset of vertices $S \subset V$ and a second set of vertices $S' \subset (V\setminus S)$, what is the best way to find the shortest path connecting the two sets? That ...
166 views

### Which potential function does this algorithm minimize or maximize?

Considering two sets $A, B$ containing some $p$-dimensional points $x \in \mathbb{R}^p$. Let $d_x^S = \min_{x' \in S \setminus \{x\}} \lVert \mathbf{x} - \mathbf{x'} \rVert$ denote the Euclidean ...
97 views

### Location Selection Algorithm in Solar Engineering

This is a practical problem in energy generation with heliostats. We have a number of heliostats basically forming the shape of a doughnut. The facility needs to deploy hubs on those heliostats. One ...
696 views

### Dividing a weighted planar graph into $k$ subgraphs with balanced weight

I've been looking for an algorithm which divides an undirected, weighted, planar and simple graph into $k$ disjoint subgraphs. Here, the graph is sparse, $k$ is fixed, and there are no negative edge ...