Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

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

0
votes
0answers
23 views

Is Travelling salesman problem with dikstra's algorithm the optimal solution?

I've tried solving the travelling salesman problem using dynamic programming and Dijkstra's algorithm to find the optimal solution in Dijkstra's algorithm is always correct(in the test data i used). ...
4
votes
3answers
858 views

Assign m agents to N points by minimizing the total distance

Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final ...
0
votes
1answer
21 views

Algorithm for selecting a sample that's as spread out as possible?

I have a large database of data with dates. There are large gaps and large chunks of data without gaps. I want to get a sample of this data such that the dates are as spread out as possible (i.e. as ...
1
vote
0answers
11 views

Can graph execution be better optimized than imperative programs?

I've been reading about Google's TensorFlow, and the way it represents calculations with graphs that are then executed by an engine. While the concept is interesting, I would like to understand why ...
0
votes
0answers
10 views

Is there an algorithm that provides the highest possible “sum of satisfaction” for a priority based distribution problem?

Let's say we have n (e.g. 6) children and a box of candy. The box has k (e.g. 8) different flavours, and m (e.g. 4) piece of candy in each flavour. This question is specifically about the cases where ...
1
vote
1answer
84 views

combinatoric grouping optimization problem based on time interval overlap, weight constraint, and distance minimization

Let each element be an individual. Consider that an individual is defined such that each individual has a time range, weight, and location. The goal is to group together individuals whose time ranges ...
0
votes
0answers
9 views

Is it possible to compute a whole convolution layer at once?

I have an input of 32×32×3 and I want to feed it to a convolution layer that output 32×32×16 feature maps. I know that I can compute a single feature map as matrix multiplication. But my question is, ...
1
vote
0answers
23 views

Find the m-th largest separation

The m-th largest number in a list of n numbers can be found in $O(m \log n)$ using a max-heap. This avoids sorting. Suppose I'm interested not in the actual numbers, but separation between adjacent ...
1
vote
0answers
18 views

Is there an algorithm to partition a set of points into two disjoint polytopes far away from the origin?

Suppose I have a finite point set $P = \{p_1,\ldots, p_K\} \subset \mathbb R^D$ and all $p_i \ne 0$. What I would like to do is partition $P$ into two disjoint pieces $A \cup B$ so the convex hulls $\...
0
votes
2answers
1k views

Longest path in DAG or finding DAG diameter

A directed acyclic graph (DAG), is a directed graph with no directed cycles. That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
1
vote
0answers
19 views

Goemans' Extended Formulation of the Permutahedron And Comparator Networks that are not Sorting Networks

I am interested in using Michel Goemans' extended formulation first developed for the permutahedron to study comparator networks that are not sorting networks. In his paper "Smallest Compact ...
2
votes
1answer
35 views

Why is the usual simulated annealing algorithm using a Boltzmann probability?

I've coded a personal version for the simulated annealing problem, and I was wondering why, (other than by analogy to the physics), the probability is $$ p = e^{-\dfrac{\Delta \text{length}}{T}}$$ (...
0
votes
3answers
64 views

Find the cheapest combination of raw foods that fulfill nutritional requirements

I am starting a raw food diet and would like to properly plan it, and thus, would like to create a program that takes a list of available raw food, and finds the best combination of foods (multiples ...
-2
votes
2answers
681 views

Divide N sticks among M boys as evenly as possible

There are $N$ sticks. $N$ is an integer greater than zero. I want to divide it among $M$ boys. $M$ is also a positive integer. Partitioning $N$ among $M$ is easy, but doing it as evenly as possible is ...
3
votes
2answers
58 views

League and Divisions problem (np-hard)

There is a League. And there are Divisions, that are the disjoint subsets of this League. There are n teams (unique locations are given, let's assume it's x and y for simplicity reasons). Every team ...
1
vote
0answers
8 views

How to improve convergence to an equilibrium value, & damp oscillation?

I am developing a program which seeks strategies for the players A, B in any of a family of simple 2-player gambling-games. The program iterates, using a genetic algorithm to determine, from the ...
1
vote
3answers
51 views

How to solve the optimization of bin packing using the decision version

Let us say the optimization version of the bin packing problem asks you to give a packing using the fewest bins possible and the decision version asks if it is possible to pack the bins into $k$ bins. ...
5
votes
3answers
2k views

Min cost max flow in bipartite run time

I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost). For the sake ...
22
votes
5answers
3k views

Why do low fitness individuals have a chance to survive to the next generation?

I am currently reading and watching about genetic algorithm and I find it very interesting (I haven't had the chance to study it while I was at the university). I understand that mutations are based ...
0
votes
0answers
11 views

How to model a path in optimization problem? [closed]

I have a question about modeling an optimization problem. I want to model all links in a path between two nodes in a network or graph. Most of the papers are based on modeling only one link between ...
2
votes
0answers
17 views

How to solve cubing, batching, and routing problem together?

I am working on an order picking project, which requires to cube the items into several totes in a trolley, then batching the totes, followed by parallel aisle picking/routing. The input data has ...
0
votes
0answers
33 views

What kind of standard deviation must be used in optimization algorithms?

I would like to ask about the standard deviation of objective function value. There are two types of standard deviations: Population standard deviation Sample standard deviation In metaheuristic ...
2
votes
2answers
44 views

Maximize number of museums visited in a day

Given a list of museums, their opening hours and time needed to visit each, make a schedule such that a tourist visits maximal number of museums in a given day. Suppose that no time is needed in ...
2
votes
0answers
24 views

Linear order minimizing weighted distance from special element

Let's say I have a set of beads, $b_0,\dots,b_n$, and let $b_0$ be the 'special bead'. I want to lay out the beads on a string to minimize the total cost, defined as $\sum_{i=1}^n w_i \cdot d(b_0, b_i)...
1
vote
0answers
65 views

Approporiate algorithm for a graph theory problem

So I have recently ran into a graph theory problem and was unable to find a matching algorithm for the problem or reword the problem to match some existing algorithm. The problem is pretty ...
2
votes
1answer
27 views

Linear programming IFF with equality constrain

Is it possible to write the following logical constrain in linear programming? Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is $y=...
3
votes
4answers
105 views

How to select best k fractions out of n fractions (k<=n) so as to have (numerator sum / denominator sum) maximum?

For example, given 4 fractions $\frac{4}{2}$, $\frac{2}{3}$, $\frac{1}{2}$, $\frac{10}{20}$, I have to select 3 fractions out of these 4 so that the value of $\frac{\text{numerator sum}}{\text{...
2
votes
3answers
1k views

Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k

I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
0
votes
1answer
59 views

Distribute repeated values into bins as evenly as possible

Preface I've asked a very similar question already on stack overflow in a different wording and gotten a working answer under the assumption that there is no way to go through all possibilities (np-...
2
votes
0answers
52 views

What algorithm should I use for the following problem?

Suppose we have 2 lists: List $G$: the goal, contains goal items each comes with a specific amount, $$G = \{i_1 \times Item_1, i_2 \times Item_2,\dots, i_n \times Item_n\}$$ List $I$: a list that ...
9
votes
6answers
3k views

Are there variations of the regular runtimes of the Big-O-Notation?

There are multiple $O$-Notations, like $O(n)$ or $O(n^2)$ and so on. I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log n^2)$, or if those are mathematically ...
0
votes
1answer
89 views

Modified Knapsack Problem

I have a problem with the following optimisation problem: In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, ...
2
votes
0answers
14 views

IPM vs Projected Subgradient Descent

In my theoretical CS class, we learned about Interior Point Methods for convex optimization, but it seems that projected subgradient descent works equally well for constrained optimization. What are ...
1
vote
0answers
81 views

MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?

A paper was published recently in Science where the authors minimized the following function: $$E_{\text{Ising}}(s) = -\dfrac{1}{2} \Sigma_{i=1}^{N} \Sigma_{j=1}^{N} J_{i,j} s_i s_j,$$ where $...
1
vote
1answer
5k views

Minimizing cost of bus travel

A man has to travel for given number of days by bus. He can buy either: $1$ day ticket for $2Rs$ (valid for 1 day) $7$ days ticket for $7Rs$ (valid for 7 consecutive days) $30$ days ticket for $25Rs$ ...
0
votes
1answer
220 views

Can this “double pop” Heapsort variation speed up sorting on average?

For classic Heapsort (in this example using a maxheap), only the root node is extracted (popped) at each iteration and the last element in the heap is swapped into its place and then the tree is "re-...
0
votes
1answer
521 views

Using 2-opt Heuristic in a Genetic Algorithm for TSP

I read few papers while trying to find some better approachs to solve the TSP (Traveling salesman problem) as close to the optimal solution as possible. I implemented a Improved Greedy Crossover (...
4
votes
2answers
205 views

Greedy Algorithms for Non-monotone Submodular Maximization with Cardinality Constraints

Does any approximation algorithm exist for maximization non-monotone submodular functions that might have negative values or be unbounded below? Fact 1: For monotone submodular functions, Nemhauser, ...
2
votes
2answers
245 views

Scheduling / Queuing jobs with multiple different workers

I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system. Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue). ...
0
votes
0answers
31 views

Minimization with asymptotic assumption

Given the function $g(n,m)=\min\Big\{f(a,b)+f(n-a,c)+f(n,m-bc)\Big|\\a,b,c\ \ \text{with} \left\{\begin{matrix} a,\ b,\ n-a,\ c,\ m-bc \geq 0 \\ b\leq a! \\ c\leq (n-a)! \\ \end{matrix}\right. \Big\}...
2
votes
0answers
38 views

Algorithm to optimize redistribution of balls amongst urns [closed]

Here is the question: Say we have k urns with 1 ball in each urn. At each iteration of the game, I pick one urn and redistribute its contents amongst other urns and each urn can receive at most one ...
2
votes
0answers
33 views

Optimizing AVL Tree operations for sequential data

I'm working on an implementation of a data structure that needs a tree-like data structure for accelerating look-ups. The interesting part about this data structure is that the only operations on the ...
4
votes
1answer
309 views

Vehicle Routing Problem with multiple deliveries?

I have a problem that can be reduced to the following: There are three types of objects, A, B, and C. For each type of object, there are a number of "pickup points" and a number of "delivery points"...
1
vote
1answer
2k views

A variant of coin change problem

Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in ...
0
votes
1answer
149 views

Finding longest prefix of a given string in set of strings that satisies some property

I have a set of strings, lets call them RULES. I have a function F which given 2 strings deterministically returns boolean value. Given one string, lets call it QUERY, what is the fastest way to find ...
1
vote
1answer
61 views

Dynamic programming - maximize sum of functions subject to constraints

Let $\{f_i\}_{i=1}^{k}:[0,k]\to\mathbb{Z}$. The problem: Maximize the sum $\sum_{i=1}^{k}f_i(x_i)$ subject to the the constraint $\sum_{i=1}^{k}x_i\le k$ I think we suppose to come up with a ...
0
votes
1answer
35 views

Loop Invariant Code Motion - am I missing something?

I've been implementing LICM for a project, and came upon a strange observation. Let's say we have a loop int i = 10; while (i > 0) { a = 2; i--; } ...
0
votes
1answer
43 views

MILP problem NP-hard proof [closed]

Since a MILP problem is not necessarily NP hard. How could I demonstrate that a MILP problem is actually NP hard? There exists some smart and easy method to do that? Many thanks!
1
vote
1answer
182 views

Solve Max 3 color problem using 3 color decision problem

I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute ...
1
vote
1answer
102 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...