# Questions tagged [linear-programming]

For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.

375 questions
Filter by
Sorted by
Tagged with
50 views

### How to use cplexAPI to solve quadratic programs/quadratically constrained linear programs?

I am trying to use cplexAPI to solve quadratic programs or quadratically constrained linear program. While it seems to be pretty straightforward to use ...
87 views

### Harvest planning problem

I need to model the following problem: For a planning horizon of $P$ equal periods, one has $N$ harvesting locations and $K$ contractors who can harvest at those locations ($K < N$). Each ...
119 views

### In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something. I'm working ...
78 views

### Resource Optimization For Cargo Handling

I have to work on some real world data and come up with an optimization technique to handle cargo. To make thing simpler let's assume that there are 2 types of resources Manpower (150 ton / 8 hour) ...
50 views

58 views

### Write in ILP: If $x$ within range then $s=1$, else $0$

How can write the following function in LP: $$s= \begin{cases} 1 & 1 \leq x \leq C \\ 0 & \text{otherwise} \end{cases}$$ where $x$ takes only non-negative integers and $C$ is some large ...
112 views

### Benders decompositions: Number of iterations does not remain the same

I am solving an LP (i.e 118-bus system economic dispatch for 130% loading) using Benders decomposition. The problem takes 26 iterations to converge. This means that the process adds 25 cuts to the ...
73 views

### Optimisation Multiple Constraints

I am trying to solve a linear algebra problem: an optimisation problem and I am using CVXOPT. I've split the problem into 3 components In its simplest form, The general formulation for CVXOPT is \...
183 views

### Are decomposition methods applicable on large linear programs?

Working on a very large Linear Program, we tried out some primitive implementations of decomposition techniques such as Lagrangian relaxation and column generation. However, none of these were able to ...
164 views

### Are there small LPs out there?

A fair share of academic research and software development focuses on solving ever-larger problems, particularly when it comes to LPs. I am however curious to know in what contexts and to what extent ...
84 views

### Linearly independent rows in simplex

I'm having some trouble understanding about the independent rows in a basic solution. In the book Introduction to linear optimization by B&T, the authors give the definition of a basic solution as ...
100 views

### Upper and lower bounds of a variable equal

I'm working on a MILP (Mixed-Integer Linear Programming) problem with the Java API of Cplex. In order to easily exclude some variables from my problem I thought about setting both their lower and ...
73 views

### Examples of LP problems in irrigate engineering

I need examples of linear programming problems applied to irrigation system. My idea is to give students many examples of LP applications in the irrigation engineering.
81 views

### Minimax problem with a large high dimensional feasible region

How to solve minimax mixed integer problem with a large high dimensional feasible region? \begin{aligned} \max_{\vec{x}}\min_{\vec{y}} \quad & \vec{r} \cdot \vec{x} + \vec{s} \cdot \vec{y}\\ \...
91 views

### KKT conditions analysis for binary constraints

I am wondering if boolean constraints in a linear program can be solved (after linear relaxation from $x\in\{0,1\}$ to both $x\ge0$ and $x\le1$) using KKT analysis. Most of the algorithms that I have ...
119 views

### Linear Relaxation of Boolean Constraint for Solving Integer Linear Program Using KKT

I am trying to convert a boolean LP to LP using LP relaxation by converting $x \in {0,1}$ to both $x \ge 0$ and $x \le 1$. Then to use it in my problem analysis, I am trying to build the KKT ...
281 views

### Model "if and only if" indicator constraints in Linear programming

Apologies if this question has been asked, but I haven't been able to find it. I'm modelling something with Gurobi and want to do the following: \begin{align}\text{cond} < \dfrac{1}{3} &\iff x =...
231 views

### CPLEX log always the same after hours ("Gap" and "Best Integer" always blanks)

I'm using the Java API of CPLEX 12.6.1 (with license) to solve a MILP (Mixed-Integer Linear Programming) maximization problem. The point is that, after 21 hours, CPLEX has consumed 32 GB of RAM and ...
77 views

### Need help with an appointment scheduling problem

I am currently stuck on writing a linear programming model to describe the process of appointment scheduling for an Oncological Center. I wanted to share it with you guys and see if anyone here could ...
53 views

### Employee allocation based on ranking: Mathematical Model

Suppose I have three employees and I have to assign three employees based on their ranks. If an employee has rank 1 that means he is best. Say, I have the following table ...
193 views

### Simplified risk game: writing a pratical Minimax objective for mixed integer programming

Problem To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ...
76 views

### MODM to create balanced groups of students to maximise diversity

I am very new to LP, Goal Seek, Decision Models etc and I have a multiple-objective decision making problem that may or may not require a mix of techniques although I am trying to solve it purely ...
79 views

### An efficient Integer programming model for the minimum spanning tree problem?

Let $T=(V, E')$ be a spanning tree of a graph $G=(V, E)$. Rather than verifying for any subset of vertices $S\subseteq V$ that $|E'(S)|=|S|-1$, is there an efficient way to satisfy the spanning tree ...
121 views

### Best way to add dummy to transportation problem? Zero cost will be always chosen first?

I know that an unbalanced transportation problem could be made a balanced transportation problem by adding a dummy node which equals the difference between demand and supply. In literature, dummy ...
245 views

### What is a good way to penalise LP relaxation?

I have a binary integer program. It is of a large size and the solver is taking longer time. I am thinking of relaxing the binary integer variable and making it a continuous variable. How can I ...
56 views

94 views

### Objective function with exponential coefficients

I have a linear programming problem, with $n$ variables and $a\leq x_{i} \leq b$ for each variable $x_{i}$, where the objective function is $\min \sum\limits_{i=1}^{n}{2^{i} x_{i}}$ Is it true that, ...
640 views

### Linear Optimization Library for C++ with GPU Support

Does anyone know any linear optimization libraries for C++ supporting GPUs for parallelization? If multiple, which do you recommend? The GPU support is important to me since I am dealing with large ...
102 views

### Multiple If else constraints in Mixed integer programming

How to formulate the following as constraints in MILP? a = y, if x= 0, a = 0, if x != 0, . . . . a[i][j] = b[i][j-1] + y, if x[j]=i, a[i][j] = a[i][j-1], if x[j] != i, ... . . . b...
49 views

### Specializing Iterations of Dantzig-Wolfe Decomposition with an Oracle

This arises from an engineering problem I am working on. Let $\mathbf{c}_i,\mathbf{a}_i\in \mathbb{R}^{d}$ be a given set (collection) of vectors where $i\in\{1,\dots,n\}$. Define the bounded ...
I am trying to add some more constraints to the flow-based ADVRP model in Almoustafa et al. (2013)1 (pp.4). The mentioned model caps the travel distance, while I cap the travel time. Let $U$ represent ...