The Stack Overflow podcast is back! Listen to an interview with our new CEO.

# Questions tagged [optimization]

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

1,226 questions
Filter by
Sorted by
Tagged with
87 views

### Filling a string with wildcards with minimum cost

You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string. You are allowed to write data to the string in blocks of ...
61 views

### Is it possible to make data structure that will find MEX and support modification queries

Let's say we have given array of $n$ elements, now we want to create data structure that will allow us to get the MEX of its elements, MEX meaning the smallest positive integer that is not present in ...
25 views

### Multi-type max-flow

Suppose you have $m$ sources $s_i$ and $n$ sinks $t_j$, but every source produces a certain type of flow, out of $k$ types, and every sink demands a certain type as well. We would like to know if ...
2k views

### Fitting different rectangles inside a rectangle

I have a fixed rectangle of size X x Y. I also have a bunch of rectangles of different sizes. I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate ...
60 views

### Among $k$ unit vectors, find odd set with sum length less than 1

I have $k$ unit vectors in $\mathbb{R}^k$. Can I efficiently identify a set of $2n+1$ vectors $v_1, \dots v_{2n+1}$ such that $\sum_{i< j} v_i\cdot v_j < -n$ for any $n$ -- or determine that no ...
56 views

### Portfolio allocation with a few twists

A similar question has been asked here, but this one is more complicated and has more constraints. I'm trying to find an algorithm to solve the following (real-life) problem: A customer has $M$ ...
27 views

### Filling a board with maximum number of fixed size tiles

You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), ...
62 views

### What do we call a greedy algorithm that tracks the best $n > 1$ solutions?

A naive greedy algorithm tries to find an optimal solution based on the best solution so far, hence it may get stuck in local optima. To avoid this problem, we may keep track of the best $n > 1$ ...
52 views

### Unknown length of chromosone in genetic algorithm

I've read some about genetic algorithms and the general approach, but I haven't found anything about using it when the length of the solution is unknown. How would the generation of the initial ...
41 views

### Global optimization algorithm based on MapReduce

In the field of the intelligent swarm, there are many algorithms can find global optimization, such as Ant Colony Optimization (ACO), particle swarm optimization (PSO). Is there any optimization ...
150 views

### Lower bounds on regret

In "regret" styled analysis over $T$ steps of an iterative algorithm $\{x_i \in F \}_{i=1}^T$ (where $F$ is some feasible set) being given the sequence of loss functions $\{ f_i\}_{i=1}^T$ one defines ...
284 views

### Are the No Free Lunch theorems useful for anything?

I have been thinking about the No Free Lunch (NFL) theorems lately, and I have a question which probably every one who has ever thought of the NFL theorems has also had. I am asking this question here,...
78 views

### long-lived scheduling using max-flow & push/relabel

I'm writing a scheduler of long-lived Processors which execute long-lived Tasks. Processors and Tasks may each come and go over time, at any time (when a Processor departs, its assigned Tasks now ...
188 views

### Black-box combinatorial optimization problem over permutations

I am solving general black-box optimization problems like: x*: f(x) -> min, where x are permutations of length N (N = 50 for example, so brute force search is not possible). Objective function f(x) is ...
82 views

### Shift Organization algorithms (Constraint Programming + Marriage problem)

I want to assign people to cover shifts considering a set of constraints and preferences. Here's the problem definition: Daily shifts must be covered by workers, who are divided in three groups: ...
42 views

### Is this problem about picking optimal entries of a matrix NP-complete?

I am trying to solve a real-world problem that I was able to reduce to the problem described below. I would like to know the following things: Is there literature about this problem? Is the ...
33 views

### What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set?

Consider the highlighted columns in the following table: Starting with 100,000 newborns, $l_{x+2}$ denotes the number of individuals in the sample still alive at age $x+2$. If we consider Makeham's ...
67 views

### Finding the number of ways to partition $\{1,…,N\}$ into $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$ for a given $N$

I am trying to think of how to optimize the following problem: Let $S = \{1,2,...,N\}$. How many ways can $S$ be partitioned into non-empty subsets $P_1$ and $P_2$ such that $sum(P_1) = sum(P_2)$? I ...
440 views

### How to find the supremum over all the “good” (interior) polytopes for a given set of 3D points?

Let $S \subset \mathbf{R}^3$ be a set of points in 3D and let $O=(x_0,y_0,z_0)$ be the origin/point of reference. We consider a convex polytope $P$ good / interior if: $P$ is wholly contained ...
269 views

### How to maximize $(h[j]-h[i])(j-i)$ in $O(n)$

I see many algorithmic problems that always reduce to something a long the lines of: You have an integer array $h[1..n]\geq 0$, you need to find $i,j$ such that maximizes $(h[j]-h[i])(j-i)$ in $O(n)$ ...
53 views

### Dynamic path planning and waypoint sorting

Good evening everyone, I have a question that I am having a bit of trouble formulating properly and thus it is making it complicated to look up literature on the subject. What I am looking for is a ...
326 views

### Are there practical methods for solving ILP?

Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms! Is solving an ...
75 views

### Simulated annealing upper bound seems way too high

