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

Given a set of point sets, find points from each set with maximum total distance between them while each distance is larger than a threshold

The title may be a bit confusing but the problem is this; Lets assume I have 5 points in 4 groups (in total 20 points). What I want to achieve is; -> Pick one point from each group (we will have 4 ...
1
vote
1answer
125 views

Help needed for understanding proof of No Regret Multi Armed Bandit Algorithm

I was reading Elad Hazan's book on Online Convex Optimization(http://ocobook.cs.princeton.edu/OCObook.pdf) and am facing difficulty understanding the proof given for the No regret algorithm for MAB (...
1
vote
0answers
22 views

Expected development of 'fitness histogram' for PSO over time

I'm plotting the fitness histogram of my particle swarm optimizer - i.e. the individual fitness scores for each particle and iteration - during a run. The problem tackled is basically curve fitting/...
0
votes
1answer
84 views

Finding minimum number of edges such that when adding into the graph, the graph is a 2-connected graph

Given is a undirected and 1-connected graph G=(V,E). Between every two node b=(u,v) in graph G there is a cost c_b to build another edge(Regardless of whether (u,v) ∈E or not). We use a C={c_b |c_b∈Z^+...
0
votes
1answer
151 views

What is the difference in SMO algorithm for SVM and SMO for one class?

Please let know if this is not the correct forum to ask this question. If not can anyone please tell where can I ask this question? I am trying to understand the difference between the paper : https:/...
2
votes
1answer
37 views

Computational complexity of maximizing sum of rational functions

I have a optimization problem: $$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
0
votes
1answer
65 views

Stable matching with asymmetric arrays (gale shapley)

I was reading this thread The stable marriage algorithm with asymmetric arrays and started to solve the problem asked in this thread about matching 5 students with 10 dorms. One of the answer ...
0
votes
1answer
34 views

If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?

My problem is mainly from this lecture notes on convex optimization here page4 Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer ...
0
votes
1answer
54 views

Interpretation of Backtracking Algorithm Problem - weighted matching

I am attempting to resolve the following problem using Backtracking: Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P_{ij}$ is the preference of the man $i$ ...
1
vote
2answers
563 views

Knapsack problem: equal profits

I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal. More formal definition of the problem from a Wikipedia article on KPs: If all the ...
2
votes
1answer
26 views

Positioning items to maximize separation

Say we want to place n items on the real line. Let us denote the position of item i by $p_i$. We have interval constraints on the position $p_i$, i.e. we are given $l_i, r_i$ such that $l_i \le p_i \...
1
vote
1answer
64 views

Variant of interval scheduling with varying task durations

I am probably just missing the correct term for my problem to find the solution but here it goes: I have a set of tasks with a given duration and an interval for each task in which it has to be ...
4
votes
1answer
147 views

How to produce nonzero absolute differences between neighboring numbers on a circle as long as possible?

I apologize for the lack of an even better title. The main reason I couldn't find a better one is because I have a problem that I cannot find reference anywhere. I am pretty sure it has a name, but I'...
1
vote
0answers
92 views

NodeJS vs Golang Performance [closed]

I was testing performance of NodeJS vs GoLang with a very simple script. Situation one is three nested for loops to do a Sin calculation and Situation two is just one for loop. It turns out that for ...
1
vote
0answers
22 views

Sparse feasible solution $|x|_0\le k$ for system of linear inequalities $A x \le b$

Suppose the set of linear inequalities $Ax\le b$, in which $A\in\mathbb{R}^{m\times n},x,b\in\mathbb{R}^n$ is given. Is it possible to determine in polynomial time with regard to $m$ and $n$ if there ...
4
votes
1answer
55 views

Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a ...
4
votes
1answer
282 views

Minimize sum of squares of rows in matrix when sum of columns have some constraint

I'm looking for an algorithm that can find any matrix $a_{j,i}$ such that $$ \sum_{i \in I} \left(\sum_{j\in J} a_{j,i}\right)^2 $$ is minimal, while also for each $j\in J$ satisfying the constraint ...
3
votes
2answers
51 views

Optimization Problem when calculating fitness is expensive

I need to solve an optimization problem, maximizing fitness in a set of around 1 million solutions. Calculating the fitness of any solution is very time consuming, taking around 5 minutes. Therefore, ...
0
votes
1answer
52 views

On the proof of NP-Hardness of the Cardinality Constrained Quadratic Knapsack Problem

in Polyhedral Study of the Cardinality Constrained Knapsack Problem the authors prove that the Cardinality Constrained Knapsack Problem is NP-Hard by reducing PARTITION to it. Besides, it's easy to ...
2
votes
0answers
49 views

How to minimize the number of gates of an arithmetic circuit?

A circuit is simply a DAG, with some input wires, some output wires, and some operations on the vertices. Consider an arithmetic circuit where the only operations are addition ($+$) and ...
1
vote
1answer
584 views

How does the problem of “Scheduling to Minimize Lateness” exhibit optimal substructure?

The problem of "Scheduling to Minimize Lateness" is as follows (Section 4.2 of the book "Algorithm Design" by Jon Kleinberg and Eva Tardos): Input: A finite set $J = {J_1, J_2, \ldots, J_n}$ of $n$ ...
0
votes
0answers
38 views

models/formalism for optimization algorithms?

In Wolpert's "No free lunch theorems for optimization", he uses the following formalism for an optimization algorithm: Let $X$ be a finite space of which an element has to be chosen, and let $Y$ be a ...
0
votes
1answer
25 views

What is the difference between the study of Evolutionary algorithm vs. Optimization?

I have a course named "Evolutionary Algorithm". But, our teacher is always mentioning the word "Optimization" in his lectures. I am confused. Is he actually teaching Optimization? If yes, why is the ...
1
vote
1answer
170 views

Optimal substructure and dynamic programming for a variant of the rod cutting problem

The rod-cutting problem described in Section 15.1 of CLRS, 3rd edition is the following. Given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \ldots, n$, determine the ...
2
votes
1answer
43 views

How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there ...
2
votes
1answer
51 views

Optimal assignment of +-1 values to vertices in a graph

Let $(V, E)$ be a simple connected undirected graph, $f: V \to \{-1, +1\}$, and $g: E \to \{-1, +1\}$. The function $g$ is completely defined by $f$, while $f$ is something we get to choose. The only ...
1
vote
1answer
75 views

Knapsack-type problem where the objective function is a ratio

I have a problem where I have a number of proposed initiatives each with a cost and payoff. I need to select a subset of these initiatives in order to maximize the ROI for the selected set as a whole ...
5
votes
0answers
89 views

Specific quadratic 0-1 knapsack problem solvable in linear time?

I am interested in a simple variant of the quadratic knapsack problem. Let $\{w_1, \ldots, w_n\} \in \{0,1\}$ be $n$ weights and $\{v_1, \ldots, v_n\} \in \mathbb{R}$ be $n$ values. Furthermore, ...
4
votes
0answers
116 views

One-sided, distance-optimal polyline reduction to a given number of vertices

So I have been battling this rather peculiar problem: given the following input (on an euclidean plane): point p polyline l integer n p is not inside of the convex hull of l find a new polyline l', ...
3
votes
1answer
45 views

Maximizing quantities/length in buckets to match each other

I have a use case, real one, and I'm trying to come up with an efficient maximization algorithm to solve it. I'll try to simplify, with a simple analogue, and after will explain the real world use ...
1
vote
0answers
21 views

In multiobjective optimization, how to calculate the distance to reference point?

In multiobjective optimization, what does the distance exactly means, is it: 1) The distance from reference point (V) to an individual (Xi) (candidate solution) in the population (decision space). <...
2
votes
1answer
384 views

Finding paths with minimum intersections

Given a graph and a set of origin-destination $\langle o_i,d_i\rangle$ pairs. The goal is computing a set of paths such that every pair has a path and number of common vertices between paths is ...
3
votes
2answers
69 views

Finding pairs of numbers in array whose reciprocals sum to 1

Given an array of numbers. Find all pairs of numbers satisfying the condition $1/a + 1/b < 1$. For example: Input: $2, 3, 1, 0.5, 3, 1.6$. Output: $(2,3), (3,2), (3,3), (3,1.6), (1.6,3)$. We can ...
1
vote
2answers
46 views

How to create constraints for Mixed integer linear problem?

i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can ...
4
votes
2answers
153 views

search problem vs optimization problem

This is mostly a terminological question: Is there a fundamental difference between "optimization problems" and "search problems"? Apologies if this is an obvious question As I understand it, we can ...
1
vote
1answer
32 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
58 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
32 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
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, ...
3
votes
1answer
125 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 ...
3
votes
2answers
284 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
60 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
72 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
31 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
120 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
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})$$...
-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
650 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
488 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
305 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 $...