Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [optimization]

general questions about selecting a best element from some set of available alternatives.

8
votes
1answer
303 views

On which classes of graphs is resource constrained shortest path (RCSP) NP-hard?

I'm looking to link a problem I'm working on to a known NP-hard problem. I think I can model my problem as a resource constrained shortest path problem. However, the structure of my graph is not ...
0
votes
1answer
609 views

Maximizing strictly increasing convex function

Let the objective be to maximize the sum of $f_i(x_i)$ where all $f_i$ are strictly increasing convex functions. Maximizing a convex function is hard as a local maximum might not be a global one. ...
8
votes
0answers
686 views

Is this minimization problem NP-Complete?

We are given an $n \times (n + k)$ matrix $A$, with entries in GF(2), of the form $A =[I_n\ B]$, where $I_n$ is the $n \times n$ identity matrix, and $B$ has no "zero" rows or columns. The problem is ...
5
votes
1answer
357 views

Place n points in a box as far away from each other as possible

Can you suggest an optimal or heuristic algorithm for placing points on a 2D plane (within a constrained space) such that minimum distance between any two points is maximized. In other words, I'm ...
6
votes
2answers
235 views

Inferring an LP cost vector from its solution

Say I have the following linear programming formulation in standard form: \begin{equation*} \begin{array}{rl} \mathbf{x}^* = \underset{\mathbf{x}}{\text{arg}\;\text{min}} & \mathbf{c}^...
5
votes
1answer
158 views

Local Smoothness vs optimisation in combinatorial problems

Local smoothness is often mentioned in literature analysing different heuristics and meta-heuristics for combinatorial optimisation. What is meant precisely by local smoothness is often left out, but ...
13
votes
3answers
1k views

Successful application of branch-and-bound methods for NP-hard problems

Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems where branch-and-bound has been used. However, I haven't been able to find references to ...
1
vote
1answer
300 views

why are the constraints in the following paper tight?

My question is about the following paper: http://webdocs.cs.ualberta.ca/~maz/publications/ratliff_nathan_2007_3.pdf In section 2 they show Equation 3 (which is just an optimization problem), which ...
14
votes
4answers
2k views

Theoretical study of coordinate descent methods

I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ ...
9
votes
4answers
452 views

Submodular functions: reference request

I would be very much interested in references to the theory of submodular functions (from basics to advanced). In particular, I am studying approximations to hard optimization problems and I want to ...
4
votes
1answer
197 views

Laying paths on a network using minimum number of links/edges

Consider an undirected graph G(V,E), where each edge $e\in E$ has capacity $c(e)$. Also given is a traffic matrix $T_{ij}$ representing the amount of traffic flowing from vertex $i$ to $j$. The goal ...
5
votes
4answers
1k views

Genetic Algorithm to Draw a Graph? Position assignment problem

I have an assignment problem at hand and am wondering how suitable it would be to apply local search techniques to reach a desirable solution (the search space is quite large). I have a directed ...
3
votes
1answer
167 views

Combinatorial algorithm for optimization over semimetric polytope

This question is motivated by the Leighton-Rao relaxation for SPARSEST-CUT. Suppose one wants to find a non-trivial semimetric over an $n$-point space that minimizes a certain linear functional. More ...
7
votes
0answers
120 views

Deterministic Parallel Algorithm for ILP with small number of variables and small coefficients

