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
0answers
46 views

Knapsack problem with additional conditions for data objects

I've been trying to theorize how to solve a certain type of problem for months now. Suppose you have a collection of $m$ pre-defined $(d+2)$-dimensional vectors like so: $$(v, s, m_1, \dots, m_{d})$$...
-1
votes
1answer
37 views

Optimization problems and quantifiers

A simple optimization problem is of form $\max_{x\in\mathcal R}f(x)$. We can quantify as $\exists x\in\mathcal R\forall y\in\mathcal R f(y)\leq f(x)$. The quantification here is $\exists\forall$. ...
1
vote
1answer
593 views

Fantasy premier league dream team algorithm?

For those of you who are not familiar with FPL, here's a short version. You have players playing as either Goalkeeper, Defender, Midfielder or Forward. Each player has some price (either rounded to .5 ...
2
votes
1answer
427 views

Optimal way to find maximal sum (with constraints) of array elements

Problem: Find the maximum sum of the elements in an array, with the following constraints: all the elements of the array are non-negative integers each element can either be left out completely from ...
2
votes
1answer
198 views

Parameter sharing / weight constraints in Neural Networks

I would like to train a neural network whose parameters (alternatively, weights) are subject to linear constraints such as $w_{i,j} = w_{i',j'}$, where $w_{i,j}$ denotes the weight from input node $...
2
votes
1answer
32 views

optimize string search on black-box function

Given a lower-bound predicate function which returns true if an input is greater than or equal to a constant string, what is the optimal way to search for the ...
2
votes
1answer
17 views

Finding many different minima of nonlinear cost function

Given a nonlinear cost function $G(\vec{x})$ of many variables, does there exist a method that allows one to find successive local minima $\vec{x}_0, \vec{x}_1, \dots$ so that $\vec{x}_n$ is ...
3
votes
2answers
432 views

Optimal meeting point

I'm interested in studying the problem of the optimal meeting point, which can be described as follow: $n$ individuals who want to gather in a restaurant (for example). They want a fair meeting point ...
1
vote
1answer
20 views

Finding a non-boundary, local optimum of a non-convex function over a convex feasible region

