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
0 votes
0 answers
8 views

Can I minimize a mysterious function by running a gradient decent on her neural net approximations? [closed]

A cross post from on AI StackExchange, and MathOverflow So I have this function let call her $F:[0,1]^n \rightarrow \mathbb{R}$ and say $10 \le n \le 100$. I want to find some $x_0 \in [0,1]^n$ such ...
0 votes
0 answers
6 views

Optimising for many points in a monotone function

I'm trying to optimise (to a certain precision) a monotonic function for many points (100+). I know a-priori that the function is continuous, with some parts zero derivative. I know that all points ...
0 votes
1 answer
21 views

swapping numbers in a list is equivalent to remove & reinsert?

Given some ordered list of $n$ items, I obviously have $n!$ possible arrangements. However, as a heuristic in some larger algorithm that needs to find the optimal order, I want to do some quick local ...
  • 111
2 votes
0 answers
18 views

How can we reduce the spatial complexity of intermediate indexes in relational databases at execution time?

In relational databases, what are the practical or theoretical ways to reduce the size and spatial complexity of intermediate indexes or tables* at execution time (so for example to reduce the size of ...
  • 21
0 votes
2 answers
41 views

Estimate which components to replace, to not only save electric energy but also improve the computer's performance

Faster CPUs solve the same computational problems in shorter time frames. The same applies to faster GPUs. Therefore, replacing with faster components can reduce the computer's power consumption. On ...
3 votes
0 answers
45 views

Approximation algorithm for minimising $x_i+y_i$ for monotonically increasing sequence $x_i$ and monotonically decreasing sequence $y_i$

Given sorted $0\leq x_1 \leq x_2 \leq ... \leq x_n$ and $y_1 \geq y_2 \geq ... \geq y_n \geq 0$ non negative integers accessible through oracles, with the additional constraints $x_{i+1}-x_i \leq 1$ ...
0 votes
2 answers
174 views

Combining fork() and algorithms

Today in my algorithms class, my professor explained how in divide and conquer algorithms we do things in "parallel" although I felt it was not exactly in parallel. Then I remembered from OS ...
0 votes
0 answers
35 views

Optimizing submodular approximation [closed]

Let $U$ be the ground set, let $f$ be a submodular function, and let $\hat f$ be another submodular function such that for every $A\subseteq U$, we have $|f(A)-\hat f(A)|\leq \epsilon$. Denote by $Z^\...
  • 199
2 votes
0 answers
28 views

Minimizing DPDA

Is there an efficient algorithm for minimizing a deterministic PDA in terms of states? Is it even computable? I know that it is not possible to minimize a PDA in general, but my question is about ...
1 vote
0 answers
17 views

Element in linear subspace with maximum number of zeros

Given a real matrix $M \in \mathbb{R}^{n \times m}$ and a vector $v \in \mathbb{R}^{n}$ I would like to find an element $x \in \mathbb{R}^m$ such that $v - Mx$ has maximum number of zeros. If the ...
  • 111
0 votes
0 answers
33 views

Proof of optimality (and correctness) of greedy algorithm

Unable to come up with a formal proof of optimality for algorithm A for the given problem. Have convinced myself that it is possible to execute some optimal schedule O in increasing order of the ...
  • 135
1 vote
1 answer
17 views

EvoPathfinding - Stuck in local optimal

I am using a Genetic Algorithm framework to solve a path-finding problem. Specifically, given the following 32x32 maze: ...
  • 111
3 votes
2 answers
69 views

Maximize enclosed area of given figures on 2d grid

I need to solve an optimization problem for a given set of polyominoes, for example the five Tetrominoes known from Tetris. The goal is to place each one of the figures on the 2d grid, so the area ...
  • 33
0 votes
0 answers
17 views

objective function to minimize the number of trucks?

I have a problem that consists of: there are a number of orders, each with a different weight and I also have several trucks, which also have different weights. The objective is to use as few trucks ...
0 votes
0 answers
25 views

optimization problem about capacitated vehicle routing problem

I have an optimization problem. The problem consists initially of the presence of several trucks, each one having different maximum capacities. There are also multiple customer orders, each with a ...
0 votes
2 answers
41 views

When should genetic algorithm's variation operators be specialized?

Genetic algorithm (GA) is general purpose metaheuristic often used in computational science, e.g. computational physics. However, some authors of computational physics software, e.g. [1], tend to ...
  • 3
0 votes
0 answers
62 views

Find a range of values to subset the rows to maximize the objective function

I have searched around for some time but couldn't find a similar example to my problem. It looks common enough that I would expect it to be solved. It lies between search and optimization/regression. ...
0 votes
0 answers
24 views

Black Box Optimization

I want to find the maximum possible value of an unknown function on a rectangle. What is the optimal method of doing this? Do I need to use simulated annealing?
1 vote
0 answers
31 views

Minimizing operations to reach a set of goal stack states

I'm trying to sort the elements of a set of "goal" stacks to minimize the number of pushes/pops to reach each state. The inputs and outputs can be some other structure rather than stacks, ...
  • 11
1 vote
1 answer
37 views

Are there adaptive algorithms/data structures for sparse and non sparse vectors?

A sparse 1D array of integers is commonly encoded as pairs of [index, value], which consumes 2 memory spots per value. A dense 1D array is commonly encoded as a linear array of values [value1, value2, ...
  • 131
0 votes
0 answers
24 views

Good resources on polyhedral compilation

I'm looking for good introductory resources (books, articles, notes, websites, videos, e.t.c.) on polyhedral compilation. I'm especially interested in applications related to deep learning / GPU ...
1 vote
1 answer
30 views

Find the placement of gates on 2D points that minimizes the total distance of all paths to be made

Suppose we have a 6 vertices graph. We also have 6 gates. Each gate is attributed a path. For example, Gate 'A' will have to go to 'B'- 'C' - 'D' and 'E' Gate 'B' will have to go to 'D' Gate 'C' will ...
  • 113
0 votes
0 answers
30 views

How much faster is Montgomery multiplication?

Montgomery multiplication is used to speed up the computation of modular products for large moduli, with respect to simpler techniques such as Barrett reduction or plain division. In practical ...
  • 121
1 vote
1 answer
34 views

Finding optimal combination with multiple constraints

I'm trying to find an optimal combination of players given certain constraints. There are ~300 players. 10 players has to be chosen in the combination. Each player has an assigned value. The goal is ...
  • 13
2 votes
1 answer
48 views

Efficiently remove intersections among a set of spheres

I have a 3D space where N spheres of identical size, identified by the location of their centers, are continually inserted. When a new sphere is inserted, I have the ability to efficiently query the ...
1 vote
0 answers
9 views

Convergence rate of quasi-newton method for non-convex objective function

Consider a real-valued $L$-smooth and non-convex objective function $f: \mathbb{R}^n \mapsto \mathbb{R}$. There exists a bound on number of iterations in order to find a (local) minima using ordinary ...
2 votes
1 answer
378 views

What are common ways to distinguish between local minima and long run-time in hyperparamteer optimization

I'm using Bayesian optimization for a pretty cost expensive function in the context of neural networks in order to optimize hyperparameters for the neural net. Is there a general, quantitative way to ...
1 vote
0 answers
43 views

How to find optimizers with computer in this kind of minimax problem [closed]

I have a minimax problem of the form $$\max_{\substack{u_1,\dots,u_n \ge 0 \\ u_1+\dots+u_n = 1}} \min_{\substack{v_1,\dots,v_m \ge 0 \\ v_1+\dots+v_m = 1 \\ v_{j_1} \le v_{j_2} \hspace{1mm} \forall (...
0 votes
1 answer
69 views

Simulated Annealing - Intuition

Most versions of simulated annealing I've seen are implemented similar to what is outlined in the wikipedia pseudocode below: ...
  • 111
3 votes
1 answer
73 views

Efficiently determine which nodes should leave a graph while maintaining connectedness

Suppose I have a graph with node weights, where a weight is either -1 or a positive integer. For example: If a node has weight -1, it is "happy", and cannot be kicked out of the graph. If a ...
1 vote
1 answer
183 views

Optimal path problem with constraint of minimal weight

Given an undirected weighted graph $G$ and two vertices $s, t$. We want to find a path $P$ from $s$ to $t$ that minimizes the following objective function $L$ $$L(P) = max(len(P), max\{c(e) \mid e \in ...
3 votes
0 answers
51 views

Minimize edge count in directed graph, allowing auxiliary nodes

Suppose I have a directed acyclic graph $G$. I want to find a graph $H$ containing the nodes of $G$ (and potentially more) which minimizes the number of edges in the graph, without changing the ...
  • 12.4k
-1 votes
1 answer
25 views

weighted graph separation algorithm proof

I have a graph G (G=(V,E)), where each edge has a non negative weight to it. My problem is to find a subset S (it doesn't have to exist) of nodes such the sum of all the weights of the edges that ...
2 votes
1 answer
68 views

Efficient algorithm to count number of intersections of n sets

I've come across this problem when working on a personal project of mine. I need an efficient algorithm of counting the number of overlaps between all pair combinations of n sets. Example: Set a = [...
  • 23
1 vote
1 answer
18 views

A lower bound for the makespan of heterogenous fog nodes

Why there is a sigma in the denominator of equation (8) in the picture? suppose we have n tasks and m fog nodes.
  • 25
0 votes
0 answers
36 views

Find The Least Waste When Sawing Wood Planks In A Specific Order

Similar to one of the questions that was posted here roughly 4 years ago. Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 50cm 30cm and 20cm. What kind of bottom-up ...
1 vote
0 answers
27 views

Minimize sum of products of partition [closed]

I have a set of positive integer numbers $A = \{a_1,...,a_N\}$ and I need to find a partition of $A$ into two sets, such that the sum of their products is minimal, i.e., $$ \min_{X,Y : X \cup Y = A} \...
  • 11
1 vote
1 answer
50 views

Algorithm to compute cheapest path between two pixels in an image

I need to compute the cheapest path between two pixels in an image. The travel cost is specified by the user, and may depend on the distance between the pixels (including pixel values, which is ...
0 votes
0 answers
60 views

Solving Scheduling Problem With Gradient Descent?

I try to solve some kind of scheduling problem and wonder if there exists any theory or implementations already. Assume my shop receives a set of orders $o\in O$, each of which consisting of a ...
  • 215
0 votes
0 answers
35 views

are computer errors inevitable?

this is my First post,I apologize for my ignorance. The question is: Could a programmer (human or Ai) with all the computing power and infinite time create a simulation of a world with our same laws ...
0 votes
3 answers
72 views

Compute a commutative and associative operation on n-2 arguments efficiently

Considering a function $f$ such that: $$ f(x_1, x_2, x_3) = f(f(x_1, x_2), x_3) = f(x_1, f(x_2, x_3)) $$ and $$ f(x_1, x_2) = f(x_2, x_1) $$ and a set $X = \{ x_1, \dots, x_n \}$; how to compute $$f(...
  • 103
1 vote
0 answers
69 views

Minimum swaps to rearrange array so that the same numbers are in consecutive positions

Problem: Given an array of $N$ integers in range $[1,M]$, count the minimum number of swaps to rearrange array such that the same values are in a row. For example, given an array $[1,2,1,1,2,1,2]$. ...
  • 159
0 votes
0 answers
27 views

Identifying the parameters and finding an optimal solution to a problem

I work in the Computer Graphics field, and I have a problem where I need to find the optimal solution for, but I'm not sure how to best formulate the problem mathematically, how to define the ...
0 votes
1 answer
36 views

Complexity of the partition problem with additional constraint

The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S_1$ and $S_2$ such that the sum of the numbers in $S_1$ equals ...
0 votes
1 answer
36 views

Printing an array using recursion

Printing an array using recursion is much slower as compared to printing an array using iteration. Why? Is iteration always faster than recursion?
0 votes
0 answers
18 views

On the bounds of number of iterations of generative adversarial networks

I've been wondering whether there is any analysis on the bounds of number of iterations of generative adversarial networks (GAN), where here 1 iteration refers to 1 step of generator + discriminator. ...
0 votes
0 answers
25 views

What is the difference between Optimal Control and Dynamic Programming?

I am reading Reinforcement Learning by Sutton and Barto, in which they mention dynamic programing and optimal control very often and as two different approaches. I wonder, what are the commonalities ...
  • 13
0 votes
0 answers
12 views

Cutting stock problem upper bound with gilmore and gomory

I am trying to implement this article https://arxiv.org/pdf/1905.04897.pdf (the article is there only for information, no need to read it to answer my question) At some point they say when talking ...
0 votes
0 answers
16 views

Is Disjoint Edge Weighted Group Steiner Tree problem equivalent to the regular Steiner Tree problem?

Disjoint Group Steiner Tree (DGST) is the following problem: Instance: a positive edge-weighted graph $G=(V,E,w)$, a collection of $k$ vertex sets (groups) $S_1,\dots,S_k \subseteq V$, such that $S_i \...
0 votes
1 answer
25 views

Multi Objective Optimization Using Only Single Objective Optimization Algorithms

Let's say there is a single objective optimization problem SP (e.g. a linear program) and an optimization algorithm SA for it (e.g. simplex). Then applying SA to SP yields an optimal solution ...

1
2 3 4 5
34