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

Implementing a job-scheduling problem with multiple dependencies and variable tasks (time frames) using dynamic programming

I'm writing a "Chores Scheduler" in Python. It has to be implemented using dynamic programming and has to take in two types of chores, as below: Regular chores with a start time and end time (a real-...
2
votes
0answers
48 views

Maximizing the product of a set of dot products

So suppose we have a set of vectors $X$ and we want to approximate the maximum of the following: $\prod_{x \in X} b \cdot x$ where the components of $b$ sum to $1$ If it matters the components of ...
0
votes
0answers
54 views

A scheduling problem on an oriented graph with multiple constraints

The problem is the following : Data An oriented graph $(V, E)$ : to be understood as a set of partially ordered tasks A map $d: V -> \mathbb{N}$ : to be understood a function mapping tasks to a ...
0
votes
0answers
15 views

Confused between different Structure from Motion pipelines

What is the difference between Global SfM, Incremental SfM, Sequential SfM, Progressive SfM and VSLAM (Visual Simultaneous Localization and Mapping). Is sequential SfM the same as VSLAM ? I have tried ...
3
votes
1answer
48 views

shortest form $s$ to $t$ stopping at $u$

Suppose you want to go from vertex $s$ to vertex $t$ in an unweighted graph $(V, E)$, but you would like to stop by vextex $u$ if it is possible to do so without increasing the length of your path by ...
1
vote
1answer
132 views

Tree traversal with conditional summing values from nodes