Given a set of $n$ linear inequalities in $d$ variables where the coefficients are integers of size bounded by $O(\log{n})$ is there a known deterministic parallel algorithm that runs in time $(d\log{...
0
votes
0answers
121 views

On algorithms that minimizes maximal load of bins

There are $n$ bins and $m$ balls, $b_i$ where $0<i\le m$. Balls are with different weights $w_i$ and have dependency between them. ball $b_1$ depends on $b_2$, $b_2$ depends on $b_3$, and so on. It ...
2
votes
2answers
4k views

Solving a Min/Max equation set

In solving a certain game, I've ended up with a set of equalities like these: ...
4
votes
1answer
244 views

Algorithm to transform an arbitrary MIP problem into the corresponding formulation for PSO

Is there an algorithm to transform an arbitrary Mixed Integer Programming problem into the corresponding formulation for Particle Swarm Optimization? I have found some information related to the use ...
29
votes
2answers
836 views

What classes of mathematical programs can be solved exactly or approximately, in polynomial time?

I am rather confused by the continuous optimization literature and TCS literature about which types of (continuous) mathematical programs (MPs) can be solved efficiently, and which cannot. The ...
1
vote
0answers
148 views

Row/column overlay problem for filling in a matrix

I was wondering if the following problem has been studied/has a name: Given a matrix of numbers (may assume to be integers), find the smallest number of rules which define the matrix. Three kinds of ...
4
votes
4answers
615 views

A search problem and no algorithm for it

I would like to learn about the following search problem, in particular, which kind of algorithms exist for it. Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight ...
7
votes
1answer
139 views

Optimal payoff from sampling from a collection of Bernoulli random variables?

Suppose I have several Bernoulli random variables, $\{X_1, \ldots, X_k\}$, each of which has a fixed probability $p_i$ of equaling 1 for each sample. Further suppose each $p_i$ is randomly distributed ...
18
votes
2answers
606 views

Solving a Number-Hopper Maze

My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this: The idea is to start from x and reach o via the normal rules. Additionally, you can "...
9
votes
1answer
315 views

Heuristics for Optimization

Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules (...
1
vote
1answer
388 views

Optimal value of a semidefinite program

Is a local optimum value of a SDP always the global one? If not, what are the conditions for that?
14
votes
4answers
1k views

What's new in compiler optimization techniques over last few years?

I'm interested in optimization of data flow and control flow graphs and in particular more computationally complex. But it will also be interesting to know about the latest inventions in the field of ...
1
vote
2answers
563 views

Bin allocation problem

Despite the warning from the StackExchange Question engine that this question appears subjective, I'm going to ask it anyway. We have a script as part of an application at work which is responsible ...
5
votes
1answer
271 views

Sending people to lunch together with minimal repetition

We have n people and split them up in groups of size x. Each group of x people goes to lunch together. Next time around when the groups are set up people who were in a group last time should not end ...
13
votes
2answers
351 views

Survey of transformations related to the use of SAT solvers

I am starting to investigate the possibility of relying on a SAT solver to tackle an optimisation problem I'm interested in, and am currently looking for a survey that would feature examples of "...
2
votes
2answers
116 views

Asking optimal questions to differentiate object in set

I have a problem in mind and I am sure this is likely an area of active research, but am at a loss as to the correct terminology and thus unable to find any reference literature. It is best explained ...
4
votes
2answers
1k views

Detecting infeasibility of System of Linear Inequalities

Infeasibility of a system of linear inequalities can be detected by using artificial variables and then using an algorithm like the simplex algorithm (or ellipsoid/interior point methods) to find a ...
2
votes
1answer
766 views

Survey on Optimization algorithms

I am trying to solve an optimization problem. I need some help in getting the results or survey on related issues. The question is a bit general but any help in identifying the correct sources would ...
7
votes
1answer
533 views

Is minimax problem NP-Hard when the inner problem is NP-Hard ?

Consider a minimax problem of the form: $\min_{x\in X} \max_{u\in U} f(x,u)$ The outer problem $\min_{x\in X} f(x,u)$ for any given $u$ is polynomially solvable. If the inner problem $\max_{u\in U} ...
23
votes
5answers
2k views

Packing rectangles into convex polygons but without rotations

I am interested in the problem of packing identical copies of (2 dimensional) rectangles into a convex (2 dimensional) polygon without overlaps. In my problem you are not allowed to rotate the ...
1
vote
1answer
154 views

Using a Polynomial Time Algorithm for Upper Bound Recognition to Show Polynomial Time for Evaluation?

Let's say I had an optimization problem $$ \min_{x \in D} f(x) $$ Where $D \subset \mathbb{R}^n$ and $f:\space D \rightarrow \mathbb{R}$, and the minimum is said to exist. Imagine I had a ...
10
votes
3answers
692 views

Applications of MCTS/UCT

MCTS/UCT is a game tree search method that uses a bandit algorithm to select promising nodes to explore. Games are played to their completion randomly and nodes leading to more wins are explored more ...
21
votes
2answers
3k views

How good is the Huffman code when there are no large probability letters?

The Huffman code for a probability distribution $p$ is the prefix code with the minimum weighted average codeword length $\sum p_i \ell_i$, where $\ell_i$ is the length of the $i$th codword. It is a ...
4
votes
2answers
2k views

Why does the Fibonacci sequence produce a worst-case Huffman encoding?

I noticed this in my Algorithms class, but just now got around to asking.
15
votes
3answers
502 views

Bob's Sale (reordering of pairs with constraints to minimize sum of products)

I've asked this question on Stack Overflow a while ago: Problem: Bob's sale. Someone suggested posting the question here as well. Someone has already asked a question related to this problem here - ...
12
votes
2answers
857 views

Minimum maximal solutions of LPs

Linear programming is, of course, nowadays very well understood. We have a lot of work that characterises the structure of feasible solutions, and the structure of optimal solutions. We have the ...
8
votes
1answer
2k views

What's the difference between online and incremental optimization?

Recently I've read some stuff about incremental optimization problems, but I can't see what's the difference between those and online optimization problems. My impression is that I can define every ...
23
votes
1answer
438 views

Approximately sampling from convex polyhedrons with quantum computers

Quantum computers are very good for sampling distributions that we dont know how to sample using classical computers. For example if f is a Boolean function (from $\{-1,1\}^n$ to ${-1,1}$) that can be ...
7
votes
3answers
2k views

A simple approximation algorithm for the TSP

Consider the following extremely simple approximation algorithm for the TSP. Input: A complete weighted graph $G=(V,E).$ Take any three vertices $a,b,c\in V$ and let $H:=(a,b,c,a).$ While there ...
3
votes
2answers
170 views

Find the right/best track combination for a given distance, using a genetic algorithm or ?.

I have a list of tracks (model railroad tracks) with different length, example: TrackA on 3.0cm, TrackB on 5.0cm, TrackC on 6.5cm, TrackD on 10.5cm Then I want to find out of what kind of track I ...
5
votes
2answers
1k views

Is the following problem NP-Hard?

I'm not expert on complexity theory and combinatorial optimization. I want to know if the following problem (or similar) is known in the scientific literature, and if you think it is NP-complete. ...
5
votes
3answers
409 views

Is there a way to solve an optimization problem where a decision variable shows up in an upper bound (or lower bound) of summation?

minimize/maximize $\displaystyle \sum_{i=0}^{f(n)} G(x,n)$ s.t. $n \ge 1$ and $x$ in some feasible region The decision variables are $x$ (a vector) and $n$ (a scalar). How is this type of ...