We’re rewarding the question askers & reputations are being recalculated! Read more.

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
148 views

How to setup a model for a guillotine cutting stock problem?

Backgroud. I'm reading papers about cutting stock problem (CSP). Said Ben Messaoud, Chengbin Chu, Marie-Laure Espinouse (2008) Characterization and modelling of guillotine constraints. European ...
2
votes
1answer
59 views

Choosing $n$ points to get the closest sum

Let's say there is a set of $N$ real numbers, $x_i, i\in\{1,2,...,N\}$, and we would like to choose $n$ points out of them to get the sum of the chosen points as close as possible to a certain number, ...
2
votes
0answers
29 views

Why can optimality be preserved when inserting a new conjunct into an optimally ordered conjunction of conditions? [duplicate]

In a programming language with short-circuiting, a conjunction of N independent conditions has the following expected cost: where: ...
2
votes
2answers
151 views

The optimal way to reverse engineer a binary classification problem

I am not sure if this question is more suitable for CS, theoretical CS or math so feel free to improve the description and migrate it. In a scenario very similar to popular binary classification ...
2
votes
0answers
152 views

What is an efficient algorithm to solve the following combinatorial optimization problem?

I have a combinatorial puzzle to solve. The puzzle has 10 interconnected spots for polyhedral blocks to fill in. The blocks have these attributes: weight, shape (denoted by number of faces, $n_{\rm ...
2
votes
1answer
360 views

Aggregate planning with inventory

I am lost in formulating a mathematical model for my linear integer program. My problem is; how to include inventory and backlogging. The following is given: 1100 units can be produced each month ...
2
votes
1answer
262 views

Why does the time/space tradeoff exist

I'd like to know why when choosing how to optimize an algorithm that there almost always (always?) exists a time/space tradeoff. Definition: https://simple.wikipedia.org/wiki/Space-time_tradeoff. ...
1
vote
1answer
181 views

Verifying if a greedy solution is optimal for a specific instance (Set cover)

Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution. Is there an efficient way of verifying if, for that particular instance, the given solution ...
3
votes
4answers
128 views

Can loops like this one be algorithmically transformed into multiplication

Are there known techniques for converting a loop like the following to an if and a multiplication? ...
3
votes
1answer
1k views

Multi- Knapsack problem variation

I'm trying to model a scenario where there are n items, each having weight and volume. We also have m number of knapsack, each ...
0
votes
0answers
43 views

How to prevent moire artifacts in this light casting algorithm?

I am writing a 2D light casting algorithm with OpenGL compute shaders. The algorithm is simple: For each light source shoot out light rays from it, the ray begins at the light coordinates, it ends at ...
2
votes
2answers
308 views

Scheduling / Queuing jobs with multiple different workers

I have a stream of jobs (so I don't know upfront how many jobs). And I have N workers in the system. Now I want to schedule / queue a job to one worker (a worker can have multiple jobs in his queue). ...
1
vote
1answer
70 views

Data Searching from a large data set without reading each element

I have just started learning algorithms and data structures and I came by an interesting problem. I need some help in solving the problem. There is a data set given to me. Within the data set are ...
1
vote
1answer
62 views

Is this problem a variant of TSP problem? if not, what is it called?

A jet which can fly no more than R kilometers without refilling, is at location 0 and needs to fly to point N+1. There are some petrol stations on the way, some of which are ready to use, others are ...
1
vote
1answer
56 views

Understanding the geometrical interpretation of word2vec

I'm trying to understand how the $word2vec$ method actually nudges word vectors of similar semantic/syntactic content closer together in the word vector space. I've read here (Quora answer) that it's ...
1
vote
1answer
76 views

Maximisation of graphs weight

I have a graph related problem. Let $G$ be an undirected weighted graph of $N$ nodes. I want to find $p$ independent (they have no edge linking them) sub-graphs of $m$ nodes in a way that the total ...
2
votes
0answers
63 views

Are there many empirical results about which metaheuristics are well-suited for which problem domains?

One of the nice things about genetic algorithms is that they can easily be used for a diverse array of problem domains, whereas PSO for example seems best-suited for candidates of real-valued vectors (...
3
votes
3answers
2k views

Portfolio rebalancing algorithm

Quite possibly this problem is already solved and has it's own name, but I was unable to find any directions. So, I have a portfolio with some items in it: | Name | Price | Amount | Share | |------...
1
vote
0answers
91 views

Was the “cuckoo search” independently discovered before 2009? If so, what was the name given to it?

Background: I would like to experiment with evolutionary algorithms to generate the "optimal" poem, according to a fitness function to be determined later. However, I cannot think of a good way of ...
2
votes
0answers
71 views

Lazy evaluation on slow Boolean functions (optimization)

Short-circuit evaluation is a straight forward subject for lazy evaluation on Boolean expressions, I noted that two factors could be useful in ordering Boolean functions to improve run-time. But this ...
2
votes
3answers
440 views

Algorithm to choose the best team of 6 Pokémon given a constraint

Apologies if this is a duplicate. I searched for some time and the closest I could find was the Knapsack Problem, which does not fit because I have a fixed team size & a different value function. ...
-1
votes
1answer
60 views

Showing MAXIMUM CLique is NPO-simple and MAXIMUM GRAPH COLORING is not

Recall the notion of NPO problem. An NPO problem is simple if the following is true: $\forall k \in \mathbb{N}^*. (\forall x. OPT(x) \leq k) \in P$ In words, given any positive integer $k$, the ...
2
votes
2answers
156 views

How can I partition a graph such that as few edges as possible cross partition boundaries?

The following problem appeared while trying to distribute a program over a cluster of computers: Given an undirected graph $G=(V,E)$ and an integer $n$, partition the vertices of $G$ into $n$ ...
2
votes
1answer
201 views

How to find minimum number of k-input LUTs needed to express a n variable boolean function?

An k-input LUT (look up table) takes in atmost k-inputs and gives 1 output (which is a function of the k inputs). I need to devise an algorithm to find the minimum number of k-input LUT's required to ...
3
votes
1answer
858 views

Can we create faster sort algorithm than O(N log N)

I was thinking that we can create algorithm for sorting that will work faster than $O(N\log N)$ Let's say we have given array $A$ consisting of $N$ integers, where $N = 10^6$. Our task is to sort ...
1
vote
1answer
286 views

Why in simulated annealing, thermal equilibrium need to be meet for each temperature throughout the iterations?

I have read in this book, simulated annealing, on page 40-41, if temperature $t$ tend to $0$, then the stationary distribution will be distributed among optimal solutions. What i can not understand ...
4
votes
1answer
118 views

Maximizing number of selected squares in a grid

We have an $n\times n$ grid of squares, each square has a non-negative integer. Two distinct squares are neighbours if they share a row or column. A selection of squares is good if every selected ...
1
vote
1answer
435 views

Interval schedule maximization when encountering intervals with equivalent end points

In interval scheduling, the greedy solution which maximizes the schedule that contains the largest number of "compliant intervals" involves initially sorting the list of intervals in ascending order ...
4
votes
2answers
2k views

Knight on a chessboard

This is a Hackerrank challenge $Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x_1, y_1)$ to $(x_2, y_2)$ ...
2
votes
1answer
46 views

Identifying set of longest time periods excluding overlapping time ranages

Suppose I have set of time records as follows 08:00 - 12:00 10:00 - 12:00 08:00 - 13:00 13:00 - 19:00 12:00 - 17:00 Now I want to select set of time records that ...
3
votes
2answers
99 views

Algorithm for arranging elements into different sized buckets

I have a set of items. For each item, there is a list of buyers I can sell it to and a corresponding price they will pay me. For example: ...
1
vote
0answers
38 views

Update model parameter with new data, discarding old data

I have this dataset, and I am using y = (a * x^n) / (b + x^n) Hill function as the model, where a is the limit of the Hill curve,...
7
votes
0answers
181 views

Algorithms for curve construction

I am interested in algorithms that construct continuous curves between two points in such a way that minimizes an energy functional of the curve. What sort of algorithms are most used for such tasks? ...
5
votes
2answers
1k views

Finding k-nearest neighbors to a set of nodes in a large graph

Given a large graph $G=(V,E)$, a set of nodes $S\subseteq V$, the problem is finding the $k$-nearest nodes in $V$ to the nodes in $S$. Given a pair of nodes $(u,v)$, the distance $d(u,v)$ between $u$ ...
2
votes
1answer
40 views

Choose N pairs of (job, time slot) with a constraint on the number of different jobs

I am making a solver to choose the best assignment to a set of people for an event, given their availability (chosen in a set $T$ of time slots), jobs preferences (among $J$ possible jobs) and some of ...
3
votes
1answer
94 views

Globally-optimized nearest neighbors lookup

I have a set $\mathcal{A}$ of $\mathcal{m}$ vectors in $\mathbb{R}^a$. I also have a different set $\mathcal{B}$ of $\mathcal{n}$ vectors in $\mathbb{R}^a$. These two sets are disjoint: $\mathcal{A}\...
0
votes
1answer
122 views

how to express an intertemporal implication constraint in integer linear programming (ILP)?

I want to express the following locigal expression in an IP: $$x_{di} \wedge x_{d'j} \Rightarrow \sum_{\substack{d'' \in D\\ i < k <j}} x_{d''k} = \sum_{i<k<j} a_{k} \ \forall \ d, d' \in ...
0
votes
1answer
54 views

Minimum difference of sums

So hey, I've recently found this problem online and I tried hard to solve but couldn't found an efficient solution. The problem statement is: Given and two integers $n$ and $k$ and an array $A$ ...
1
vote
1answer
856 views

Dynamic Programming to Maximize Profit

I have this problem to resolve in dynamic programming: An ice cream shop owner has 4 stores. To meet the demand in the summer he purchased 7 refrigerators for the ice cream. Because the stores are ...
2
votes
1answer
31 views

number of subsegments that contain A[i] as the minimum

I've recently been thinking about this problem. Given an array $A$ containing $n$ integers and an index $i$, find the number of subgements of $A$ containing $A[i]$ as their minimum. To better ...
2
votes
2answers
598 views

Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?

Problem statement: You are in an infinite 2D grid where you can move in any of the 8 directions : ...
4
votes
1answer
357 views

Definition of $\alpha$-approximation

I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation. Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if ...
1
vote
1answer
85 views

Optimal covering of 2D matrix elements given spatial constraints

I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction. I've ...
1
vote
1answer
196 views

What algorithm to use, least waste when sawing wood planks

Lets say we have two wooden planks each 1m long. And we want to have 4 pieces, 60cm 30cm 50cm and 20cm. Is there an algorithm for calculating the least waste? When using brute force it quickly ...
0
votes
1answer
82 views

Sorting the number sequence

I have $4$ variables $n_1, n_2, n_3, n_4 \in \mathbb N$ that sum to $N$. $4$ positive real constants $c_1 < c_2 < c_3 < c_4$. Given a particular tuple $(k_1,k_2,k_3,k_4)$, how do I find ...
0
votes
2answers
156 views

Maximizing product of list of integers whose sum equals n

Given a positive integer n, find the list of positive integers whose product is the largest among all the list whose sum is n. For example, if n is 4 the desired list is 2,2 because 2x2 = 4 is larger ...
0
votes
1answer
156 views

Ant colony optimization algorithm

if i have an equation like $$f_n = x + y + z + a + b$$ and each variable has a discrete answer like $a = 0, 1 , 3$ . $b = 2 ,4,5$ etc. i want to find the global optimum minimization point....
1
vote
1answer
78 views

Can all optimizations be expressed in source code?

If someone compiled a program with all optimization settings enabled, would it be possible to create source code that, if it was compiled with all optimizations disabled, produced an identical binary? ...
3
votes
2answers
321 views

Find non-overlapping subsets that maximize the sum of their values

Given a set of elements $N$, a set $S$ of subsets of $N$, and a function $v:S \to \mathbb R$, determine a set $R\subseteq S$ of non-overlapping subsets that maximizes the total value. Has this ...
3
votes
1answer
114 views

Algorithm to mimimally pair up points in 3D space

Given a set of $n$ points $P$ and a set of $n$ points $Q$ in 3 dimensional space, what's the fastest algorithm to uniquely pair points in $P$ with points in $Q$ so that the sum of the square of the ...