# Questions tagged [optimization]

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

1,211 questions
Filter by
Sorted by
Tagged with
152 views

### Overlap Maximization problem

Here's the problem: I have a collection of collections, $C$, where each $c\in C$ is a collection of sets $X\subset U$. Denote $c_i$ as the i-th $X$ in $c$. Informally, I want to map all the sets in ...
103 views

### Finding the required value of an algebric expression

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$. I want to find the ...
82 views

### Issues with an optimization problem

I have an expression $$Ax+By+Cz.$$ where $A$, $B$ and $C$ are positive constants $\ge1$. The variables $x$, $y$ and $z$ are non-negative integers. I am also given a number $T$. I want to find the ...
1k views

### NP complete problems that are solvable in polynomial time if the input (e.g. number of variables) is fixed?

I have seen some problems that are NP-hard but polynomially solvable in fixed dimension. Examples, I think, are Knapsack that is polynomial time solvable if the number of items is fixed and Integer ...
569 views

### Finding the largest 3-clique-free induced subgraph

Consider this problem: Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that: $G'$ is an induced subgraph of $G$ $G'$ has no 3-cliques $|V'|$ is maximal So the ...
87 views

### Algorithm for finding optimal branch points

I'm developing software to run variations on a base process flow (see #1, below). A user specifies in a text file what steps in the process to modify. Because each step takes a long time to run, I'd ...
55 views

### What is the name of the optimization that removes self eliminating multiplication-division statements?

I have a compiler optimization which should be quite common, but I can not find a name for it, nor a reference that describes it. Given an integer x, not known at optimization time, a known constant ...
587 views

174 views

### Experimental Survey on Different Heuristics for Knapsack Problem

I am looking for a good survey/study of experimental results of heuristics for Knapsack problem (or implemented libraries in java/c++). Any help is appreciated!
75 views

### Convex optimisation under linear inequality constraints

What are the fastest known algorithms for general convex optimisation under linear inequality constraints?
989 views

### Convergence of Simulated Annealing Based Algorithms

I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge ...
913 views

### Dynamic Knapsack Problem - Algorithms and References

I don't know the right name for this problem, or if there is a name, but it is inspired by my initial interpretation of the title of this question (my question is very different, so the link may be ...
76 views

### Algorithms to prioritize equipment renewals

I am looking for algorithms to prioritize equipment renewals. Input: (years since last renewal, cost of renewal, importance of renewal). Output: An ordering of the equipment according to which it ...
1k views

### Find maximum distance between elements given constraints on some

I have a list of numbered elements 1 to N that fit into positions on a number line starting with 1. I also have constraints for these elements: The element 1 is in position 1, and element N must be ...
470 views

### Using Clique decision to solve Clique optimization

How can you perform the clique decision algorithm fewer than $O(n)$ times to solve clique optimization? I'm not sure if my approach is right but this is my thought process: you would pick vertices ...
549 views

### Randomized Rounding of Solutions to Linear Programs

Integer linear programming (ILP) is an incredibly powerful tool in combinatorial optimization. If we can formulate some problem as an instance of an ILP then solvers are guaranteed to find the global ...
32 views

### Inferences about Branching in TSP algorithm

I am building a program that uses branching-and-bounding to find an optimal path in a complete graph (the heuristic, faster algorithm is the second part). I have to begin and end at node 0. I was ...
920 views

692 views

### Minimum vertex-weight directed spanning tree where the weight function depends on the tree

Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$. The weight function assigns a non-...
1k views

### How to implement the details of shotgun hill climbing to make it effective?

I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems ...
2k views

### Optimization problem vs decision problem - reduction

Assume we have an optimization problem with function $f$ to maximize. Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to ...
50 views

### Produce decision version of the problem

An optimisation problem requires minimising some function $f(x)$, where $x$ is a vector of integers. What is the corresponding decision version of the problem?
688 views

330 views

### In s-t directed graph, how to find many small cuts?

Solving the maximum flow problem yields one qualified minimal cut. But I want several (maybe hundreds) small cuts as candidates. The cuts don't have to be minimum cuts, as long as they are small (in ...
557 views

### Minimizing the total variation of a sequence of discrete choices

My setup is something like this: I have a sequence of sets of integers $C_i (1\leq i\leq n)$, with $|C_i|$ relatively small - on the order of four or five items for all $i$. I want to choose a ...
1k views

### How to use dynamic programming to solve this?

Here is the question: suppose we are given x cents, the amount we want to pay, and a 6-tuple (p, n, d, q, l, t) that represents respectively the number of pennies, nickels, dimes, quarters, loonies ...