# Questions tagged [optimization]

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

1,385 questions
Filter by
Sorted by
Tagged with
905 views

### Multiple matching in Maximum Flow problem?

I'm sorry if this has already been asked before, but I couldn't find any similar questions. The situation is as such: Assume there are x restaurants, each with a capacity q, and y people, each of ...
66 views

98 views

153 views

121 views

### Scheduling optimization problem in theta(n)

I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to ...
11 views

### What is the best way to identify highly performing groups?

I am currently working on a project that involves sorting people into groups based on their ability to work well with others. While it is a bit of a simplification, I have a problem that is ...
41 views

### What properties of a discrete function make it a theoretically useful objective function?

A few things to get out of the way first: I'm not asking what properties the function must have such that a global optimum exists, we assume that the objective function has a (possibly non-unique) ...
22 views

### Is there any good method to find if a grammar is optimal for a problem?

I've been thinking about grammatical evolution problems and how the grammar influences the algorithm performance. It came to my mind the huge impact that the grammar that you're using has in the time ...
17 views

### How to consider combinatorial optimization problem with multiple objectives?

I am considering a combinatorial optimization problem with two objectives. The two objectives have a trade-off between each other which means if I minimized the first objective alone it gives the ...
37 views

### In a LP problem Ax = b, how to solve for A instead of x?

I have a multi-objective linear programming problem of the form Ax = b, where A is a matrix and x and b are vectors. x is known, and I'm looking to minimise each row of b by solving for A. Constraints ...
15 views

### Bounding 0-1 matrix with k unique rows

Problem Statement: Suppose that I have a $0-1$ matrix $A$ (all of the entries are $0$ or $1$). I wish to find the tightest upper bound with $k$ many unique rows. To be more precise, let S denote the ...
25 views

### Is this the correct “standard form” of nonlinear programming (optimization) problem and if it is why it's in this form?

Rather a simple question I guess, though makes me wonder. The standard form I've found in the book (and on wiki) is something like this: $\min f(x)$ s.t. $h_i(x) = 0$ $g_i(x) \le 0$ Is this ...
47 views

### Maximum sum path in a matrix

Given a square matrix of size N X N (1 <= N <= 1000) containing positive and negative integers with absolute value not larger than 1000, we need to compute the greatest sum achievable by walking ...
24 views

### A version of TSP where there is a probability each node is visited?

A friend in industry proposed a problem to me. If you have a supply warehouse, you can treat each station with products as a node. Each node has a probability it will be visited by an employee working ...
15 views

### Lowest cost path(s) between source and destination that collects required items

I have an undirected graph where each vertex is given some items from a set of items. My goal is to find the lowest cost path from my source vertex to destination vertex while collecting all such ...
16 views

### Powells Method for 2 Variables?

This is my first question here, so if anyone has tips on how to improve it that would be great. I've been studying this youtube on Powells method and it looks like when we have a single variable we ...
50 views

### How to realize applicable meet-in-the-middle algorithm for 0-1 Knapsack?

I am now studying Knapsack Problem (KP), and find the Meet-in-the-middle algorithm described in Wikipedia a little unclear that, how to realize it in the theoretical time complexity of $O^*(2^{n/2})$? ...
59 views

### What is the best hash functions for millions of String keys?

I have a situation where there are a million Keys of type String and I want to use the Symbol table to store the key and the value. The problem that the retrieval process is too slow and I want to ...
30 views

### Does this problem have a formal name?

I have come across the following problem but am unable to understand the solution for it. Hence I would like to know if it has a formal name then, I can search for it and read about it in more detail. ...
35 views

### Buying ingredients for a cake from many different stores and need to minimise the number of stores - algorithm name?

So let's say I'm baking a cake and it has a few ingredients (including multiples): ingredients = {sugar, sugar, baking powder, chocolate, flour, egg, egg} I can ...
6 views

### Ant Colony Optimization on Maximum Partitioning Graphs with Supply and Demand

I'm still new to the field of Computer Science and I'm having trouble understanding this paper An ant colony optimization algorithm for partitioning graphs with supply and demand. Can I ask for a ...
17 views

### Search Space for Population Metaheuristic Optimization Problem

Given that x objects (repetition allowed) can be arranged into y configurations, and that the population size is N, I am uncertain as to whether the size of the search space is |S| = |(y^x) * N| or |S|...
30 views

### How would I make sure my compressed string has the smallest length possible?

I'm trying to make a function that takes a string and compresses the repeating blocks. The code I'm using is implemented in such a way that a single character like 'a' would be converted to '1(a)' ...
25 views