In a nutshell I found this paper that provides an upper bound for the amount of iterations we expect before visiting the global optimum at least once. (It then uses that number to find a lower bound ...
138 views

### Converting nested absolute value into linear programming

I am having trouble writing the following optimization problem as a linear program (LP) $$\min_{x \in \mathbb R^2} \big| | x_{1} - a_{1} | - | x_{2} - a_{2} | \big|$$ where $a \in \mathbb Z^2$ is ...
34 views

### Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)

I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different. All I managed to think of was the ...
145 views

### Efficient bucketing of numbers

Assume we have a sorted list of n numbers, I want to map those numbers to m buckets or clusters. For each bucket the average of all numbers in that bucket will be computed. The task is to find a ...
33 views

### suggestion for optimization problem with $\ell_{2,1}$ norm and Frobenius norm

Suppose I derive my application problem as the following type of optimization problem: $$\min_X ||X||_{2,1}+||X^\top||_{2,1}+||X-A||_F,$$ where $X$ is a (square) matrix, $A$ is a constant matrix. I ...
69 views

### Maximizing the sum of adjacent pairs of elements

I encountered the following interesting problem on stackoverflow: Given numbers $a(1)<\cdots<a(n)$, find a permutation $\pi$ that maximizes $$\sum_{i=1}^{n-1} a(\pi(i)) a(\pi(i+1)).$$ The ...
45 views

### Algorithm to find most efficent partitioning of a set

Given a set $S$ with a finite number of elements, where each $s_i\in S$ is itself a set with a finite number of elements, how do you partition $S$ using as few partitions as possible, such that all ...
48 views

### How to approach homework about graph traversal

I am given a connected, weighted undirected graph. I must obtain minimum possible weight sum of "marked" vertexes in the graph. Vertexes must be marked so that each simple cycle contains at least ...
81 views

### Does big-Oh notation in optimization follow the same convention as in CS?

I first learned big-Oh (little-Oh, big-Theta.....) complexity for growth of functions using CLRS in a computer science class. Now I am doing a project on optimization. In our optimization class, we ...
32 views

### Minimum fare price on public transportation network

In a public transportation network each stop has an assigned zone. The price of a trip depends on the number of adjacent zones that the user touches during a given trip. If the user touches two ...
13 views

### Relating indexes for parameters and variables

I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help. I have the following ...
1k views

### What is a ridge - Hill climbing

I do not understand what is a ridge for hill climbing. The definition I found is a place where all points appear like a maximum, but how is that different than a plateau?
26 views

### Minimum expected cost through an unconventional graph with probabilities at which edges are selected

I'm having trouble identifying the approach to minimize the cost of reaching a certain state in an optimization problem. I've modeled it here as a game. Problem Structure You buy heroes and send them ...
32 views

### Algorithm to select sets of objects while maximizing number of objects covered

If we have different objects, [A1, A2, A3, B1, B2, B3, B4, B5] Some calculations will be performed to find compatible objects. For example, lets assume following ...
131 views

### Optimization of coefficients by using genetic algorithm

I want to optimization the coefficient of FIR filter using genetic algorithm method. The main data structures in the Genetic Algorithm are: chromosomes (vector) objective function values fitness ...
506 views

### How to construct the objective function for genetic algorithm optimization?

I am trying to optimize a coefficients of filter by minimizing sum-squared error. I want to use a genetic algorithm (GA) optimization wherein the coefficients of filter form the GA's chromosome (a ...
370 views

### How to classify a 3D “Knapsack” problem where the only limitation is space, i.e. there is no weight constraint?

The problem is defined as: pack a 3D space with a given list of 3 types of cuboids which are each assigned a value, trying to either completely fill the space or to achieve the highest total value of ...
405 views

### Finding the shortest sublist that contains all search terms

I've been trying to get better at writing algorithms and came across a problem that was something like this: Given a list of words: ...
63 views

### Buying as many items for as much money

I cant find a way to implement a certain solution. Let me flesh out the problem. Somebody gives you X amount of money and sends you to the shop to buy Y amount of items. You must spend as much money ...
255 views

### INOI 2017 Problem 2 - Training

INOI 2017, Problem 2, Training Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it passes through N cities, numbered 1, 2, …, N, and in this order. ...
115 views

### Find a permutation that maximizes $\sum_i a_{i-1}a_ia_{i+1}$

I want to solve the following problem: You have a list of numbers, for example [10, 33, 7, 7, 12]. The goal is to find the permutation of this list that maximizes the function \$\sum_i a_{i-1} ...
35 views

### Is graph search of shortest (optimal) path an instance of optimisation?

I am familiar with mathematical (gradient-based) optimisation methods, some heuristic methods like GAs or linear programming methods like simplex algorithm. I am not too familiar with graphs / trees ...
91 views

### black-box function optimization with binary vector input: terminology and NP-hardness proof

I have a black-box function optimization problem: $$\arg\max_{\vec{x}} \; f(\vec{x}, \vec{y}) \\\text{subject to } \vec{x} \in \mathbb{Z}_2^N, \|\vec{x}\|_1=K, K<N, \vec{y} \in \mathbb{Z}_2^M$$ ...
152 views

### Why is sequential search of ordered list slower than search of unordered one

I have got assignment to implement set class with linked list, so I first made it with unordered list and time needed to insert million integers is bit less than hour. Then I thought I can get it to ...
64 views

### Arrange objects in space so that the outline takes the least surface/volume

Imagine you have a number of 2-dimensional objects. The question is how to fit them all in a rectangular space in such a way that this rectangle takes the smallest area possible. On the below image ...
69 views

### Filling a 3x3 board with connected tiles

long story short: I want to list all possible combinations of n tiles on a 3x3 board with the restriction that at least 6 tiles are part of a connected chain. Tiles are connected if the pattern ...