# Questions tagged [optimization]

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

1,435 questions
Filter by
Sorted by
Tagged with
13 views

### Find sets of weighted objects to maximize number of sets with weight >= X

I have N objects, each of which has a weight. I need to form combinations of the objects to maximize how many sets of objects add up to at least x total weight. Combinations can consist of any number ...
15 views

### Approximate LP for vertex cover problem

I am studying the topic of vertex cover on coursera and how it can be solved approximately by linear programming. Suppose the optimal solution for the vertex cover problem is $OPT$. I do not ...
23 views

### Min weighted edge cover - is the greedy algorithm sub-optimal?

The post here: Solving the min edge cover using the maximum matching algorithm provides a way to obtain the min edge cover from a maximum matching by greedily adding edges on top of the maximum ...
23 views

### Algorithm for finding shortest set of paths through a weighted DAG (?)

Short version What algoithm can find an optimal (or near optimal) solution to the following problem? Given the following: a weighted DAG, with one start node (only has outgoing edges) and one end ...
15 views

### What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it. Here is the problem: A company is in ...
22 views

### Find exact sum in path

So the question is Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. You can only move down and to ...
34 views

### How does AlphaGo perform when increasing the size of the board?

I recently watched AlphaGo, a documentary on the recent defeat by the best human player of Go by a computer, AlphaGo. The commentary the beginning points out this was ten years ahead of schedule (...
21 views

### Subset selection with maximum sum and minimum variance?

So I am trying to tackle a combinatorial optimization problem and would like some insights on how to approach it. The problem statement is as follows: Consider a set of elements of size N, how do I ...
44 views

### Graph coloring with fixed-size color classes

I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to minimize the number ...
53 views

### Monte Carlo tree search optimizations

I am designing a algoritm for a game using a Monte Carlo tree search AI that I implemented. I play against another player and want to get the best move. Every time I do a move I completely build a new ...
14 views

### Messy Representation Encoding example

I am currently working through Metaheuristics by El-Ghazali Talbi where he discusses encodings of algorithms. "Messy representations: In linear representations of fixed length, the semantics of ...
75 views

### Classify an algorithm to maximize number of tips used by liquid handlers concurrently

I'm looking for suggestions on algorithms, data structures or at least problems (so that I look for solutions in that domain) to consider. I realize that exact solution probably doesn't exist. But the ...
26 views

### Optimise the size of union of sets

We consider a set of sets $S = \{S_1, S_2, \dots, S_n\}$, and we want to find a subset $I$ of $S$ that maximises the size of the union of the set $S_i$ included with a penalty for each set included. ...
50 views

### Loop optimization of non-tail recursion

When researching how to optimize recursion into loops, I came upon (on Wikipedia) a general rule about this: Whenever a function is in form: ...
32 views

### How to understand the solution to Task Scheduler problem on LeetCode?

LeetCode Task Scheduler problem is the following: Given a characters array tasks, representing the tasks a CPU needs to do, where each letter represents a different task. Tasks could be done in any ...
14 views

### How to predict the number of patients from the number of diagnoses

I have data on the diagnostic measures that individual patients received that year. For that individual data, I would like to make a prediction of how many such patients are in the country.　To do so, ...
9 views

### How to combine multiple Boolean Functions in CDNF efficiently for implementation on a CPU?

I am trying to see how fast I can implement a 6-bits to 6-bites lookup table. Generally, I am attempting to do this by using the common method mentioned in CS textbooks of using the Quine-McCluskey ...
148 views

### Strong polynomial time algorithm for deciding LP feasibility

Let $$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
37 views

### 0-1 Knapsack problem with item discounts

I recently encountered this kind of problem in a real world setting, and could not for the sake of me find any literature relating to the problem statement I came up with. An example will be included ...
13 views

### Dynamic Chromosome Length in Genetic Algorithms

My inquiry concerns the length of chromosomes employed in genetic algorithms (GA), and more broadly in other classes of evolutionary algorithms. The chromosome length is fixed throughout a GA's run. ...
12 views

### Encoding a lot of categorical variables

I have 10 million categorical variables (each variable has 3 categories). What is the best way to encode these 10 million variables to train a deep learning model on them? (If I use one hot encoding, ...
28 views

### Maximize the minimum gap while scheduling within intervals?

Problem There are N intervals in which a particular integer can be chosen. What is the maximum possible minimum gap between each integer if one integer is chosen for each of those intervals? For ...
48 views

### Parall execution of algorithms that solves polynomically disjoint subsets each of a NP-hard problem

I was thinking in the following approach for solving a problem that is believe to be a NP-hard problems today in polynomial time, assuming the following: There exists a believed-today NP-hard problem ...
22 views

### Polynomial-time algorithm to solve the maximum vertex bipartite subgraph problem

I'm trying to find an algorithm that solves the maximum vertex biclique problem. I know that that algorithm can be solved in polynomial time (in contrast with the maximum edge biclique problem, which ...
22 views

### In a set of sentences, how could I determine the fewest sentences that contains all characters?

So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced. So ...
64 views

### Optimising an exhaustive search for a card game

I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an ...
34 views

### If a poly-time solution exists for an NP-Complete (Decision) problem, then there exists a poly-time solution for the NP-hard (Optimization) flavor?

This question boils down to: If a polynomial time solution exists for a decision problem, is there also a polynomial time solution for the same problems optimization flavor? Let's take the Traveling ...
13 views

### What are all local optima of the six-hump camel back function?

This is a famous function to test optimization heuristics such as genetic algorithms and others. The 2 global optima are described clearly in many webpages, but surprisingly I'm unable to find any ...
38 views

### offline Bin Packing problem with multiple size bins

As per my research on stack overflow communities, This is probably known as cutting stock problem / multiple Knapsack problem (a variant of the bin packing problem) which is NP hard. here are the ...
47 views

### Why does a kalman filter work better in a simulation than in real life?

I am trying to use a classical Kalman filter for getting indoor location. I am using geolocation API of HTML to get latitude, longitude, position accuracy and speed. I am also using the smartphone's ...
18 views

### How to justify the choice of using a specific metaheuristic?

For a problem how to justify the use of a metaheuristic upon another? For exemple for scheduling problem, could the same heuristic be efficient for different variants of the problem? What are the ...
35 views

### Maximization problem

I work at a company and i got to a seminar we're they told us to solve this problem below in the picture Is there an algorithm that can help me solve this question. I thought about a randomized ...
38 views

### Algorithm for maximizing the number of same-sized groups

Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the ...
30 views

### Find maximal subset with interesting weight function

You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th ...
31 views

### How important is initial state for local search optimisation?

I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation. I'm wondering how important the ...
26 views

### Search for range in continuous function satisfying some condition

I am attempting to define an optimization for the following problem: given a graph find the largest interval(s) where S > S_th (the narrower the interval the ...
18 views

63 views

### How to convert a recursive function to a non recursive one using stack while keeping memoization?

Let's say I want to count the number of ways a string can be decoded, once encoding algorithm follows this map: 'a'=>'1', 'b'=>'2', ... 'z'=>'26'. I could ...
256 views

### efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
42 views

### What is the largest sum that can be constructed with the given recipes?

There are $n$ sets of distinct positive integers, $S_1,\ldots,S_n$. There is a set of recipes that allows us to construct tuples of integers from these sets. For example, the recipe {1,2} allows us to ...
23 views

### How to linearly combine loss functions to preserve optimal substructure property?

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
18 views

### Minimizing the length a Boolean Algebra Expression in disjunctive normal form

I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
45 views

### Repeated linear programming with similar (not identical) problems

I have multiple linear programming problems of the form: $$Minimize\{c^{T}\cdot x\} s.t. Ax = b, x \ge 0$$ Where $c$ and $A$ are fixed for all the problems. Is there any way to utilize that for a ...
45 views

### Algorithm for summation with lowest maximum temporary sum

I've got this problem on my last exam, which I struggle to deal with. Let's say we have array of $N$ integers (it can be float too, but let's say integers for sake of simplicity. We need to sum those ...
34 views

### Approximation factor preserving reduction

The definition of approximation factor preserving reduction from the book by Vijay V. Vazirani, page 365: Let $\Pi_1$ and $\Pi_2$ be two minimization problems, an approximation factor preserving ...
73 views

### Minimum vertex cover and odd cycles [closed]

Suppose we have a graph $G$. Consider the minimum vertex cover problem of $G$ formulated as a linear programming problem, that is for each vertex $v_{i}$ we have the variable $x_{i}$, for each edge \$...
40 views

### Is MAX-averageSAT a well-known problem?

Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an ...