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
3
votes
1answer
285 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 ...
7
votes
0answers
126 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\}...
3
votes
1answer
1k 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 ...
2
votes
1answer
842 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. ...
7
votes
2answers
5k 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 ...
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 ...
2
votes
1answer
208 views

Neighbourhood in local search metaheuristic

I cannot seem to find an answer to this question with Google, so I am going to ask here: is it required for a good neighbourhood function that it in principle (i. e. by recursively considering all ...
1
vote
0answers
90 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
181 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 ...
2
votes
3answers
429 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 ...
3
votes
0answers
84 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$...
10
votes
3answers
694 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 ...
10
votes
2answers
353 views

How do I classify my emulator input optimization problem, and with which algorithm should I approach it?

Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) ...
1
vote
1answer
344 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 ...
1
vote
0answers
70 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
99 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 ...
7
votes
1answer
63 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
449 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 ...
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 ...
1
vote
0answers
538 views

Streaming Knapsack Problem

I want to implement efficiently "streaming Knapsack" problem in java. The problem is I have a stream input of integer data coming continuously for example -1, 2, 9, 5, 5, 11, 1 -3,... The question ...
3
votes
1answer
150 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 "...
3
votes
1answer
692 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. ...
10
votes
1answer
863 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 \...
6
votes
1answer
169 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
264 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 ...
0
votes
1answer
121 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
2k 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 ...
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\...
-1
votes
1answer
42 views

Is a non-perfect improvement and optimisation?

In real word problems, the influence of multiple not perfectly known factors results in using heuristics instead of mathemacial solutions that calculates a perfect value from only precisly defined ...
2
votes
0answers
643 views

Other greedy choices to solve activity selection problem

I have been studying about activity-selection-problem and the solution of greedy choice I came across is to select the activity that finishes in the earliest among the present activities. But surely ...
4
votes
1answer
68 views

Congestion Game with Varying Price

I molded my problem as the following game (it is a congestion game with varying price): $N$ players share resources $E$, $S_i$ is the strategy space of player $i$ which is in $2^E$ (where $2^E$ is ...
4
votes
1answer
186 views

Formulating a linear program s.t. only extreme point solutions are found

If there are many solutions to a linear program s.t. the objective function is minimized/maximized (= optimal solutions are on an edge of the polytope), how can I force an LP solver to find only an ...
4
votes
4answers
614 views

Using a computer algebra system to optimize mathematical expressions

This is something I've been wondering for years. Software like Mathematica is great at manipulating expressions into simplified, factorized, and other forms. I'm wondering if there's a way, ...
4
votes
2answers
99 views

Solution for a combinatorial minimization problem

Let's say we have an inequality, $p \le {a \choose b}$ where $p$ is a fixed constant and $a, b$ are variables. The problem is that, we are trying to find the minimum $a$ with respect to the inequality ...
3
votes
0answers
157 views

How to compute an optimally cost-effective cache strategy?

I am looking for advice in the following optimization problem. I have a website (system) that receives database updates later returned in queries made to the same system. In order to speed up the ...
1
vote
0answers
666 views

Minimizing concave function with a linear constraint

The problem can be formulated as: $\min f(\textbf{x})=\sum_{i=1}^{n} \prod_{j \in N(i)}(1-F(x_i))$ s.t. $\sum_{i=1}^n x_i \leq B$ $N(i)$ is a set of i. And $F_{x_i}$ can be any function with range ...
2
votes
1answer
85 views

Calculate the number of elements after multiplying/adding two polynomials

Suppose I have two polynomials $f(x)$ and $g(x)$ and I somehow represent their coefficients. I have a couple of ways to hold a polynomial depending on how many significant coefficients the polynomial ...
4
votes
2answers
2k views

Scheduling algorithm to minimize maximum deadline overshoot in pre-emptive scheduler

Suppose there are $n$ tasks, which need to be scheduled by a pre-emptive scheduler. Each task $T_i$ has a deadline $d_i$ and a total processing time $t_i$ associated with it. Now, all $n$ tasks are ...
13
votes
1answer
337 views

Finding maximal factorization of regular languages

Let language $\mathcal{L} \subseteq \Sigma^*$ be regular. A factorization of $\mathcal{L}$ is a maximal pair $(X,Y)$ of sets of words with $X \cdot Y \subseteq \mathcal{L}$ $X \neq \emptyset \neq Y$...
3
votes
0answers
607 views

Motion planning using second order Bézier curves

I'm trying to find an algorithm for a motion planning problem. I have $N$ points, $P_1$ to $P_N$, in $k$-dimensional cartesian space, defining $N-1$ segments. The problem is about constructing the ...
11
votes
4answers
1k views

Finding exact corner solutions to linear programming using interior point methods

The simplex algorithm walks greedily on the corners of a polytope to find the optimal solution to the linear programming problem. As a result, the answer is always a corner of the polytope. Interior ...
3
votes
1answer
593 views

A variant of job assignment (scheduling) problem with variable time span

The problem is a scheduling problem with n jobs and k machines. Each job i can be started at any time, but its duration is not exactly known except a time span interval. For example, a job may take ...
2
votes
1answer
36 views

Optimal coverage of a $D$-dimensional grid with small blocks

I have a $D$-dimensional grid with the size $(N_1, \ldots, N_D)$, where $N_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m_1, \ldots, m_D)...
0
votes
1answer
117 views

Algorithm to maximize function of subsets

Let's say I have a finite set S with, say, 1000 elements, and a function f on some subset of S. Suppose that f has no useful mathematical properties. What algorithm is most relevant in finding the ...
0
votes
1answer
2k views

Find disjoint contiguous sub-arrays in better than $\mathcal O(n^2)$

Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum. The sub-arrays should not overlap and it can not be ...
23
votes
2answers
2k views

Collectively pay the bill problem

There are $n$ people at a table. The $i$th person has to pay $p_i$ dollars. Some people don't have the right bills to pay exactly $p_i$, so they come up with the following algorithm. First, ...
3
votes
1answer
301 views

Is this NP-hard: min-weight n-clique in a complete n-partite graph

I have a complete $n$-partite graph, where each partite set has $n$ vertices (yes it's also $n$), so the graph has $n^2$ vertices in total. My problem is to find a minimum weight $n$-clique in the ...
2
votes
1answer
98 views

Multicommodity circulation formulation

On the circulation problem page on wikipedia, the multicommodity circulation problem formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation ...
4
votes
2answers
250 views

Recommended Reading for non-CS undergraduate student doing a research Project on Travelling Salesman Problem

I am an undergraduate student in Industrial Engineering. I have taken the topic of Travelling Salesman Problem as a Research Project for my final year. More specifically, I am focusing on Convex Hulls ...