Hi all i have algorithmic problem and i struggle with finding optimal solution. I have tree which i want to traverse. Nodes of the tree consist of value and a rank of node (value as well as rank can ...
6
votes
2answers
143 views

Which algorithm can I use to allocate human resources?

I have to manage shifts of a variable number of people inside several rooms for a week. Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same ...
2
votes
0answers
100 views

Join Order Optimization

Consider the join: (σtitle=Overwatch Game)⨝ Event ⨝ rating ⨝ Player What is the optimal join order? Based on the schema on the following picture: I am suppoused (and that's what I tried) to use ...
2
votes
1answer
373 views

Finding the largest possible area covered by M rectangle under a given histogram

Finding the largest rectangular area possible in a given histogram is a well-known problem and have linear solution. I have a similar but different problem. In my problem, we have $M$ rectangles ...
1
vote
1answer
57 views

Image registration using gradient descent

I have a target image $f(x,y)$ (where $x \in [0, 250]$ and $y \in [0,300]$), and a source image $g(x,y)$ I want to align $g$ to $f$ using the transformation : $$\Psi(x,y;t_x, t_y, \theta) = \begin{...
9
votes
2answers
175 views

Find an optimal ordering

I came across this problem and am struggling to find a way to approach it. Any thoughts would be greatly appreciated! Suppose we are given a matrix $\{-1, 0, 1\}^{n\ \times\ k} $, for example, ...
2
votes
2answers
35 views

What does Stroustrup mean by 7/8ths of MIPS being in the vector units?

In his article Software Development for Infrastructure Stroustrup states the following: Hardware improvements make the problems and costs resulting from isolating software from hardware far worse ...
0
votes
1answer
47 views

How to judge the searching precision of Particle Swarm Optimization?

As the title mentioned, how can I judge the searching precision of PSO? Is this depending on the velocity of the particles? I would like to give an example to clarify my question: For a 2-D searching, ...
1
vote
1answer
37 views

Turing Machine where branches are resolved via arbitrary operator

Alternating Turing Machines output Boolean values and combine the values returned by branches via the any/all operators. Is ...
1
vote
1answer
19 views

Selection of dates respecting delay constraints

I encountered an issue at work that can be derived approximatively to this problem. Let say we have a machine that can be triggered to instantly do an action. There are several (between 10 to 15) ...
2
votes
0answers
115 views

Sub-optimal and fast solutions to assignment problem

I am looking for a fast solution to the assignment problem for large cost matrices (5000x5000 or larger). The Hungarian algorithm is $O^3$, which is impractical for any moderately large problem. Are ...
0
votes
0answers
28 views

Greedy Approach without constraint and a feasibility function

We know that the Greedy Approach in general, picks an element from a set of candidate elements that satisfies a predefined criteria (selection function) and is added to the solution if it satisfies ...
1
vote
0answers
28 views

How to optimize the return given the stock price of all time?

There is a list of N stocks. In M days, the stock price is given. Assume that each stock has only 1 price per day. Assume that ...
0
votes
0answers
27 views

Optimize an underdetermined system with quartic constraints

I encountered an optimization problem which does not belong to any well-known category of optimization. The system has $M$ (typically $M=120$) real variables and $N$ (typically $N=100$) constraints (...
2
votes
0answers
39 views

Using exponential penalty functions in constrained nonlinear optimization

Background: penalty functions Penalty functions convert a constrained optimization problem \begin{equation}\begin{split} \text{minimize} \quad & f(x) \\ \text{subject to} \quad & g(x) \leq 0 ...
0
votes
0answers
138 views

Travelling Salesman problem using Guided Local Search

I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/ stuck in solving TSP. As there are a lot of methods to solve this problem, I am currently coding Guided Local Search as ...
1
vote
0answers
35 views

$n$ machines, $n$ types of jobs with $q_j$ jobs, minimizing the cost

I have this problem A firm has $q_j$ jobs of type $j$, where $1 \leq j \leq n$. It also has $[n] = {1,2,...n}$ machines. Machine $i$ can service any job of type $j$ where $j ≤ i$. The cost of ...
2
votes
2answers
80 views

Recursion to DP Solution

There's a problem in Kleinberg & Tardos's Algorithm Design (Chapter 6, Question 4) where you are running a lightweight consulting business that has two offices: NYC and SF. In month $i$, you'll ...
1
vote
0answers
49 views

Finding the best state for chain graph with cycles

I have a chain graph like in the picture. Each node of the graph has finite possible labels, i.e. states, which define the node's weight(non-negative) as well as the internode weight(also non-negative)...
2
votes
1answer
41 views

List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
0
votes
0answers
59 views

Resource allocation / optimization

At work I stumbled across this problem of allocating resources: We are given a set of objects belonging to one of seven possible classes (multiple objects per class are allowed). We distinguish ...
1
vote
1answer
48 views

Evolutionary optimisation algorithm and graph based search

Simulated annealing and genetic algorithm are examples of evolutionary optimisation algorithms. Both of these methods entail doing a search on a graph of candidate solutions. Do all other evolutionary ...
1
vote
1answer
76 views

Finding Conflict algorithm doubt

Let $e_1,e_2,\cdots,e_n$ are some events are given by their starting time and ending time. I have to find an event that conflict with maximum number of other events. Conflicts means interval ...
1
vote
0answers
70 views

Solving the Size-Constrained Weighted Set Cover Problem

I'm wondering if anyone has experience trying to solve a weighted set cover problem over the power set (i.e. all possible subsets) of an $n$-element ground set where the number of sets included in the ...
4
votes
2answers
122 views

Run-time of Hungarian algorithm - matrix formulation

There are many different explanations of the Hungarian algorithm. My favorite explanation is the one based on matrices, for example here, since it is very intuitive and easy to carry out in a ...
1
vote
0answers
94 views

Closest Value instead of Max Value in Knapsack problem

I have a problem like the knapsack problem, except instead of finding the max value, I'm trying to find the closest value to a given value. Anyone know where to start, have a name for this problem, ...
6
votes
1answer
129 views

Optimal partitioning of n-tuples

Motivation Recently I was trying to optimize some API calls and reduced the problem to optimization of a cumulative number of identifiers across all the requests. I put some considerable effort into ...
1
vote
1answer
18 views

Bounds on “well dispersed” sparse matrices

Suppose we have an $n\times n$ zero/one matrix $M$, with $k$ ones. Let us say that the extent of $M$ is the maximum of $i+j$ over all ones at positions $(i,j)$ of the matrix, and the quality $q(M)$ is ...
1
vote
1answer
77 views

Finding optimal multiplication order and optimal binary tree

I have to determine the Optimal Multiplication Order for above matrices using Dynamic Programming approach and also present that sequence (i.e. optimal order) in Binary Tree. Consider the following ...
1
vote
1answer
42 views

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached

Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached. I thought to run an SCC algorithm to find binding ...
0
votes
1answer
85 views

Maximum flow with constraints

In a flow network, suppose we add constraints of the following type: The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$. Is maximum-flow with such constraints still ...
1
vote
0answers
15 views

Does Quadratically-Constrainted Quadratic Programming get easier if all constraints are equalities?

A Quadratically-Constrainted Quadratic Program consists of optimizing a quadratic objective function while imposing quadratic constraints, which can be inequalities or equalities. Obviously, ...
0
votes
3answers
58 views

Which is better ? Iterations or Recursions?

I've heard that any algorithm using iterations can be changed into one that uses recursions and vice-versa. But which type of repetition is preferable for minimum amount of computational effort and ...
2
votes
1answer
21 views

If you have a smallest grammar approximation, do you immediately have a CFG inference algorithm?

The smallest grammar problem is to find a single-string CFG. So given a finite list of language samples, known to all lie in some CFG, can we, using the smallest grammars (approximated) of each ...
0
votes
0answers
25 views

what can cause the best-bound to get tighter in the first MIP node?

I'm using gurobi MIP optimization engine for solving a mixed integer linear minimization problem. I see that the engine didn't start the branch and bound stage ...
0
votes
1answer
24 views

Kiln optimization problem

Say I have a kiln for making castings. There are 3 shapes. I need to produce the following castings: 102 of A 364 of B 70 of C I can put 50 molds in the kiln at a time. I can have 75 molds made in ...
0
votes
0answers
9 views

Clarification on descending direction in optimization of function

Could someone clarify for me why given $f:\mathbb{R}^n \rightarrow\mathbb{R}$ to optimize an iterative function according to : $p^k=-M\nabla f(x^k)$ for $p^k$ to be descending direction the matrix M ...
0
votes
0answers
7 views

What analysis / algorithm helps stabilizing the fit of correlated parameters (but not colinear)?

I have many curves that I want to fit using a convolution of some functions. These functions include Weibull distributions with 2 parameters lambda and ...
0
votes
0answers
10 views

Most probable inputs assignment in Gaussian process

Given A Guassian process $w(\mu^*,\Sigma^*)$ $n$ observations of the output And $n$ potential inputs. But the assignment of the inputs to the observations is unknown. The goal is to find a inputs-...
1
vote
0answers
14 views

Disk Scheduling for a Fragmented Hard-Drive

Recently In class I have been learning about simple disk scheduling algorithms such as FCFS, STTF, LOOK, LOOK-SCAN etc. From my understanding these algorithms schedule I/O requests depending on which ...
3
votes
2answers
74 views

Is it possible to solve this problem in less than n^2 time without using additional space?

Here's the problem: Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
0
votes
0answers
29 views

University timetable optimisation - with a twist

I've made a website that helps students at my university optimise their student timetables. Currently, for subjects with not many classes - I can generate and optimise the timetables quite fast. ...
1
vote
0answers
38 views

Optimizing library dimensions

Say I have a library that looks like that: ...
0
votes
0answers
36 views

Branch and bound Dual Gap

Let's suppose we want to solve the knapsack problem using the Branch and Bound algorithm. I know that the algorithm ends when the optimality gap is = 0. However i have not understood how the dual ...
1
vote
1answer
34 views

How fast can we optimally cluster 1-D data?

K-means clustering is the problem of partitioning a set of points in a metric space into $k$ sets (clusters), such that the sum of squared distances between each point and the center of its cluster) ...