Questions tagged [optimization]

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

Filter by
Sorted by
Tagged with
1
vote
1answer
2k views

Automatic seat assignment algorithm [closed]

I am looking for articles relating to algorithms that deal with automatic selection of seating assignment. I need an algorithm (preferably more than one) that can automatically select a seating place ...
1
vote
0answers
128 views

In multi criteria decision making, what notions are there to get a subset of the Pareto set?

In the multi criteria decision making context, let $\mathcal{A}$ be a set of alternatives or choices. Each alternative $\alpha\in \mathcal{A}$ is a vector of $k$ criteria $\alpha=(v_1,v_2,\dots,v_k)$. ...
3
votes
0answers
378 views

Trying to understand the Gilmore-Lawler lower bound

For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
2
votes
0answers
593 views

Practical Application of Kadane algorithm

Kadane Algorithm is used to solve the maximum subarray problem which in simpler terms is to find the highest possible value of a continuous sub array in an array. One often cited application of ...
1
vote
0answers
50 views

Assigning packages to different points by minimizing distance: is this a known problem?

Imagine we have N houses, on a standard euclidean 2D plane. We also have N "packages", each of which contains several "objects" of different types, let's call them A, B, C, etc. We know the content of ...
12
votes
1answer
4k views

Choosing a subset to maximize the minimum distance between points

I have a set of points $C$, and I have the distance between each point $D(P_i,P_j)$. These distances are euclidean but the points are actually in a feature space. From the $C$ points I want to choose ...
3
votes
1answer
548 views

Mutation and crossover operations in discrete differential evolutionary operations?

I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of ...
0
votes
1answer
102 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $...
4
votes
2answers
572 views

Suboptimal Solution for a combinatorial problem

I have a cost function $f(X)=\|\hat{X}-X\|_2$ to minimize which depends on a $s\times s$ matrix $X$ where $\hat{X}$ is given and $\|X\|_2=\big(\sum_{i,j}x_{ij}^2\big)^{1/2} $. This matrix $X$ is ...
1
vote
5answers
4k views

What is the best way to index lookups on a 2D array of integers that is boundless in x and y?

Lets say you have a data model that consists of a 2D grid of integer points. This grid is sparsely populated and boundless in x and y (up to the max of a 32-bit integer). What is the best way to ...
3
votes
1answer
613 views

Boat riddle as a combinatorial optimization problem?

I remember a riddle about a bunch of people on a river bank, and a boat with limited capacity (lets say the boat can transport 2 people at a time). There are various relations between the people like: ...
3
votes
1answer
272 views

Bin packing problem or not?

Suppose I have $N$ bins and $M$ items as depicted in the figure below (3 bins and 3 items): Suppose that every bin has unit capacity and the weights of the items depend on the bins used. I want to ...
6
votes
0answers
119 views

Boolean formula that agrees with most truth assignments

Let $X_1,\dots,X_n$ be $n$ boolean variables. I have an unknown predicate $P(X_1,\dots,X_n)$ on these boolean variables. Of course, I can view the predicate as a function $f_P : \{0,1\}^n \to \{0,1\}...
-1
votes
1answer
356 views

Balanced partition problem for N =< 60 and very large sums

I was proposed (in school) to develop an approach to solve optimally the balanced partition problem. I tried the pseudo-linear algorithms but SUM is very large (~1M) and so O(S*N) cant run under ...
3
votes
2answers
748 views

minimizing the summed cardinality of set unions

