# Questions tagged [optimization]

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

1,267 questions
Filter by
Sorted by
Tagged with
33 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 ...
34 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, ...
132 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 ...
314 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 ...
61 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 ...
75 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 ...
32 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. ...
128 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 ...
47 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})$$...
38 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$. ...
662 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 ...
502 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 ...
339 views

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 ...
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. ...
142 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 ...
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)}$...
226 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 ...
2k 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 ...
130 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 ...
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$-...
73 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 ...
59 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 ...
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 ...
143 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$ ...