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
7
votes
0answers
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 ...
1
vote
2answers
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 ...
2
votes
0answers
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 ...
7
votes
1answer
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 ...
8
votes
1answer
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 ...
2
votes
1answer
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 ...
2
votes
1answer
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 ...
4
votes
1answer
587 views

Minimizing a multivariate polynomial over the hyper-cube is NP-Hard

In an exercise I have to show that minimizing a multivariate polynomial with $n$ variables over the hyper-cube $H = \{ (x_1, \ldots, x_n) : 0 \leq x_i \leq 1 \}$ is NP-Hard. Formally, given $p(x_1, \...
14
votes
2answers
14k views

Initial temperature in simulated annealing algorithm

I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm. Is there any way ...
4
votes
1answer
151 views

Prize collecting steiner tree

I'm reading about the prize collecting steiner tree problem and an approximation algorithm that uses randomization to set a lower bound on the optimal solution (see Chapter 5.7 in The Design of ...
2
votes
0answers
110 views

Why are optimization problems always NP-hard and not NP-complete and what does this mean for other levels of the polynomial time hierarchy? [duplicate]

I have read that optimization problems cannot be $\mathcal{NP}$-complete, but are always classified as $\mathcal{NP}$-hard. When a problem is NP-complete, I know it is contained in $\mathcal{NP}$P. ...
4
votes
0answers
429 views

Variation of interval scheduling algorithm with several job categories, only one from each can be used

I have a problem similar to the interval scheduling algorithm. The differences are: The jobs have the same length. There are several categories of jobs and only one job from each category can be ...
2
votes
0answers
71 views

Throughput measure

I have to implement a limitation algorithm in order to avoid to reach a throughput limit imposed by the service I'm interacting with. The limit is specified as «N request over 1 day» where N is of ...
2
votes
2answers
589 views

Polynomial time reductions using binary search

There are many NP-complete decision problems that ask the question whether it holds for the optimal value that OPT=m (say bin packing asking whether all items of given sizes can fit into m bins of a ...
4
votes
2answers
162 views

Constraint violation and efficiency in search

It seems that (in a broad sense) two approaches can be utilized to produce an algorithm for solving various optimization problems: Start with a feasible solution and expand search until constraints ...
1
vote
1answer
2k views

Interval Scheduling Problem with more than One Resource

Consider the interval scheduling problem, see also here. In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest ...
11
votes
1answer
7k views

What algorithm would compute the maximum choices from two sets?

Given two vectors of integers of possibly unequal lengths, how can I determine the maximum result possible from accumulating choosing the maximum between corresponding pairs of numbers between the two ...
6
votes
1answer
232 views

Optimal partition of a set of pairs

Suppose we have a set $S = \{(a_1,b_1),...,(a_n,b_n)\}$ where $a_i < m$, $b_i = m-a_i$, $m \in \mathbb{Z}^{+}$, $m>2$ and $n$ is an even number greater than $3$. What is the most efficient ...
4
votes
1answer
78 views

Can one have a condition like this in semidefinite programming?

Is it possible to have the following condition in a semidefinite programming as a constraint? $ M= \left[ {\begin{array}{cc} a & \sqrt{u} \\ \sqrt{u}...
2
votes
0answers
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!
3
votes
0answers
75 views

Convex optimisation under linear inequality constraints

What are the fastest known algorithms for general convex optimisation under linear inequality constraints?
4
votes
2answers
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 ...
3
votes
0answers
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 ...
3
votes
2answers
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 ...
4
votes
1answer
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 ...
2
votes
1answer
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 ...
5
votes
2answers
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 ...
2
votes
0answers
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 ...
5
votes
1answer
920 views

Optimizing a strictly monotone function

I am looking for algorithms to optimize a strictly monotonic function $f$ such that $f(x) < y$ $f : [a,b] \longrightarrow [c,d] \qquad \text{where } [a,b] \subset {\mathbb N}, [c,d] \subset {\...
8
votes
0answers
608 views

Chained operations on sequences with two operators

Given a binary expresion tree, with addition and multiplication operations, how can we optimize it's evaluation? Can we learn from matrix chain multiplication? A generalization of matrix chain ...
3
votes
0answers
372 views

Cyclic coordinate method: how does it differ from Hook & Jeeves and Rosenbrock?

I have trouble understanding the cyclic coordinate method. How does it differ with the Hook and Jeeves method and the Rosenbrock method? From a past exam text: Describe the cyclic coordinate ...
2
votes
2answers
109 views

Optimization-factoring $\le_p$ Decision-factoring

Optimization factoring: Input: $N\in \mathbb{N}$ Output: All prime factors of $N$ Decision factoring: Input: $N, k\in \mathbb{N}$ Output: True iff $N$ has a prime factor of at most $k$ How can I ...
7
votes
2answers
242 views

Are monoids useful in optimization?

Many common operations are monoids. Haskell has leveraged this observation to make many higher-order functions more generic (Foldable being one example). There is ...
3
votes
0answers
44 views

A variant of the assignment problem (?) [duplicate]

Possible Duplicate: A variant of the Assignment Problem (Not a comp.scientist, but have the basic research. Please excuse me if I've overlooked anything obvious.) In my variant of the problem I ...
0
votes
1answer
1k views

Integer LP formulation and the existence of a solution

A film producer is seeking actors and investors for his new movie. There are $n$ available actors; actor $i$ charges $s_i$ dollars. For funding, there are $m$ available investors. Investor $j$ will ...
1
vote
0answers
120 views

Is it possible to analyse computation?

Take a Turing machine, with a terminating program, convert it to some representation of the machine which captures, in a lossless manner, its state as it performs the computation. So you have a ...
6
votes
2answers
918 views

A variant of the Assignment Problem

In my variant of the assignment problem I have a set $A$ of agents and a set (of possibly different cardinality) $T$ of tasks. Each agent needs to be assigned exactly $n$ or $n+1$ tasks, and each task ...
1
vote
0answers
69 views

How to reduce MaxUNSAT to MaxSAT in a (almost) direct way?

In question How to reduce MaxUNSAT to MaxSAT? I was asking, how to reduce the MaxUNSAT problem to MaxSAT. With help of the given answer I could give a polynomial reduction : $MaxUNSAT \leq ...
6
votes
0answers
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-...
7
votes
1answer
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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?
11
votes
0answers
688 views

Fast algorithm for max-convolution with concave functions?

I'm interested in a discrete max-convolution problem, which is to compute $$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$ for all values $c=0, \ldots, C$, where $x=(...
11
votes
2answers
1k views

Minimize the maximum component of a sum of vectors

I'd like to learn something about this optimization problem: For given non-negative whole numbers $a_{i,j,k}$, find a function $f$ minimizing the expression $$\max_k \sum_i a_{i,f(i),k}$$ An example ...
2
votes
2answers
3k views

Function Maximization in Java

I have a bivariate function like $ f(x,y) = \frac{1}{x^3 \sqrt{\pi}}. e^{\frac{2-x}{x^2}} . y^3 . e^{3.y \over 3-y} $ and I want to find its global maximum over a range of $ x \in [0, 200] \text{, ...
7
votes
1answer
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 ...
8
votes
2answers
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 ...
2
votes
2answers
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 ...
3
votes
1answer
463 views

Efficient bandwidth algorithm

Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario: Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
6
votes
2answers
120 views