### Weighted interval set scheduling problem

Given a set of weighted intervals, the weighted interval scheduling problem is to select a subset of the intervals such that none of the intervals in the subset overlap and the sum of their weights is ...
19 views

### Need help optimizing an algorithm that's supposed to maximize the greatest common divisor of n elements by removing at most one element

Alright, first here's the text of the problem: You're given n bags of candies where the i-th bag contains a[i] candies and all numbers a[i] are in the segment [1,m]. You can choose a natural ...
31 views

### Dynamic programming algorithm to merge two lists maintaining relative order and minimizing cost between elements

So I have a problem in which I have two lists of physical exercises (routines) and I want to merge them such that the merged list maintains the relative order of the previous lists, so for example, if ...
15 views

### Use of Tabu search Algorithm for solving optimization problem

I am trying to solve a maximization problem using the Tabu search algorithm but there is no relevant code available on the internet. Any kind of sample code is highly appreciable. My function is F(...
35 views

### Maximum-density multiple-choice knapsack problem

I am looking for work done on solving a problem (specifically I'm looking for an approximation algorithm) which is very similar to a combination of two variations of the knapsack problem: maximum-...
30 views

### Solving NP problems : analogy between the SAT problem and the shortest path problem

in this 2minute-long video https://www.youtube.com/watch?v=TJ49N6WvT8M (pulled from a free udacity course on algorithms/theoretical computer sciences), whose purpose is to show how a SAT problem can ...
18 views

### ILP formulation question

How to formulate the following constraint in ILP? if i-1 <= x <= i+1 then y < 5 end if So basically if the x is ...
17 views

### algorithm for scheduling tasks based on constraints and feedback loop if possible

I have a list of recurring tasks (1k+ tasks) and I am trying to find a optimal scheduling given a shared constrained resource. In other respects the tasks are independent of each other Each task is ...
19 views

### Optimization Problem to Maximize Points Given Cost Constraints

I have 2 groups of items: A and B. Each item has an associated cost c i and points p i. I need to choose 3 items from group A, and 2 items from group B such that the sum of points of those 5 items is ...
28 views

### simple question about epsilon and estimation turing machines

i am getting really confused by it. i got to a point i had to calculate the lim when $n \rightarrow \infty$ for an optimization problem, and i got to the point that i had to calculate a fairly simple ...
16 views

### Duplicate dominating parents when using Deterministic Crowding in Genetic Algorithm

This is the pseudocode for using deterministic crowding: ...
53 views

### Integer Linear programming formulation if then condition

I want to create constraints such that I can implement the following condition: Let A be an integer variable >= 0 with an upper bound of 12 I want to introduce the following variable B also an ...
198 views

### Making Candies - HackerRank question - proof of optimality of a greedy approach

I stumbled across this question in HackerRank: Karl loves playing games on social networking sites. His current favorite is CandyMaker, where the goal is to make candies. Karl just started a ...
12 views

### Is there any case that using pipeline reduces throughput?

We know that one of the ways to make implementation more efficient is to use pipeline which is to process new data before completely finishing the previous ones. I want to know is there any case that ...
15 views

### Maximizing a sequence of items under order and pairwise restriction

Suppose I have a number of items $\{A ... Z$} which are ordered accordingly. Each item has an associated weight, for example $W_A$. Between all items, there's a criterion $c$ which determines whether ...
28 views

### Artificial ant colony algorithm for graph

let's assume we have ant at node $1$ and she has $\{2,3,4\}$ vertices. How do I compute which one she choose? I mean if the formula $p_{ij}(k)$ is the probability of $k$-th ant at node $i$ choose $j$ ...
54 views

### How to maximize $f$ while minimizing $g$ at the same time?

Lately, I have been dealing with a problem that I didn't know how to name it to solve it properly. The problem is as follow: let's assume that we have a set of elements $A$. And, we have two ...
17 views

### Relation between shape descriptors and featured connected component in matching problems

Hope I'm asking in the correct community, from the title, I need a clarification regarding the idea of dealing with 3d descriptor and featured connected components. I have this approach: model -> ...
30 views

### Schedule a Seminar in Minimum Time

There are t1, t2, t3,.....,tn topics which are to be scheduled in a building with c1,c2,c3,....ck halls. Members have already registered there interests on the topics, and they have liberty to choose ...
I am minimizing a scalar function $f$ which takes a $n$-dimensional vector input and outputs a scalar value. I have code that given an input $x$ will compute the output of $f(x)$ (a scalar), its ...