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.

1
vote
1answer
30 views

How do I model this expression maximization problem as a Knapsack problem?

Given two arrays of the same length $n$: $A = \{a_1,a_2,\dots,a_n\}$, $B = \{b_1,b_2,\dots,b_n\}$, I have to maximize the following expression: $$\frac{a_{i_1} + a_{i_2} + a_{i_3}+ \dots + a_{i_k}}...
2
votes
0answers
43 views

Inexact cover, or cover with gaps

Dancing Links: wikipedia article, research paper is an implementation of algorithm X for exact cover problem. In the Knuth's research papaer, linked above it is shown how Polymino problem (that is ...
1
vote
0answers
26 views

Job shop scheduling with events that should be completed simultaneously

I'm working on a scheduling algorithm that schedules a set of events with an event duration to a set of agents with various working times. However, some events require more than one agent to be ...
1
vote
1answer
33 views

Is there a generic algorithm to optimally combine elements by some arbitrary scoring method?

I'm looking for a generic algorithm to optimally combine elements of a list. I'm not sure if it even exists, but I believe some kind of divide-and-conquer algorithm could exist. In my specidifc case, ...
3
votes
1answer
85 views

Weird behaviour of softmax derivative?

I have been implementing some neural networks in MATLAB and recently I noticed a weird thing while implementing softmax derivative: Setting the derivative to one, rather than using the actual ...
2
votes
2answers
129 views

Maintaining a sorted moving window

I have an array of length $n$ representing a time series of data. I want to implement a moving (sliding) window of length $k < n$ and calculate things like sliding median, sliding quantile, sliding ...
1
vote
0answers
58 views

How to Optimise Each Multithreading Technique? (Cooperative/Preemptive/Simultaneous)

I am currently in the process of writing an IB Extended Essay on the efficacy of multithreading on increasing the performance of applications. So far, I have been able to deduce that there are three ...
4
votes
0answers
62 views

Need help figuring out a planning/assignment problem

I'm looking to solve this planning problem. Any pointers or ideas are much appreciated! You have a number of i individuals i = { 1, 2, ..., n } that need to perform tasks. Tasks are performed in ...
1
vote
1answer
28 views

How important is to formulate a convex optimization for a proposed algorithm?

I proposed a new sparse coding algorithm which has good results compared to the baselines, however, it has a non-convex optimization framework. I solved the problem using a general solver (e.g. ...
4
votes
1answer
89 views

Integer Problem Solving with two boolean selection variables

I am trying to solve a two dimensional combinatorial problem. Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible ...
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})$$...
0
votes
0answers
42 views

A list of regex and a list of strings

Given a list A of regex of size n and a list B of strings of size m, you need to output the regex that corresponds to at least one string in B. One way to do is by looping which gives an O(nm). Is ...
-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$. ...
0
votes
0answers
66 views

Machine learning for finding best fit?

How to apply machine learning method to learn to find a solution for the following problem, by going through multiple cases and learning from mistakes ? I am looking for an analytic solution for the ...
0
votes
0answers
18 views

References on the facility location problem

Thanks to the answers given to my last question, I'm looking for references on the facility location problem. I'd like to find a course for example, which can explain to me the problem and every I ...
1
vote
1answer
435 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
349 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 ...
1
vote
1answer
131 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
31 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
278 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
19 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
37 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 ...
0
votes
0answers
30 views

Minimizing steps to distribute in a candies in a circle

There are n children in a circle. Each of them has some candies (may be negative, positive or zero). They can give at a time a single candy to their neighbors. The end result is that they all should ...
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
54 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
16 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 ...
2
votes
1answer
133 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
67 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
94 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
28 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
118 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
17 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
48 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
124 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
234 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
46 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
246 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
40 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
155 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
12 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
106 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
13 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
170 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 ...
0
votes
1answer
845 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
93 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
25 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$-...