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
1answer
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 ...
0
votes
1answer
66 views

Array covering problem

Suppose that we have $N$ integer points on coordinate line: $X = \{x_1, ..., x_N\}$ and we have to add $M$ more points (their coordinates can be rational). Suppose that we chose some $Y = \{ y_1, ......
0
votes
1answer
173 views

A problem solved by weighted median

Given a set of $n$ points $p_1,p_2,\ldots,p_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x_1,x_2,\ldots,x_n$ (not necessarily in ...
0
votes
1answer
119 views

What is wrong with my LP exercise (longest path cost for a graph)

I have to do a linear programming exercise but i have some problems regarding the result. I have a graph with N nodes and E edges, that is not acyclic, and each edge is associated to a cost. I have ...
0
votes
1answer
482 views

Understanding the P2||CMax scheduling problem

I have a problem with understanding the $P_2 \mid \mid C_\max$ problem which is also known as Tasks Scheduling on Multiple Processors. In fact, in my case I need only one processor (but the problem ...
0
votes
1answer
80 views

O(n) time algorithm for maximum earnings

There are $n$ plates $p_1$ to $p_n$ each filled with money of value $a_1$ to $a_n$. You can take the money from one or more plates if the sum of the money in them is divisible by three. I need a $\...
0
votes
1answer
98 views

How to exclude all points adjacent to a given point from the feasible region of IP

Consider a basic integer program such as: $$\begin{align} \min_x & \quad c^Tx \\ \text{s.t.} & \quad Ax \leq b \\ &\quad x_i \in \{-100,\ldots,100\} \end{align} $$ where $x \in \mathbb{...
0
votes
2answers
1k views

find the optimal combination [closed]

Suppose I have these values with weights -- $$ x_1 = 2\\ x_2 = 4\\ x_3 = 5\\ $$ There is no negative or $0$ value. I need to find $2$ element subset with maximum value computed from a function $f(\...
0
votes
1answer
153 views

Check constraint under some condition in linear programming

I would like to minimize linear pseudo-boolean function $$\mathrm{obj} = \sum_i c_i \mathrm{sel}_i$$ subject to $$\sum_i c_i sel_i \geq \mathrm{Value} \qquad\qquad(1)$$ where $c_1,\dots c_5, \...
0
votes
1answer
103 views

How to reformulate my problem as a mixed-integer quadratic problem

I have an unknown $n$-dimensional vector $x$ whose analytical expression depends on the following sum $x = z + Ba$ where the vector $z$ and the matrix $B\in \mathbb{R}^{n\times s}$ are given. So the $...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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) ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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})$? ...
0
votes
3answers
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 ...
0
votes
0answers
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. ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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|...
0
votes
0answers
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)' ...
0
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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(...
0
votes
0answers
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-...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
0
votes
0answers
16 views

Duplicate dominating parents when using Deterministic Crowding in Genetic Algorithm

This is the pseudocode for using deterministic crowding: ...
0
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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$ ...
0
votes
0answers
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 ...
0
votes
0answers
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 -> ...
0
votes
0answers
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 ...
0
votes
0answers
20 views

How to model most optimized encoding of string data

Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation. I ...
0
votes
0answers
7 views

Efficiently populate a look-up table for a function over a range of arguments

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 ...