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.

Filter by
Sorted by
Tagged with
1
vote
1answer
15 views

Grokking pseudo-code for solution to gas station problem

I'm trying to grok the pseudo-code for the gas station problem (which I think we should start calling the charging station problem but that's a different story) given as Fill-Row in Fig. 1 in To Fill ...
0
votes
0answers
19 views

Knapsack Problem Via Column Generation

If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
0
votes
0answers
14 views

Fuse 3D-Points in Bundel Adjustment? [closed]

(Crossposting from here: https://softwareengineering.stackexchange.com/questions/399331/fuse-3d-points-in-bundel-adjustment) I'm actually implementing my own Pose-Estimation/- and -Refinement ...
1
vote
1answer
23 views

Minimum sum of two numbers formed from digits of two arrays

Given two arrays of digits, both of size $n$, $2 \le n \le 9$, form two separate numbers $n_1$ and $n_2$, so the difference $n_1 - n_2$ is positive and minimal, if multiple solutions are possible the ...
3
votes
1answer
25 views

Is unconstrained quadratic programming NP-hard?

I could not find the answer on the Internet. The case of quadratic programming with constraints is already solved on this forum, see Transforming SAT to Quadratic Programming in polynomial time. But ...
2
votes
1answer
46 views

Algorithm for dividing items into buckets while minimizing total weight

Let's say I have two buckets coloured red and blue, both of which can hold two rocks. I need to divide a set of $n$ weighted rocks into these buckets in such a way as to minimize the total weight of ...
0
votes
1answer
92 views

How to Optimise the following algorithm? maximum good value of an element in an array

I was recently stuck while doing a question, please suggest a way with a code/pseudo code to optimize the following algorithm for finding the maximum good value in an array where a good value of an ...
0
votes
0answers
39 views

Making change optimally

Consider that a currency system has $k$ denominations $d_0, d_1, ... d_{k-1}$. $d_0, d_1, ... d_{k-1}$ are such that $d_0 < d_1 < ... < d_{k-1}$ and $d_i$ divides $d_j$ for all $0<=i<j&...
1
vote
0answers
14 views

Is there a high-level framework from which all known search and optimization algorithms can be derived?

The fields of applied math and computer science are inundated with optimization algorithms, variations on those optimization algorithms, and variations on those variations. I'm mainly talking about ...
1
vote
1answer
23 views

Modifying the genetic algorithm

I have a multi-objective optimization problem (NP-complete). To solve it, I've decided to use the genetic algorithm. I have 3 "areas" of optimization, say parameters ...
1
vote
1answer
37 views

Is Newton's algorithm really this much better than conjugate gradient descent?

I have a function I'm minimizing. I'm using conjugate gradient descent and the Newton algorithm. I am experiencing that the Newton algorithm is absurdly faster. Like, it finishes it 5-6 iterations, ...
2
votes
1answer
25 views

Select certain number of column elements of a stochastic matrix, maximum one element per row

Consider a $m \times n$ Matrix. Every column represents a class and every row an observation. Every row/observation is a probability distribution, hence every row sums up to 1. We now want to choose ...
1
vote
1answer
29 views

Sorting algorithm for set of elements, when I have comparison of just some pairs not all of them

Is there some kind of algorithm for sorting of set, when there is comparison of just some pairs? Example 1: set(a, b, c, d, e) pairs(a>b, ce) Example 2: set(a, b, c, d, e) pairs(a>b, d>b, c>d, d>e)...
1
vote
0answers
32 views

About Steiner tree problem in graphs

In the paper (p. 3) and the slides presents the formulation of the Steiner problem on graphs via so called Steiner cuts. But according to the definition, the number of Steiner cuts and so the ...
0
votes
2answers
42 views

How to partition disagreeable people into compatible groups

We have a number of people that must be partitioned into groups, but there may be people that dislike other individuals. Partition the people into the minimum number of groups such that no person is ...
1
vote
2answers
22 views

How to effectively represent and generate 2D cellular automaton rules that are invariant under rotation and reflection of the input matrix?

Consider cellular automaton rules for a two-dimensional universe with two states, where a cell's new state can depend on its previous state and the states of the cells in its Moore neighborhood. Such ...
5
votes
2answers
120 views

If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems?

Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time. Now I am learning that a convex optimization problem can ...
1
vote
2answers
35 views

Algorithm Design: Efficient O(n) algorithm to get the ith to jth largest elements in an array

I am trying to design an efficient algorithm that retrieves the ith to jth largest elements in an array. For example, if the following array is the input: ...
1
vote
0answers
40 views

Max sum of k contiguous subarrays

The question is: given an array of size $n$ and a number $m$, now our goal is to find AT MOST $m$ contiguous subarrays such that the sum of all these subarrays is the largest. It is also required that ...
1
vote
1answer
55 views

How can I calculate the maximum sum/product of sequence?

I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\{ 1, 2, 3 , 4\}$) by inserting a plus ($+$) or ...
1
vote
1answer
17 views