this optimization problem, I am working on, is kind of making me crazy. ;) Given is a list o of sets (with finite cardinality) of strictly positive integer values (...
3
votes
1answer
5k views

How to stop genetic algorithm population converging to a single value

I've written a genetic algorithm (GA) that solves a 7-dimensional optimisation problem. All seven variables are floating point numbers. The problem is that the entire population seems to converge to ...
2
votes
1answer
821 views

Genetic algorithm fitness function [closed]

I'm trying to write some little code (POC for the selection/mutation operators) that uses a genetic algorithm to solve a global maximum for a function. ...
2
votes
1answer
895 views

How can we minimize the total distance of cross pairs in an array

Suppose we had 2 arrays of the same size with positive numbers and we wanted to pair up the elements of each array such that the total difference between the pairs is minimized. The first thought ...
7
votes
2answers
4k views

What is the no free lunch theorem?

I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser ...
3
votes
1answer
108 views

Finding largest subset that matches moments

I would like to find a algorithm that will do the following: Given two sets $A, B \subseteq \mathbb{R}$, where $|B| > |A|$, find the largest subset $C \subseteq B$, such that: $\qquad |\...
1
vote
1answer
352 views

Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?

The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in ...
1
vote
0answers
86 views

Applications of algorithms to stock trading analysis

There is a new Quantitative Finance SE site. However, I am interested in asking the "CS crowd": What are some interesting key references or surveys on applying algorithms to stock trading analysis?...
4
votes
2answers
176 views

Genetic algorithm: What is the expected number of strings that are explored?

My question concerns genetic algorithm searching along bit strings. Given: $N$ = population size $l$ = length of bit strings $p_c$ = probability that a single crossover occur (double crossover never ...
3
votes
0answers
83 views

What functions are easy to optimize?

Say I have variables $w_1, \dots w_n, h_1, \dots h_m \in \mathbb R$, constants $W, H$, functions $f_1, \dots f_k : \mathbb R\times\mathbb R\to\mathbb R$ from some family $F$ and for each function $f_i$...
1
vote
1answer
2k views

Efficiently pick a largest set of non-intersecting line segments

Given a set of line segments, how do we identify a subset of maximal cardinality where all line segments are pairwise non-intersecting? Brute force we would get $2^n$ sets to check where $n$ is the ...
7
votes
3answers
14k views

How does the 3-opt algorithm for TSP work?

I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers ...
1
vote
1answer
329 views

Local search: Problem with neighborhood definition

I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U_k$ be the neighborhood ...
2
votes
2answers
2k views

Weighted Set covering problem with a fixed number of colors

I have a set of elements U = {1, 2, .... , n} and a set S of k sets whose union form the whole universe. Each of these sets is associated with a cost. I have a fixed number of colors, C = {1 , 2, ... ...
2
votes
3answers
407 views

A genetic algorithm modified for a specific problem

I have a problem whose solution can be written as a binary string with a given length $N$, where $N$ is a given parameter. Standard GA works well on this problem. From runs of small values $N$, I ...
2
votes
1answer
185 views

Using approximations to optimization problems for threshold problems

Many problems in computer science come in two flavors: Optimization problem: "Find an object with the largest size". Decision problem: "Given $n$, find an object with a size of at least $n$, or reply ...
1
vote
0answers
67 views

Quadratic programming problem involving permutation matrices [closed]

Does anyone know a good algorithm for quickly finding an approximate solution to the following problem? Given two square matrices $A$ and $B$, minimize $\| P A P^\top - B \|$ over all permutation ...
1
vote
1answer
92 views

optimal placement of fixed length items on a given length

I have got some equipment of standard lengths, say: equipment_lengths = {60, 48, 36, 29} that I have to place on a given length of, say 100. I have to place this equipment so as to minimize ...
3
votes
1answer
443 views

Find subset with minimal sum under constraints

Let $M$ be a finite set of even cardinality. Define $C=\{\{a,b\}:a,b \in M, a \neq b\}$ the set of all pairs over $M$. Let $w:C \rightarrow \mathbb{R}^+_0$ be a function. Now find $C' \subset C$ with ...
5
votes
1answer
2k views

Is the set partitioning problem NP-complete?

I know that the set partitioning problem defined like this: Given $$S = \left\{ x_1, \ldots x_n \right\}$$ find $S_1$ and $S_2$ such that $S_1 \cap S_2 = \emptyset$, $S_1 \cup S_2 = S$ and $\...
6
votes
1answer
60 views

Is there a more up-to-date / wider-scope version of the 'Compendium of NP Optimization Problems'

When I was studying Comp Sci, we had Garey & Johnson as a course textbook, with a large collection of NP-Complete problems. But by that time you could also have a look at the Compendium of NP ...
3
votes
1answer
640 views

Clarification on Tabu Search

I need some help in understanding the 'Tabu Search' Algorithm. (Wikipedia) I miss a simple explanation to Tabu Search. Anyway, I'm trying to refer to available resources and build an understanding. ...
3
votes
1answer
148 views

“Unusual” coupling between a decision problem and a corresponding optimization problem

There seems to usually be a tight connection between decision problems and (corresponding) optimization problems in general. However, is this always the case? Are there examples where the typical "...
55
votes
8answers
169k views

What is a the fastest sorting algorithm for an array of integers?

I have come across many sorting algorithms during my high school studies. However, I never know which is the fastest (for a random array of integers). So my questions are: Which is the fastest ...
11
votes
1answer
11k views

Variant of the knapsack problem

How would you approach the knapsack problem in a dynamic programming situation if you now have to limit the number of item in the knapsack by a constant $p$ ? This is the same problem (max weight of $...
6
votes
1answer
154 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 ...
1
vote
0answers
255 views

NTP: synchronisation of time between two machines for ICMP timestamping

Some guy on the internet recommends using the same ntp server when it is required to troubleshoot asymmetric routes through ICMP, and it's somewhat important to have synchronised time between the two ...
10
votes
1answer
519 views

Easy way to prove that this algorithm eventually terminates

Introduction and notations: Here is a new and simple version of my algorithm which seems to terminates (according to my experiments), and now I would like to prove that. Let the notation $x_i \in \...
0
votes
1answer
119 views

Scheduling optimization problem in theta(n)

I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to ...
1
vote
0answers
1k views

Maximum subset intersection problem

Given N finite subsets of the finite universe set E, it is necessary to find the intersection which contains maxumum number of subsets. Let call this problem MSI (Maximum Subset Intersetion). Firstly ...
5
votes
0answers
39 views

Does it make sense to examine the dual of a feasbility problem?

Consider a standard feasibility problem. The goal is to examine the state of feasible solutions for $Ax=b$ to find an $x$ that satisfies some property. Does the dual of this problem tell us anything ...
10
votes
3answers
647 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 ...
3
votes
3answers
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 ...
5
votes
1answer
2k views

Variation of Set Cover Problem: Finding a maximum-sized collection of disjoint set-covers

I have the following problem, which seems to be similar to Set Cover. We are given a set $U$ of elements (the universe, e.g., $U=\{1,2,3,4,5\}$). We're also given a set $S$ of subsets (e.g., $S=\{\{1\...
5
votes
3answers
15k views

Artificial Intelligence: Condition for BFS being optimal

It is said in the book Artificial Intelligence: A Modern Approach for finding a solution on a tree using BFS that: breadth-first search is optimal if the path cost is a nondecreasing function of ...
12
votes
2answers
1k views

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

What is the complexity of $\text{MIN-2-XOR-SAT}$ and $\text{MAX-2-XOR-SAT}$? Are they in P? Are they NP-hard? To formalize this more precisely, let $$\Phi\left(\mathbf x\right)={\huge\wedge}_{i}^{...