Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

# Questions tagged [optimization]

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

1,243 questions
Filter by
Sorted by
Tagged with
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 ...
146 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'...
86 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 ...
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 ...
54 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 ...
272 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 ...
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, ...
49 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 ...
48 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 ...
556 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$ ...
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 ...
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 ...
157 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 ...
42 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 ...
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 ...
70 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 ...
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, ...
115 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', ...
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 ...
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). <...
350 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 ...
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 ...
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 ...