Maximum-cardinality matching in unbalanced bipartite graphs

Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$. The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So ...
3
votes
1answer
19 views

Choosing which workers (limited number) to use in a binary assignment problem?

First of all, I am not completely sure whether this problem belong to the category of assignment problems so feel free to correct me in this case. The problem: We are given a set of $m$ workers $A = ...
6
votes
1answer
50 views

Perpendicular vectors out of a set

I stumbled on this problem and I wanna know if there is a better solution. There are $n$ 3d vectors with $x$, $y$, and $z$ components and I wanna find all pairs of perpendicular vectors in this set. ...
0
votes
0answers
44 views

Verifying the minimum cost from each node to a sink node in linear time

Problem Statement: Let $G= (V, E)$ be a directed graph with costs $c_e \in \mathbb{R}$ on each edge $e \in E$. There are no negative cycles in $G$. Suppose there is a sink node $t \in V$, and for ...
0
votes
0answers
25 views

Minimum amount of rectangles to create a 2-dimensional matrix

From this codegolf question. Consider an $r$ by $c$ matrix of nonnegative integers, called $M$. You also have a zero matrix of the same dimensions, called $N$. A "move" consists of replacing a ...
0
votes
0answers
10 views

Given we restrict the time and memory allowed what bounds can we place on a halting decider?

If a program is given as much memory and as much time to execute as it wants, then the halting problem is undecidable, and by Rice's theroem all non-trivial, semantic properties of programs like that ...
2
votes
0answers
33 views

Dynamic Program for this Weighted Possion-Binomial Problem?