I have a reasonably smooth non-convex non-monotone function in high(ish) dimensional space, that I wish to find a local minimizer for, over a convex feasible region (the intersection of a ball with a ...
3
votes
0answers
38 views

Optimal flow in a network with non-constant edges' weights

I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather ...
3
votes
1answer
68 views

Find the shortest sub-tree with node deletion

Let $T=(V,E)$ be a tree rooted in $r$ and let $L$ denotes the set of leaves of $T$. For a given $v \in V$, let $C(v)$ be the out-neighors of $v$ i.e. its children in $T$ and $p(v)$ be its in-neighbor ...
0
votes
0answers
58 views

Hessian in reinforcement learning

The Hessian of multi-layered network exhibits known behaviour at critical points as shown in [1]. The tools of random matrix theory allow [2] to deduce the asymptotic distribution of the eigenvalues ...
2
votes
0answers
18 views

Job Shop Problem with dynamic jobs

I've got a problem at hand that's about scheduling tasks to different ressources, basically a simple job shop problem. But: my tasks "branch" dynamically, that is, there are tasks that not only have a ...
3
votes
1answer
226 views

Which algorithm can calculate an optimal allocation of students to projects?

I am trying to find an algorithm which calculates an optimal and stable allocation of $n$ students to $m$ projects, where each student strictly ranks all projects by preference. The available projects ...
4
votes
2answers
69 views

Largest weight-limited connected subgraph: NP-complete?

When playing Terra Mystica, it might be useful to predict how many spades you will get throughout the game, and use this information to decide where to build, such that you stand a good chance of ...
4
votes
2answers
96 views

How to model and solve this problem?

I have a matrix $P \in M_n(\mathbb N)$, where $$ P = \begin{bmatrix} 0 & P_{12} & \ldots & P_{1n}\\ P_{21} & 0 & \ldots & P_{2n}\\ \vdots & \vdots & \ddots &...
2
votes
1answer
26 views

How to find splitting point in [0,1] to maximize sum of sign function?

Given two $n$-number arrays $a_1, a_2, \ldots,a_n \in [0,1] $ and $b_1, b_2, \ldots,b_n \in [0,1] $. We would like to find the real number $x^{*} \in (0,1)$ s.t: $x^{*} =\arg\max_{x} \sum_{i=1}^n \...
2
votes
1answer
33 views

How to efficiently select the initial node to start a search in a Skip Graph

Checked out a few papers on Skip Graphs: Locally Self-Adjusting Skip Graphs Adaptive Probabilistic Skip Graphs Skip Graphs Family Trees All of the insertion/deletion algorithms assume that you have ...
2
votes
0answers
121 views

Shortest path from one source which goes through N edges [closed]

In my economics research I am currently dealing with a specific shortest path problem: Given a directed deterministic dynamic graph with weights on the edges, I need to find the shortest path from ...
1
vote
1answer
19 views

CNN/Neural Network: Can I still estimate 3 parameters if my input data has insufficient parameter labels?

I am trying to simplify a CNN model. Currently, I need to train 3 different models (with the same architecture) to estimate each parameter. I am just wondering if there is a way to just train one ...
0
votes
1answer
49 views

Compute unknown matrices that minimize a sum

This problem is about working with smart-phone accelerometers. To calibrate accelerometer, I need to find three unknown matrices T, K and B that minimize this sum: $$\sum_{i=0}^N(|g|^2 - |TK(a_i + B)|...
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 ...
3
votes
3answers
130 views

Minimal number of nodes needed to connect a disconnected graph

Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such that $G[U' \cup T]$ is connected. If we ...
4
votes
1answer
288 views

Maximizing the sum of selected elements in a matrix

I’m trying to find an efficient algorithm for the following optimization problem: Given a matrix $A$ with elements $a_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n<k$) such ...
3
votes
1answer
47 views

Minimum number of moves required to transfer items from source bins to target bins?

I have a set of source bins, each with some number of items, and a set of target bins. I want to move all of the items from the source bins to the target bins, using the minimum number of moves. ...
1
vote
1answer
307 views

stable marriage/residency problem with multiple matches

Consider the stable marriage problem, where both sides want to match with multiple individuals from the other side (perhaps a fixed number, or perhaps within some range). Something like, if doctors ...
1
vote
0answers
41 views

Re-arrangement Algorithm Minimizing Total movement

I have $n$ items arranged on a straight line (like a number line, items can only move 2 directions). The each item has a size, some distance around their center position, that can't overlap with ...
2
votes
1answer
158 views

Maximum connected cell length containing two different numbers

Suppose we are given an $n\times m$ matrix $M$ of positive integers. The adjacent cells of a particular cell is the up, down, left and right cells. Like for cell $M[i][j]$ the adjacent cells are $M[i-...
1
vote
1answer
37 views

How many queries does it take to find the best flight?

I often find flights through a search engine like Google Flights. On input some refined subset of the space of all flights (e.g., non-stop only, departing in the morning, from one of two airports, and ...
2
votes
1answer
13 views

Strassen's algorithm on unit vectors?

I am trying to do a dot product of two vectors of each 128 dimension. I am just looping each member and calculating the sum. ...
5
votes
0answers
121 views

Can all types of problems be converted to decision problems?

We know all optimisation problems can be converted to decision problems. Is that true for search problems, counting problems and function problems as well? Description of the types of problems is ...
0
votes
0answers
14 views

Optimizing convex function in an online manner

I have a convex function of $n$ variables, $f(x_1,x_2,\dots,x_n)$ and need to find its minimizer. Are there algorithms that can retrieve the minimizer in an online fashion? i.e. solve for $x_1^{(opt)}$...
2
votes
2answers
192 views

Implications of Integral linear program

Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$ Let $(P^*)$ be ...
1
vote
1answer
1k views

Find all local minima in a big 2d array

Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all ...
0
votes
0answers
98 views

Shortest path between 2 nodes subject to constraints

I am trying to find shortest path between 2 nodes in a graph similar to below: Each edge has a weight assigned to it. Also, the graph is directional with each edge directing from left to right. I ...
1
vote
0answers
26 views

Markov Decision Process Optimal Policy

Consider the setting of finite MDPs. I will be using the notation in Chapter 2 of http://rll.berkeley.edu/deeprlcourse/docs/ng-thesis.pdf. Say we have already computed values for the optimal $Q$-...
2
votes
1answer
60 views

Find the nearest sum to a given number of two elements in sorted matrix

Given a sorted $n\times n$ matrix $A$ of real values. That is $a_{ki}<a_{kj}$ and $a_{it}<a_{jt}$, when $i<j$. Propose and algorithm, finding two elements of this matrix with the sum nearest ...
1
vote
1answer
49 views

video shape recognition in real time

I believe from common sense that video shape recognition problems (identifying shape of a moving object) is of natural interest in many real world situations. The process of identifying is understood ...
0
votes
1answer
20 views

Evolutionary algorithm - is there a relation between minimum iterations and size of decision variables

I am solving an optimization problem using SPEA2, my problem has three cases with decision variables 25, 50 and 100 in each case. I want to ask if there is some relationship between the number of ...
2
votes
1answer
136 views

Find the sum of the first K subsets of integer array

We have given a multiset of $N$ integer, both positive or negative. Consider all $2^N$ subsets, sorted by their sum (the empty subset has sum 0). We want an algorithm that outputs only the first $K$ ...
0
votes
1answer
46 views

Alternatives to evolutionary computing for structure, design and policy optimization (optimal structure search)?

I once had this question https://math.stackexchange.com/questions/1083338/structural-design-meta-optimization-is-there-mathematical-theory-optimiza about the methods for finding optimal structures, ...
1
vote
1answer
157 views

Assuming that P=NP - Finding an optimal algorithm for 3SAT

Let assume that P=NP so we have both search and decision algorithms for 3SAT at polynomial time. Can you help me to find an optimal algorithm for optimize 3SAT, i.e.: to find the maximum number of ...
4
votes
4answers
510 views

Are there any optimization problems in P whose decision version is hard?

Normally to show that an optimization problem is hard, we show the corresponding decision version of the problem is hard. However, is this sufficient to support the conclusion? Does there exist any ...
1
vote
0answers
41 views

Polynomial time algorithm for a simple machine scheduling problem

Think about a setting where there are $n$ tasks and $m$ machines. We are interested in task-machine assignment. Let $p_i$ be a non-negative completion time of job $i$. Also, $x_i$ denotes the machine ...
0
votes
1answer
91 views

Maximize vertex cover weights with bounded edge weights in a connected subgraph

Similar questions were asked elsewhere, but no satisfying answers occurred yet. In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is ...
1
vote
0answers
77 views

Chromosome length in Genetic Algorithms

In order to find the appropriate length of chromosomes in GA programming, the author of this book states: Suppose six decimal places for the variables' values is desirable. It is clear that to ...
2
votes
0answers
217 views

Understanding the Polyhedral Model

I am wondering at a high level the mathematics of the Polyhedral Model. The polyhedral model (also called the polytope method) is a mathematical framework for programs that perform large numbers of ...
1
vote
1answer
45 views

Has the problem of finding the most profitable transactions given a set of discrete time series been well-studied?

Overview and Problem Description Suppose I have a set of N discrete time-series (represented as a map from time-interval-index to value/utility), and I would like to identify a sequence of actions in ...
0
votes
1answer
24 views

The optimal way to find leaves in a weighted full binary tree

Let T be a full binary weighted tree. For a node v in T, the cost of going right is a i.e w(v, v.right) = a while w(v, v.left) = b How do I find optimal paths to all leaves from the root. I don't ...
0
votes
0answers
27 views

How many optimal alignments can be there for a string of length m with a string of length n?

So I was practicing optimal alignment algorithm and I was stuck with this question of finding optimal alignment for a string of length m with a string length n ? Also is it possible to run it in theta(...