Setup: Suppose we have $n$ independent Bernoulli random variables, say $\boldsymbol{X} = \{X_1, ..., X_n\}$ each with prior $\mathbb{P}(X_j = 1) = p_j$, and weights between $-1$ and $1$, say $W = \{...
2
votes
1answer
48 views

Minimal hitting set with respect to set inclusion from a book “Parameterized Complexity Theory”

In the first chapter of "Parameterized Complexity Theory" by Flum and Grohe, an example is presented to find a hitting set of minimal cardinality. In Fig. 1.3, the author says a black colored leaf ...
1
vote
1answer
47 views

Can an optimization algorithm be “universal”?

I am wondering if a Bayesian Optimization framework (e.g. Google's Vizier) can be used in lieu of a traditional solver like Gurobi or CPLEX. In trying to answer this question, I realized that I don'...
0
votes
1answer
28 views

Change the structure from 3SAT to 1in3 3SAT

There is a variable set V = {x1,x2,x3} and clause set C1={x1,x2,-x3} C2={x1,-x1,-x2} C3={-x1,-x2,x3} C4={x2,x3,-x3}. For this structure, no matter each variable is positive or negative, the clause can ...
1
vote
1answer
39 views

Intuition behind this specific algorithm for time series

Going through the EPI book and I need some help understanding this part. There's a problem, 5.7, that deals with buying and selling twice over a single time-series in order to maximise profit. The ...
-2
votes
1answer
25 views

Question about complexity of TSP Optimization problem

Is this statement true? Optimization TSP problems are known to be NP-hard, as we do not have a minimum cost to compare against, and in order to verify a solution is optimal, we need to iterate ...
2
votes
2answers
82 views

For what applications of the traveling salesman problem, does visiting each city at most once truely matter?

Traditionally, the traveling salesman problem has you visit a city at least once and at most once. However, if you were an actual traveling salesman, you would want the least cost route to visit each ...
1
vote
1answer
29 views

Student Course Allocation Problem with Many Constraints [closed]

Problem statement In an university, there are $t$ course categories, $m$ courses, $n$ sections, $p$ students. $i$-th section has: A student capacity: $cap_i$. Two lecture timings. (Formally, each ...
0
votes
0answers
19 views

How well do multi objective optimization algorithms such NSGAii scale when there are many objectives (for example 10 or more)?

What I'm trying to figure out is what happens when using a multi objective optimization algorithm such as NSGA-ii and instead of trying to find the usual 2/3 objectives, I use 10 or many more ...
0
votes
0answers
22 views

What is the difference between derivative free optimization and derivative optimization in terms of advantages/disadvantages?

I understand the basic operation of the algorithms however i'm unclear as to when to use one over the other and what advantages/disadvantages they offer over each other. Also as an aside, if anyone ...
0
votes
1answer
25 views

Looking for the name of this job scheduling algorithm

You have a list of jobs. Each job has a deadline and an associated profit if completed before the deadline. Also, each job takes 1 unit of time to complete, and only one job can be completed at any ...
0
votes
0answers
7 views

How to input random values (constraints) of any variables in case of formulating Linear Programming Problem?

Suppose, Min 2x+3y Subject to, x=2,x=5,x=7 y=5, y=9 is a linear program. Where x holds the values 2 or 5 or 7 and y holds the values 5 or 9. Then what should the correct ...
0
votes
1answer
23 views

Minimize same placed elements in a list of permutations (Heap)

I'm trying to optimize the permutations generated from a set of n elements. Here is the pitch: I have a set of 6 elements $\{1,2,3,4,5,6\}$ and I want to create 10 permutations. I could use Heap ...
1
vote
1answer
22 views

How to get to the efficient solution of a problem on buying with exchange policy

I was working through some coding challenges at hackerrank.com and got to this one. I understand the problem and how to solve it, but after solving it I searched for more solutions to improve mine. ...
0
votes
0answers
17 views

How to identify a continuous shape and break it into minimum number of rectangles?

The input in this case is going to be coordinates in 2D of the vertices of the shape. There will be no curves, but the shape can have holes. The algorithm or program needs to identify the continuous ...
0
votes
0answers
19 views

How is ellipsoid method a polynomial-time algorithm for LP?

I have always thought that the ellipsoid algorithm is an algorithm which can be used to solve LP in polynomial-time. However, what confuses me is the dependence on the ratio of volumes of the balls (...
1
vote
0answers
22 views

Circle fitting with fixed radius using algorithm by Chernov

I am doing a project where circle fitting is needed and I came across an algorithm and code found on the website (https://people.cas.uab.edu/~mosya/cl/CPPcircle.html) which works very well. My ...
0
votes
0answers
24 views

metaheuristics vs exact and traditional algorithms

Recently, my friend has submitted a paper and solved a problem with an exact method. Surprisingly, a reviewer asked him why he used an exact method instead of the popular metaheuristics algorithms! We ...
0
votes
0answers
8 views

Optimization palletizing and dispatch

I have the following situation: I have to find the most optimal days to palletize and to dispatch pallets to 22 different destination. The demand for each destination varies, ranging from 3 to 12 ...
0
votes
0answers
57 views

Is this variation of the assignment problem NP-hard, and does it have a name?

I’m trying to solve a problem very similar to the assignment problem, with a few twists. The problem has a certain amount of workers, and a certain amount of tasks - workers is always >= tasks. Each ...
0
votes
0answers
19 views

Creating a waste-optimizing algortihm for cutting a 1d block

I have a one-dimensional block of material. I run an analysis that divides the material into usable and unusable regions. In a manufacturing process, said material is cut and the unusable regions ...
0
votes
1answer
12 views

Is this a good way of generating diverse solutions to a problem using a genetic algorithm?

Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values ...
1
vote
0answers
31 views

Minimize number of math operation of a specific matrix vector multiplication?

Let's say we have a Matrix M and a column vector v like below multiply equals Assume we can only perform multiplication, addition and substraction operation. With normal approach we need 3 ...
1
vote
0answers
84 views

Time Complexity of Binary Linear Programming

As far as I know, Integer Linear Programming(ILP) problem is NP-complete. According to the following paper, Binary Linear Programming problem(BLP) can be solved in Polynomial time. http://dx.doi.org/...